이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리(Binary Search Tree, BST)는 각 노드에 키(key)를 저장하는 트리 형태의 자료구조다. BST는 다음 특징을 가진다.
- 이진 트리(Binary Tree): 각 노드는 최대 두 개의 자식 노드를 가질 수 있다.
- 탐색 트리(Search Tree): 각 노드의 키 값은 왼쪽 서브트리의 모든 키 값보다 크고, 오른쪽 서브트리의 모든 키 값보다 작다.
BST의 장점
- 검색 효율: 탐색 트리의 특성상, 이진 탐색과 유사하게 O(log n) 시간 복잡도로 원하는 키를 찾을 수 있다.
- 순서 : 중위 순회(inorder traversal)를 통해 키 값을 정렬된 순서로 얻을 수 있다.
- 동적 자료구조: 삽입 및 삭제 연산을 효율적으로 수행할 수 있다.
BST의 주요 연산
1. Search (탐색)
BST에서 특정 키 값을 가진 노드를 찾는 과정이다. root 노드에서 시작하여, 찾는 키 값과 현재 노드의 키 값을 비교하며 왼쪽 또는 오른쪽 서브트리로 이동한다.
예시: 키 값 4 탐색
- root 노드(6)에서 시작하여, 4 < 6 이므로 왼쪽 서브트리로 이동한다.
- 현재 노드(2)에서, 4 > 2 이므로 오른쪽 서브트리로 이동한다.
- 현재 노드(4)에서, 4 = 4 이므로 탐색 완료.
2. Insertion (삽입)
BST에 새로운 key-value 쌍을 추가하는 과정이다. 먼저 탐색 과정과 동일하게 삽입할 위치를 찾는다. 만약 찾는 키 값이 이미 존재하면 값을 갱신하고, 그렇지 않으면 새로운 노드를 생성하여 삽입한다.
예시: 키 값 5 삽입
- 루트 노드(6)에서 시작하여, 5 < 6 이므로 왼쪽 서브트리로 이동한다.
- 현재 노드(2)에서, 5 > 2 이므로 오른쪽 서브트리로 이동한다.
- 현재 노드(4)에서, 5 > 4 이지만 오른쪽 자식 노드가 없으므로, 오른쪽에 새로운 노드(5)를 생성하여 삽입한다.
3. Deletion (삭제)
BST에서 특정 키 값을 가진 노드를 삭제하는 과정이다. 먼저 탐색 과정과 동일하게 삭제할 노드를 찾는다. 삭제할 노드의 자식 노드 개수에 따라 다음과 같이 처리한다.
- 자식 노드가 없는 경우 (Leaf Node): 해당 노드를 간단히 삭제한다.
- 자식 노드가 하나인 경우: 해당 노드를 삭제하고, 자식 노드를 부모 노드에 연결한다.
- 자식 노드가 두 개인 경우: 해당 노드의 오른쪽 서브트리에서 가장 작은 키 값을 가진 노드(inorder successor)를 찾아 삭제할 노드의 위치로 옮기고, inorder successor를 삭제한다. (inorder successor는 항상 자식 노드가 0개 또는 1개다.)
예시: 키 값 2 삭제
- 루트 노드(6)에서 시작하여, 2 < 6 이므로 왼쪽 서브트리로 이동한다.
- 현재 노드(2)에서, 2 = 2 이므로 삭제할 노드이다.
- 삭제할 노드(2)는 자식 노드를 두 개 가지므로, 오른쪽 서브트리에서 가장 작은 키 값을 가진 노드 [4]를 찾았다.
- 노드[4]를 삭제할 노드[2]의 위치로 옮기고, 노드[4]의 원래 위치에서 삭제다.
* Inorder Traversal (중위 순회)
BST의 모든 노드를 정렬된 순서로 방문하는 방법이다. 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순으로 방문한다.
def inorder_traversal(node):
if node is not None:
inorder_traversal(node.left)
print(node.key) # 현재 노드 방문
inorder_traversal(node.right)
예시: 위에서 삭제 연산 후의 BST에 대해 inorder traversal을 수행하면 1, 4, 6, 8, 9 순으로 출력된다.
BST 성능
마무리
이진 탐색 트리는 탐색, 삽입, 삭제 연산을 효율적으로 지원하는 강력한 자료구조이다. 정렬된 데이터를 다루거나 효율적인 검색이 필요한 상황에서 유용하게 활용될 수 있다. 하지만 트리의 균형이 깨지면 성능이 저하될 수 있다는 점을 유의해야 한다. 이러한 단점을 보완하기 위해 다양한 종류의 균형 탐색 트리(Balanced Search Tree)가 개발되었으며, 대표적으로 AVL 트리, 레드-블랙 트리 등이 있다. 이에 관하여 다음 포스팅에서 자세히 다뤄보도록 하겠다.
(https://hyeonb.blogspot.com/2024/03/blog-post.html)
[자료구조] Sorted map & skip list
