균형 이진 탐색 트리: AVL, Red-Black, B-Tree
편향 문제를 해결하는 균형 탐색 트리인 AVL 트리, 레드-블랙 트리, B-Tree의 균형 유지 방식과 쓰임새를 비교한다.
시리즈 · 자료구조 · 알고리즘8 / 13
- 시간 복잡도와 공간 복잡도
- 재귀 함수와 꼬리 재귀 최적화
- 연결 리스트(Linked List)
- 스택과 큐: 원형 큐 구현과 덱
- 해시 테이블: 해시 함수와 충돌 처리
- 트리와 이진 탐색 트리
- 힙(Heap)과 우선순위 큐
- 균형 이진 탐색 트리: AVL, Red-Black, B-Tree
- 그래프: 인접 행렬과 인접 리스트
- 최단 경로 알고리즘: BFS, 다익스트라, 벨만-포드, 플로이드-워셜, A*
- 최소 신장 트리(MST): Kruskal, Prim, Union-Find
- 정렬 알고리즘: 퀵·병합·기수 정렬부터 Timsort까지
- Thread-Safe 자료구조: Python GIL과 Java ConcurrentHashMap
균형 이진 탐색 트리(BBST)
이진 탐색 트리는 삽입 순서에 따라 한쪽으로 편향되어 탐색이 O(N)까지 느려질 수 있다. 균형 이진 탐색 트리(Balanced Binary Search Tree)는 삽입과 삭제 때마다 스스로 높이 균형을 맞춰 높이를 O(log N)으로 유지한다.
대표적인 균형 탐색 트리로 AVL 트리, 레드-블랙 트리가 있고, 노드가 여러 자식을 갖도록 확장한 B-Tree, B+Tree, B*Tree가 있다.
AVL 트리
모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리이다. 삽입이나 삭제로 이 조건이 깨지면 회전(rotation) 으로 높이를 다시 맞춘다.
균형이 깨진 노드를 A, 새로 삽입된 노드를 N이라고 하면 네 가지 경우가 있다.
| 타입 | N이 삽입된 위치 | 해결 |
|---|---|---|
| LL | A의 왼쪽 자식의 왼쪽 | 오른쪽 회전 1회 |
| LR | A의 왼쪽 자식의 오른쪽 | 왼쪽 회전 후 오른쪽 회전 |
| RR | A의 오른쪽 자식의 오른쪽 | 왼쪽 회전 1회 |
| RL | A의 오른쪽 자식의 왼쪽 | 오른쪽 회전 후 왼쪽 회전 |
B-Tree와 B+Tree
B-Tree는 한 노드가 여러 개의 키와 여러 자식을 가질 수 있는 균형 탐색 트리이다. 이진 트리는 아니지만 모든 리프 노드가 같은 깊이에 있도록 균형을 유지한다.
B+Tree는 실제 데이터를 리프 노드에만 두고, 리프 노드끼리 연결 리스트로 이어 범위 탐색을 쉽게 한 구조이다.
데이터베이스 인덱스에서 B-Tree가 어떻게 쓰이는지는 MySQL B-Tree 인덱스 글에 정리했다.
레드-블랙 트리
각 노드가 빨간색 또는 검은색을 갖는 자가 균형 이진 탐색 트리이다.
성질
- 모든 노드는 빨간색 혹은 검은색이다.
- 루트 노드는 검은색이다.
- 모든 리프 노드(NIL)는 검은색이다. NIL은 자료를 갖지 않고 트리의 끝을 나타내는 노드이다.
- 빨간색 노드의 자식은 검은색이다. 즉 빨간색 노드가 연속으로 나올 수 없다(No Double Red).
- 어떤 노드에서 리프 노드까지 가는 모든 경로에는 같은 수의 검은색 노드가 있다(Black Depth가 같다).
균형이 보장되는 이유
이 성질들로부터 루트에서 가장 먼 리프까지의 거리가 가장 가까운 리프까지의 거리의 두 배를 넘지 않는다는 결론이 나온다.
- 4번 성질에 따라 어떤 경로에도 빨간색 노드가 연이어 나타날 수 없다.
- 최단 경로가 모두 검은색 노드로만 구성되어 있다면, 최장 경로는 검은색과 빨간색이 번갈아 나오는 경로이다.
- 5번 성질에 따라 모든 경로의 검은색 노드 수가 같으므로, 최장 경로는 최단 경로의 두 배보다 길어질 수 없다.
삽입
새 노드는 항상 빨간색으로 삽입한다. 이때 부모도 빨간색이면 Double Red가 발생하고, 부모의 형제 노드(삼촌, U)의 색에 따라 처리 방법이 나뉜다.
| 삼촌 노드의 색 | 처리 |
|---|---|
| 검은색 | Restructuring |
| 빨간색 | Recoloring |
Restructuring
새 노드(N), 부모(P), 조부모(G)를 정렬해 가운데 값을 부모로 올리고 나머지 둘을 자식으로 둔다. 그리고 올라간 노드를 검은색, 두 자식을 빨간색으로 바꾼다. 한 번으로 끝나며 위쪽으로 전파되지 않는다.
Recoloring
부모(P)와 삼촌(U)을 검은색으로, 조부모(G)를 빨간색으로 바꾼다. 조부모가 루트라면 다시 검은색으로 바꾼다.
조부모가 빨간색이 되면서 조부모와 그 부모 사이에 다시 Double Red가 생길 수 있다. 이 경우 조부모를 새 노드로 보고 같은 과정을 위로 올라가며 반복한다.
삭제
삭제되는 노드가 빨간색이면 검은색 노드의 수가 변하지 않으므로 문제가 되지 않는다. 검은색 노드가 삭제되면 5번 성질이 깨지므로 색 변경과 회전으로 다시 맞춰야 한다.
레드-블랙 트리를 사용하는 이유
레드-블랙 트리는 삽입, 삭제, 검색 모두 최악의 경우에도 O(log N)의 실행 시간을 보장한다. 실시간 처리처럼 실행 시간의 상한이 중요한 경우에 유용하고, 일정한 실행 시간을 보장하는 다른 자료구조를 만드는 데에도 쓰인다. C++의 std::set이 보통 레드-블랙 트리로 구현된다.
AVL 트리와의 비교
둘 다 삽입, 삭제, 검색이 O(log N)이지만 균형을 맞추는 엄격함이 다르다.
- AVL 트리는 더 엄격하게 균형을 유지한다. 트리 높이가 더 낮아 조회에는 유리하지만, 삽입과 삭제 때 균형 조건을 확인하고 회전하는 비용이 더 자주 든다.
- 레드-블랙 트리는 균형 조건이 느슨하다. 색만 바꾸고 끝나는 경우가 많고 회전 횟수가 적어, 삽입과 삭제가 잦은 경우에 일반적으로 선호된다.
AVL 트리와 레드-블랙 트리의 리밸런싱 과정은 어떻게 다른가?
AVL 트리는 삽입이나 삭제 후 변경된 위치에서 루트 방향으로 올라가며 각 노드의 높이 차이를 검사하고, 조건이 깨진 곳마다 회전한다. 레드-블랙 트리는 색 규칙이 깨졌을 때만 Recoloring이나 Restructuring을 하므로 리밸런싱에 드는 시간이 더 적다.
B-Tree와의 비교
- 레드-블랙 트리: 메모리 안에서 삽입과 삭제가 빈번한 자료구조에 적합하다.
- B-Tree: 한 노드에 많은 키를 담아 트리의 높이가 매우 낮다. 디스크 접근 횟수를 줄일 수 있어 조회가 빠르며, DB 인덱스에 쓰인다.