트리 알고리즘: Self-Balancing Binary Search Tree
Data structure remind
지난 학기 자료구조 시간에 다양한 데이터 구조에 대해 배운 바 있다. 대표적인 데이터 구조로는 배열(array)과 연결 리스트(linked list)가 있다. 배열은 데이터를 연속된 메모리 공간에 저장하는 반면, 연결 리스트는 데이터를 노드(node) 단위로 연결하여 저장한다. 각 데이터 구조는 삽입, 삭제, 검색 연산에 대해 서로 다른 시간 복잡도를 갖는다.
| 데이터 구조 | 검색 | 삽입/삭제 |
|---|---|---|
| Sorted array | O(log n) | O(n) |
| Sorted linked list | O(n) | O(1) |
이진 트리와 이진 검색 트리
트리(tree)는 계층적인 구조를 갖는 데이터 구조이다. 이진 트리(binary tree)는 각 노드가 최대 두 개의 자식 노드를 갖는 트리이다. 이진 검색 트리(binary search tree)는 이진 트리의 특수한 형태로, 왼쪽 자식 노드의 키(key)는 부모 노드의 키보다 작고, 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다는 조건을 만족하는 트리이다.
 |
| BST(Binary Search Tree) |
Self-Balancing Binary Search Tree
이진 검색 트리는 최악의 경우, 즉 트리가 한쪽으로 치우쳐 linked list 형태가 되는 경우 삽입, 삭제, 검색 연산에 O(n) 시간이 소요될 수 있다. 이러한 문제를 해결하기 위해 고안된 것이 Self-Balancing Binary Search Tree이다. Self-Balancing Binary Search Tree는 트리의 균형을 유지하기 위해 노드를 재배치하는 알고리즘을 사용한다.
 |
| O(n) vs O(log n) |
Rotation
회전(rotation)은 이진 검색 트리의 구조를 변경하는 연산으로, 트리의 균형을 유지하는 데 사용된다. 회전 연산은 트리의 특정 노드를 기준으로 수행되며, 노드의 왼쪽 자식과 오른쪽 자식의 위치를 바꾸는 방식으로 동작한다.
 |
| Rotation |
Red-Black Tree
Red-Black Tree는 Self-Balancing Binary Search Tree의 한 종류로, 각 노드에 빨간색 또는 검은색을 부여하여 트리의 균형을 유지한다. Red-Black Tree는 다음과 같은 특징을 갖는다.
- 모든 노드는 빨간색 또는 검은색이다.
- 루트 노드는 검은색이다.
- 모든 잎 노드(NIL)는 검은색이다.
- 빨간색 노드의 자식 노드는 항상 검은색이다.
- 모든 노드에서 NIL 노드까지의 경로에 포함된 검은색 노드의 수는 같다.
Red-Black Tree의 구체적인 동작에 대해서는 기존 자료구조 관련 글을 참고하고, 이번 시간에는 어떻게 Red-Black Tree가 O(log n)의 time complexity를 갖는지 알아보고자 한다.
Red-Black Tree time complexity
 |
| Red-Black Tree worst case |
결과적으로 Red-Black tree는 트리의 높이를 log n으로 유지하며, 삽입, 삭제, 검색 연산을 O(log n) 시간에 수행할 수 있다.
결론
Red-Black Tree는 이진 검색 트리의 단점을 극복하고 삽입, 삭제, 검색 연산을 효율적으로 수행할 수 있는 자료 구조이다. 트리의 균형을 유지하기 위한 알고리즘을 통해 최악의 경우에도 O(log n) 시간 복잡도를 보장한다.
추천글 :
[자료구조] Red-Black Tree
(https://hyeonb.blogspot.com/2024/06/red-black-tree.html)
[알고리즘] hash table - direct addressing, hash function, chaining
(https://hyeonb.blogspot.com/2024/10/hash-table-direct-addressing-hash.html)
[알고리즘] Algorithmic Analysis - correctness with induction
(https://hyeonb.blogspot.com/2024/09/algorithmic-analysis-correctness-with.html)
