사전(Dictionary) 자료구조와 이진 트리
추상 자료형(Abstract Data Type)인 사전(Dictionary)을 구현할 때, 각 노드는 값(value)과 연결됩니다. 사전은 본질적으로 키(key)들의 집합이며, 이 키들은 반드시 전체 순서(total ordering)를 따르는 원소여야 합니다. 각 키에는 추가적인 정보가 함께 저장될 수 있지만, 이는 개념적 이해에는 큰 영향을 주지 않습니다.
이진 탐색 트리의 불변식(Invariant)
사전을 트리 구조로 구현하면, 각 노드는 고유한 키를 가집니다. 트리 내 임의의 노드 u에 대해 다음과 같은 불변식이 성립합니다.
- 왼쪽 서브트리(u.l)에 있는 모든 키는 노드 u의 키(u.k)보다 엄격하게 작습니다.
- 오른쪽 서브트리(u.r)에 있는 모든 키는 노드 u의 키(u.k)보다 엄격하게 큽니다.
이러한 불변식에 따라 조직된 트리를 이진 탐색 트리(Binary Search Tree)라고 부릅니다.
중위 순회를 통한 정렬된 키 목록 얻기
이 불변식의 가장 큰 장점 중 하나는 중위 순회(in-order traversal)를 사용하면 선형 시간 O(n) 안에 정렬된 키 목록을 얻을 수 있다는 점입니다. 중위 순회는 재귀적으로 다음과 같이 정의됩니다.
- 트리가 비어 있으면 아무 작업도 수행하지 않습니다.
- 그렇지 않으면 먼저 왼쪽 서브트리를 재귀적으로 순회합니다.
- 루트 노드를 방문하여 보고(report)합니다.
- 마지막으로 오른쪽 서브트리를 재귀적으로 순회합니다.
이진 탐색 트리의 주요 연산
이진 탐색 트리에서는 탐색(search), 삽입(insert), 삭제(delete) 등 다양한 연산을 수행할 수 있습니다. 특히 탐색 연산은 트리의 높이(height)에 비례하는 시간 복잡도를 가지며, 균형이 잘 잡힌 트리라면 O(log n)의 효율성을 기대할 수 있습니다. 그중에서도 탐색은 다른 모든 연산의 기반이 되는 가장 중요한 연산입니다.