이진 검색 트리

검색트리

자료들을 일정한 순서에 따라 정렬한 상태로 저장해둠

원소의 추가와 삭제 + 특정 원소의 존재 여부 확인 등 다양한 연산을 빠르게 수행할 수 있음

검색트리가 사용될 수 있는 곳 예시

- 이미 가입한 사용자들의 주민등록번호를 저장해두고, 특정 사용자가 이미 가입되었나 찾기

- 사용자의 ID를 사용자 정보로 대응시키는 사전 객체 만들기

- 모든 학생들의 시험 점수를 저장해놓고, 나보다 1등 위인 사람과 1등 아래인 사람 찾기

검색트리 중 가장 흔하게 사용되는 것이 바로 이진 검색 트리이다.

이진 검색 트리

각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리

왼쪽에는 root보다 작은 값, 오른쪽에는 root보다 큰 값이 들어감

원하는 값을 찾아가는 과정은 배열에서의 이진 탐색과 비슷함. 시간복잡도는 O(lgN)

순회

중위 순회하면 오름차순 정렬을 얻을 수 있음

즉, 첫번쨰 원소는 최소값이고 마지막 원소는 최대값인 것임

자료의 검색

root가 16인 트리에서 15를 찾는다면 왼쪽으로 내려가면 됨

이렇게 한 번 비교하는 것으로 절반을 줄일 수 있다.

=> 이진탐색과 비슷한 속도

조작 ★

이진 검색 트리는 원소를 추가하거나 삭제하는 조작 연산을 할 때 진가를 발휘함

- 추가 : 새 잎 노드 생길 뿐 트리에 영향 X

- 삭제 : 트리의 어디에서도 일어날 수 있음. 합치기를 구현해야함 (책 700p)

이진 검색 트리는 표준 라이브러리에서 지원하지만, 다음 경우에 지원하는 언어는 거의 없음

1) X보다 작은 원소의 수 찾기

2) k번째 원소 찾기

즉, 직접 이진트리를 구현해야함

시간복잡도

최대 호출의 횟수는 트리의 높이 h임

즉, 모든 연산의 시간복잡도는 O(h)임

그러나 이 경우는 기울어진 트리이고, 이런 형태론 이진 검색 트리를 사용한 의미가 사라짐. 사실상 연결리스트와 같아짐.

이상적인 트리는 노드가 들어갈 수 있는 자리가 꽉 차 있는 '평평한' 트리임.

트리의 높이가 1 높아질 때마다 원소의 개수가 대략 두 배 늘어남

=> 트리의 시간복잡도는 O(lgN)이 됨

균형 잡힌 이진 검색 트리 (balanced binary search tree)

항상 트리의 높이가 O(lgN)이 되도록 유지함

ex) 레드-블랙 트리