[자료구조] 이진 탐색 트리(Binary Search Tree)

 

이진 탐색 트리란?

이진탐색을 위한 이진트리.

• 모든 노드의 Key는 유일하다. (중복 없음)
• 왼쪽 자식은 나보다 작다
• 오른쪽 자식은 나보다 크다

 

이진 탐색 트리의 장점

• 일반 이진 탐색은 중앙 요소를 알아야하기 때문에 "배열"에서만 사용 가능.
  • 연결 리스트는 이진 탐색에 적합하지 않다.
  • 배열의 크기가 변화면 안되는 정적
• 이진 탐색 트리
  • 배열을 사용해 탐색할 때보다 시간 복잡도가 작다 O(logN) 
  • 동적으로 데이터 집합 크기가 바뀌고 순서가 바뀌어도 문제가 없다.

 
주의할 점

트리 모양이 한쪽으로 치우치면 트리 탐색의 장점인 O(logN) 시간복잡도가 마치 배열을 순차 탐색하는 듯하는 O(N)에 가까워지게 된다.
 
=> 데이터를 추가/삭제 할 때 트리 모양을 균형있게 만드는 "레드 블랙 트리"가 있다. (C++ map STL에서 사용된다!)
 

---

이진 탐색 트리 구현

1) 탐색
2) 삽입
3) 삭제
 

탐색

 
루트 노드부터 시작해 찾을 값과 크기를 비교하며 내려오면서 찾으면 된다.

• 찾으려는 값 < 현재 트리의 루트 노드 값
  • 왼쪽 서브트리로 내려감.( 왼쪽 서브트리의 모든 값은 루트노드 보다 작다 )
• 찾으려는 값 > 현재 트리의 루트 노드 값
  • 오른쪽 서브트리로 내려감

찾을 때까지 재귀.
 

삽입

이진 탐색 규칙 ( 왼쪽은 작고 오른쪽은 크다) 를 만족해야 하기 때문에 삽입될 위치도 이진 탐색으로 찾아야 한다.
"추가"되는 것은 곧 조상부터 크기를 비교하며 내려오면서 누군가의 왼쪽, 오른쪽 자식으로 세팅된다는 것.
 

삭제

 
삭제는 케이스를 나눠서 구현해줘야 한다.

1. 삭제할 노드의 서브트리가 0개 -> 그냥 삭제해버리면 됨
2. 삭제할 노드의 서브트리가 1개 -> 내 부모 노드에서 내가 있는 쪽에 서브트리를 붙여준다
3. 삭제할 조드의 서브트리가 2개 

1번과 2번은 간단하다. 
3번을 좀 자세히 생각해 보면 현재의 서브트리에서 루트를 봤을 때,
오른쪽 자식의 서브트리는 모두 크고 왼쪽 자식의 서브트리는 모두 작다.
 
이걸 잘 생각해보면, 삭제될 노드가 삭제되고 나서 그 자리를 대체할 노드가 무엇인지 찾을 수 있다.
1) 오른쪽 서브트리의 가장 왼쪽 노드
2) 왼쪽 서브트리의 가장 오른쪽 노드
 
둘 중 하나이다. 
 
전체코드는 깃허브에
https://github.com/mina3215/STL/blob/main/map/BST.cpp
 
 
 
 
 
 
https://ansohxxn.github.io/algorithm/bst/

(C++) 이진 탐색 트리 (장단점, 삽입, 삭제, 탐색, 순회)

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC

이진 탐색 트리 - 위키백과, 우리 모두의 백과사전