레드-블랙 트리 (red-black tree)#
Red-black tree는 자체 균형 이진 검색 트리(self-balancing binary search tree)의 한 종류로, 컴퓨터 과학에서 정렬된 정보의 빠른 저장과 검색을 위해 사용되는 데이터 구조이다. 데이터베이스와 파일 시스템에서 널리 사용된다.
Red-black tree는 각 노드에 추가적인 색상 속성(빨간색 또는 검은색)을 가진 자체 균형 이진 검색 트리로, 트리의 균형을 유지하여 효율적인 검색, 삽입, 삭제 연산을 보장한다.
https://www.geeksforgeeks.org/introduction-to-red-black-tree/
- 모든 노드는 빨간색 또는 검은색이다.
- 루트 노드는 항상 검은색이다.
- 모든 리프 노드(NIL 노드)는 검은색이다.
- 빨간색 노드의 자식은 항상 검은색이다 (연속된 빨간색 노드는 없음).
- 모든 경로에서 검은색 노드의 수는 동일하다.
- 삽입, 삭제, 검색 연산의 시간 복잡도가 O(log n)으로 보장된다.
- 자체 균형 기능으로 효율적인 성능을 유지한다.
- AVL 트리에 비해 삽입과 삭제가 더 빠르다.
- 데이터베이스 인덱싱
- 파일 시스템 구현
- 맵(Map)과 셋(Set) 자료구조 구현
구성 요소#
- 노드: 값, 색상, 왼쪽 자식, 오른쪽 자식, 부모 노드 참조를 포함한다.
- 루트: 트리의 최상위 노드이다.
- NIL 노드: 리프 노드로 사용되는 특별한 검은색 노드이다.
구현 방식#
Red-black tree는 일반적으로 다음과 같은 구조로 구현된다:
1
2
3
4
5
6
7
| class Node:
def __init__(self, value, color='red'):
self.value = value
self.color = color
self.left = None
self.right = None
self.parent = None
|
주요 연산은 삽입, 삭제, 검색이며, 각 연산 후 트리의 속성을 유지하기 위해 회전(rotation)과 색상 변경이 수행된다.
동작 원리#
- 검색: 일반적인 이진 검색 트리와 동일한 방식으로 수행된다.
- 삽입:
- 일반적인 이진 탐색 트리처럼 새로운 노드를 삽입한다.
- 새로운 노드를 빨간색으로 칠한다.
- Red-Black 속성이 위반되었다면 다음 두 가지 작업으로 속성을 복구한다:
- Recoloring: 노드들의 색상을 변경
- Rotation: 트리의 구조를 변경 (Left rotation 또는 Right rotation)
- 삭제:
- 일반적인 이진 탐색 트리처럼 노드를 삭제한다.
- 삭제된 노드가 검은색이었다면 Black 높이가 변경되므로 이를 복구하기 위한 재조정이 필요하다.
- Double Black 문제를 해결하기 위해 여러 가지 경우에 대한 처리가 필요하다.
예시 코드 (Python)#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| class RedBlackTree:
def __init__(self):
self.TNULL = Node(0)
self.TNULL.color = 0 # 검은색
self.TNULL.left = None
self.TNULL.right = None
self.root = self.TNULL
def insert(self, key):
node = Node(key)
node.parent = None
node.item = key
node.left = self.TNULL
node.right = self.TNULL
node.color = 1 # 빨간색
y = None
x = self.root
while x != self.TNULL:
y = x
if node.item < x.item:
x = x.left
else:
x = x.right
node.parent = y
if y == None:
self.root = node
elif node.item < y.item:
y.left = node
else:
y.right = node
if node.parent == None:
node.color = 0
return
if node.parent.parent == None:
return
self.fix_insert(node)
def fix_insert(self, k):
while k.parent.color == 1:
if k.parent == k.parent.parent.right:
u = k.parent.parent.left
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.left:
k = k.parent
self.right_rotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.left_rotate(k.parent.parent)
else:
u = k.parent.parent.right
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.right:
k = k.parent
self.left_rotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.right_rotate(k.parent.parent)
if k == self.root:
break
self.root.color = 0
def left_rotate(self, x):
y = x.right
x.right = y.left
if y.left != self.TNULL:
y.left.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def right_rotate(self, x):
y = x.left
x.left = y.right
if y.right != self.TNULL:
y.right.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
|
이 코드는 Red-black tree의 기본 구조와 삽입 연산을 구현한 것.
실제 사용을 위해서는 삭제, 검색 등의 추가적인 메서드가 필요하다.
참고 및 출처#