[Algorithm] 21 이진 검색 트리

이진 검색 트리

• 자료들을 일정한 순서에 따라 정렬한 상태로 저장
• 원소의 추가 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 수행

정의

• 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드 만을 가질 수 있는 트리
• 자식 노드 들의 배열 대신 두 개의 포인터 left와 right를 담는 객체로 구현
• 이진 탐색 에서 아이디어를 가져와서 만든 트리
• N개의 원소 중에서 원하는 값을 찾는데, 매번 후보의 수를 절반씩 줄임 → O(lgN)

순회

• 중위 순회하면 크기 순서로 정렬된 원소의 목록
• 현재 노드의 왼쪽에는 현재 원소보다 작은 원소, 오른쪽에는 현재 원소보다 큰 원소
• 최대 최소 원소를 쉽게 구할 수 있음

자료의 검색

• 한 번 원소를 비교하는 것 만으로도 전체 대상의 절반을 줄일 수 있음 → 이진 탐색과 비슷한 속도

조작

• 배열보다 이진 검색 트리가 유용한 경우는 집합에 원소를 추가하거나 삭제하는 연산을 할 때이다.
• 정렬된 자료구조에서 원소를 추가하거나 삭제할 때 장점
• 새 원소가 들어갈 위치를 찾고 거기에 노드만 추가하면 됨
• 원소 삭제의 경우 어려움
• 원소 삭제 (합치기) : 노드 t를 지울 거라면, t의 두 서브트리를 합친 새로운 트리를 만든 뒤 이 트리를 t를 루트로 하는 서브트리와 교체

합치기 연산

• 이진 검색 트리에서 삭제를 구현하는 방법 중 ‘합치기’ 연산이 가장 간편함
• 만약 노드 t를 지울 거라면, t의 두 서브트리를 합친 새로운 트리를 만들고 이 트리를 t를 루트로 하는 서브트리와 바꿔치기 한다.

두 트리 A와 B를 합치려고 한다.

A의 최대 원소는 B의 최소 원소보다 더 작다.(A와 B는 노드 t의 왼쪽/오른쪽 서브트리이므로)

A 트리 루트 a가 합쳐질 트리의 루트가 되도록 합쳐보자.

a의 왼쪽 서브트리에 있는 원소들은 모두 a 원소보다 작다.

a의 오른쪽 서브트리와 B에 있는 원소들은 모두 a의 원소보다 크다.

따라서, a의 오른쪽 서브트리와 B를 재귀적으로 합치고 이 트리를 a의 오른쪽 자식으로 두면 합치기 연산이 완료

시간 복잡도 분석과 균형 잡힌 이진 검색 트리

• 이진 검색 트리에 대한 모든 연산은 루트에서부터 한 단계씩 트리를 내려 가면 재귀 호출을 통해 수행
• 최대 재귀 호출의 횟수는 트리의 높이 h 와 같다. → 시간복잡도 =O(h)
• 원소 N개일 때 트리의 최소 높이 O(lgN)→ 높이가 1 높아질 때마다 트리에 들어갈 수 있는 원소 수가2배 늘어남
• 균형 잡힌 이진 검색 트리 → 트리의 높이가 항상 O(lgN)이 되도록 유지
• ex) 레드 블랙 트리