3.7.1 이진 트리
이진 트리(binary tree)는 각 노드에 왼쪽 자식과 오른쪽 자식이라는 최대 2개(0, 1 또는 2)의 자식이 있는 트리입니다.
이진 탐색 트리(BST, Binary Search Tree)는 다음 방법으로 노드를 정렬한 이진 트리입니다.
1. 왼쪽 하위 트리의 키(key)가 부모 노드의 키보다 작거나 같습니다.
2. 오른쪽 하위 트리의 키가 부모 노드의 키보다 큽니다.
▲ 그림 3-6 이진 탐색 트리
이진 탐색 트리의 API는 다음과 같습니다.
• Insert(k) 트리에 새 원소 k를 삽입합니다.
• Delete(k) 트리에서 원소 k를 삭제합니다.
• Search(k) 트리에서 값이 k인 원소를 검색합니다. 값이 k인 원소는 없을 수도 있습니다.
• FindMax() 트리에서 가장 큰 값을 찾습니다.
• FindMin() 트리에서 가장 작은 값을 찾습니다.
이진 탐색 트리의 모든 연산은 트리가 균형을 이룰 때는 평균적인 시간 복잡도 O(logn)이며, 트리가 균형을 이루지 않을 때는 최악의 시간 복잡도 O(n)입니다.
항상 균형을 유지하는 몇 가지 이진 탐색 트리가 있습니다. 그중에서 가장 유명한 것은 AVL 트리와 레드-블랙 트리(RB-트리)입니다. 정렬된 딕셔너리(dictionary)는 RB-트리를 사용해 구현합니다.