[자료구조] 이진 탐색 트리(Binary Search Tree)
이진 탐색 트리란?
이진탐색을 위한 이진트리.
- 모든 노드의 Key는 유일하다. (중복 없음)
- 왼쪽 자식은 나보다 작다
- 오른쪽 자식은 나보다 크다
이진 탐색 트리의 장점
- 일반 이진 탐색은 중앙 요소를 알아야하기 때문에 "배열"에서만 사용 가능.
- 연결 리스트는 이진 탐색에 적합하지 않다.
- 배열의 크기가 변화면 안되는 정적
- 이진 탐색 트리
- 배열을 사용해 탐색할 때보다 시간 복잡도가 작다 O(logN)
- 동적으로 데이터 집합 크기가 바뀌고 순서가 바뀌어도 문제가 없다.
주의할 점

트리 모양이 한쪽으로 치우치면 트리 탐색의 장점인 O(logN) 시간복잡도가 마치 배열을 순차 탐색하는 듯하는 O(N)에 가까워지게 된다.
=> 데이터를 추가/삭제 할 때 트리 모양을 균형있게 만드는 "레드 블랙 트리"가 있다. (C++ map STL에서 사용된다!)
이진 탐색 트리 구현
1) 탐색
2) 삽입
3) 삭제
탐색
루트 노드부터 시작해 찾을 값과 크기를 비교하며 내려오면서 찾으면 된다.
- 찾으려는 값 < 현재 트리의 루트 노드 값
- 왼쪽 서브트리로 내려감.( 왼쪽 서브트리의 모든 값은 루트노드 보다 작다 )
- 찾으려는 값 > 현재 트리의 루트 노드 값
- 오른쪽 서브트리로 내려감
찾을 때까지 재귀.
삽입
이진 탐색 규칙 ( 왼쪽은 작고 오른쪽은 크다) 를 만족해야 하기 때문에 삽입될 위치도 이진 탐색으로 찾아야 한다.
"추가"되는 것은 곧 조상부터 크기를 비교하며 내려오면서 누군가의 왼쪽, 오른쪽 자식으로 세팅된다는 것.
삭제
삭제는 케이스를 나눠서 구현해줘야 한다.
- 삭제할 노드의 서브트리가 0개 -> 그냥 삭제해버리면 됨
- 삭제할 노드의 서브트리가 1개 -> 내 부모 노드에서 내가 있는 쪽에 서브트리를 붙여준다
- 삭제할 조드의 서브트리가 2개
1번과 2번은 간단하다.
3번을 좀 자세히 생각해 보면 현재의 서브트리에서 루트를 봤을 때,
오른쪽 자식의 서브트리는 모두 크고 왼쪽 자식의 서브트리는 모두 작다.
이걸 잘 생각해보면, 삭제될 노드가 삭제되고 나서 그 자리를 대체할 노드가 무엇인지 찾을 수 있다.
1) 오른쪽 서브트리의 가장 왼쪽 노드
2) 왼쪽 서브트리의 가장 오른쪽 노드
둘 중 하나이다.
전체코드는 깃허브에
https://github.com/mina3215/STL/blob/main/map/BST.cpp
https://ansohxxn.github.io/algorithm/bst/
(C++) 이진 탐색 트리 (장단점, 삽입, 삭제, 탐색, 순회)
<뇌를 자극하는 알고리즘> 책을 참고했습니다.
ansohxxn.github.io
https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC
이진 탐색 트리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전.
ko.wikipedia.org