읽기 전
- 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
- 개인적으로 배운 점을 정리한 글입니다.
- Python 구현 코드를 첨부한 포스팅이 별로 없어 넣어봤습니다.
Red-Black 트리란?
자가 균형 이진 탐색 트리의 일종으로 AVL 트리와 사용되는 용도가 조금 다르다 AVL 트리는 balance를 엄격히 유지하기에 조회 속도는 빠르나 삽입/삭제 시 balancing 과정으로 인해 속도가 지연된다. 따라서 조회가 빈번히 발생하는 DB에 사용되며 Red-Black Tree는 AVL 트리보다는 balance를 조금 느슨하게 유지하여 적절한 조회 속도를 가져가되 빠른 삽입/삭제를 지원한다. B-Tree, AVL Tree와 마찬가지로 BST의 고질적인 문제인 skewed tree 문제 해결이 가능하다.
레드 블랙 트리의 성질
- 노드의 색상은 Red 혹은 Black이다.
- 루트 노드의 색상은 무조건 Black이다.
- 모든 리프 노드의 색상은 Black이다.
- Red 노드의 자식은 모두 Black이다.
- Red 노드가 루트에서 리프까지의 경로에 연속으로 등장할 수 없음을 의미한다.
- 루트 노드에서 임의의 리프 노드에 이르는 경로에 존재하는 Black 노드의 수는 일정하다.
- Red 노드 + Black 노드의 수는 다를 수 있다.
- 5번 성질로 인해 최단, 최장 경로의 노드 수가 차이가 2배 이상 커지지 않는다.
- 레드-블랙 트리에서의 리프 노드 : 일반적으로 트리에서의 리프 노드는 가장 하단에 있는 값을 가진 노드라 부르지만 레드-블랙 트리는 가장 하단의 값을 가진 노드(보통 리프 노드라 부르는)의 자식 노드에 Null 값을 줘서 NIL Leaves나 null Leaves라고 부른다.
모든 마지막 노드의 양쪽 자식 노드는 NIL Leaf 노드이므로 개념적으로 모든 노드가 가지고 있지만 실제 구현 시 하나의 객체를 참조하게 하면 공간복잡도를 줄일 수 있다.
레드 블랙 트리의 높이
- 노드 x의 높이 $h(x)$는 자신부터 리프 노드까지의 가장 긴 경로에 있는 edge의 개수다.
- 레드-블랙 트리의 black height = bh는 루트 노드에서 리프 노드까지의 블랙 노드의 개수이고 모든 리프 노드 또한 블랙 노드이기에 카운트에 들어간다. 높이 h인 레드-블랙 트리의 블랙 높이는 $bh \ge \cfrac{h}{2}$를 만족한다.(레드-블랙 트리의 성질 조건 4)
- 루트 노드가 x인 서브트리의 노드의 수는 적어도 $2^{bh(x)} - 1$개를 갖는다.
- $h(x)=0$이면 x는 NIL 노드로 $2^0-1=0$으로 가정이 성립한다.
- $h(x) >0$이고 x는 두 개의 자식을 갖는다고 하자. x의 색상에 따라 x의 자식 노드는 $bh(x)$, $bh(x) - 1$의 높이를 갖는다. 최소한의 관점이므로 $bh(x) - 1$이라 하자. 그러면 적어도 x를 루트로 하는 서브 트리는 양쪽에 $2^{bh(x) - 1} - 1$개 노드를 갖는 트리가 되고 양 쪽 서브 트리와 x 노드를 포함하면 $2\cdot(2^{bh(x) - 1}-1) + 1 = 2^{bh(x)}- 1$가 된다.(귀납적 증명)
- n개의 노드를 갖는 레드-블랙 트리의 높이는 $h\le 2log_2{(n + 1)}$을 만족한다.
- $n \ge 2^{bh(x)} - 1 \ge 2^{h/2}-1$이므로 $2^{h/2} \le n + 1$이고 $\cfrac{h}{2}\le log_2{(n + 1)}$가 되어 $h\le 2log_2{(n + 1)}$이 된다.
레드 블랙 트리의 시간복잡도
모든 경우에 대해 최선/최악을 가리지 않고 $O(log\ n)$의 시간복잡도는 보여준다. 현존하는 BST 중 가장 안정적으로 여러 SDK나 라이브러리의 검색알고리즘에 쓰인다고 한다.
레드 블랙 트리의 검색(Search)
레드 블랙 트리도 이진 탐색 트리의 일종이기에 검색 연산은 현재 노드보다 크면 우측, 작으면 좌측으로 탐색하면 된다.
python 코드 - 검색파트
class Node:
def __init__(self, data):
self.data = data
self.parent = None
self.left = None
self.right = None
self.color = "Red" # Initial color is red
class RedBlackTree:
def __init__(self):
self.root = None
self.inserted_node = None
def find(self, data):
return self._find_data(self.root, data)
def _find_data(self, root, data):
if root is None or root.data == data:
return root
elif root.data >= data:
return self._find_data(root.left, data)
elif root.data < data:
return self._find_data(root.right, data)레드 블랙 트리의 삽입(Insert)
삽입 과정에서 노드 상태의 변화가 발생하면 경우에 따라 balancing 작업을 수행해야 한다. AVL 트리에서는 rotation만 사용했는데 레드 블랙 트리는 recoloring이 추가되어 recoloring이 불가할 경우 rotation을 구행한다.
- 삼촌 노드가 Red면 : recoloring 수행
- 삼촌 노드가 Black이면 : rotation 수행 후 recoloring 여부 결정
일반적인 BST 삽입처럼 노드를 삽입하되 색상은 Red로 한다.
만약 삽입한 노드가 루트 노드라면 Black으로 바꾼다.
삽입된 노드 x가 루트 노드가 아니라며 x의 부모가 Red인 경우
3.1 삼촌이 Red인 경우(이중 Red는 불가하므로 조부모 노드가 존재한다면 색상은 Black)
- 부모와 삼촌 노드의 색상을 Black으로 변경
- 조부모 노드의 색상은 Red로 변경
- x를 x의 조부모 노드로 치환하고 2, 3번 과정을 반복
3.2 삼촌이 Black인 경우
부모가 조부모의 왼쪽 자식이고 x가 부모의 왼쪽 자식일 때 - LL Case
부모가 조부모의 왼쪽 자식이고 x가 부모의 오른쪽 자식일 때 - LR Case
부모가 조부모의 오른쪽 자식이고 x가 부모의 오른쪽 자식일 때 - RR Case
부모가 조부모의 오른쪽 자식이고 x가 부모의 왼쪽 자식일 때 - RL Case
Python 코드 - 삽입 파트
def insert(self, data):
self.root = self._insert_node(self.root, data, None)
self._balancing(self.inserted_node)
return
def _insert_node(self, cur, data, parent):
if cur is None:
cur = Node(data)
cur.parent = parent
self.inserted_node = cur
else:
if data < cur.data:
cur.left = self._insert_node(cur.left, data, cur)
elif data > cur.data:
cur.right = self._insert_node(cur.right, data, cur)
return cur
def _balancing(self, node):
P = node.parent
if P is None: # if node is root node
node.color = "Black"
else: # if node isn't root node
if P.color == "Red": # if parent node is red
G = P.parent # must exist grandparent
U = None
if G.left == P:
U = G.right
elif G.right == P:
U = G.left
if U is not None and U.color == "Red":
# parent, uncle -> Black, grandparent -> Red
P.color, U.color = "Black", "Black"
G.color = "Red"
# rebalncing from grandparent
self._balancing(G)
else: # uncle is None or uncle.color is black
if P == G.left and P.left == node: # LL Case
G.color, P.color = P.color, G.color
self._right_rotate(G)
elif P == G.left and P.right == node: # LR Case
self._left_rotate(P)
G.color, node.color = node.color, G.color
self._right_rotate(G)
elif P == G.right and P.right == node: # RR Case
G.color, P.color = P.color, G.color
self._left_rotate(G)
elif P == G.right and P.left == node: # RL Case
self._right_rotate(P)
G.color, node.color = node.color, G.color
self._left_rotate(G)레드 블랙 트리에서의 삭제(Delete)
삽입 연산에서는 삼촌 노드의 색상에 따라 분기문이 나뉘었지만 삭제 연산에서는 형제 노드의 색상에 따라 나뉜다. 삽입 연산에서는 노드 삽입 시 연속된 Red 노드가 문제였으나 삭제 연산에서는 루트에서 리프 노드까지의 블랙 높이가 일정하지 않게 되어 문제가 된다. AVL 트리도 그렇고 레드 블랙 트리도 삭제 연산은 특히 복잡하다.
삭제될 노드 V이고 V의 자식 노드 C가 V를 대체할 노드라고 하자.
- 일반적인 BST에서의 삭제 연산처럼 접근하여 삭제될 노드를 가르키는 객체를 생성한다.
- 삭제될 노드의 자식이 없거나 1개면 문제가 되지 않지만 2개인 경우 successor 중 가장 작은 값(inorder)를 찾아서 값을 치환한 후 해당 successor가 노드를 삭제하면 전체 대소관계를 해치지 않고 삭제될 노드는 리프 노드이거나 자식 노드가 1개임을 보장할 수 있다.
python 코드 - 삭제 파트(삭제 노드 명시)
def delete(self, data):
node = self._get_delete_node(self.root, data)
if node is None:
return False
self._delete_node(node)
return True
def _get_delete_node(self, node, data):
if node.data > data:
return self._get_delete_node(node.left, data)
elif node.data < data:
return self._get_delete_node(node.right, data)
elif node.data == data:
# check left, right child
left = node.left
right = node.right
if left is not None and right is not None:
# delete node has both child
# swap value of minimum successor and delete node
min_successor = self._find_min_successor(node.right)
node.data, min_successor.data = min_successor.data, node.data
return min_successor
else:
return node만약 V나 C들 중 하나가 Red라면 V를 대체할 자식 노드 C의 색상을 Black으로 바꾸고 종료한다.
- 둘 다 Red인 경우는 이중 Red로 존재할 수 없어 생략
만약 V, C가 모두 Black인 경우 V를 대체할 C 노드를 "double black"으로 표기한다. 이후 double black을 single black으로 바꿔야 한다.
3.1 만약 V를 대체할 C 노드가 루트 노드라면 single black으로 바꾸고 종료한다.
- 전체 bh가 1 감소한 효과
def _delete_node(self, V): C, S = None, None P = V.parent if V.left is not None: C = V.left elif V.right is not None: C = V.right if P is None: self.root = None return elif V == P.left: S = P.right elif V == P.right: S = P.left if C is None: C = Node(None) # temporary Node C.parent = V C.color = "Black" if V.color == "Red" or C.color == "Red": # if V has child and V or C node color is red # make C color black and just delete V if P is None: self.root = V else: if C.data is not None: C.parent = P C.color = "Black" if P.left == V: P.left = C elif P.right == V: P.right = C elif C.data is None: if P.left == V: P.left = None elif P.right == V: P.right = None V = C elif V.color == "Black" and C.color == "Black": C.parent = P if V == P.left: if C.data is None: P.left = None else: P.left = C elif V == P.right: if C.data is None: P.right = None else: P.right = C V = C V.color = "BBlack" if P is None: V.color = "Black" self.root = V else: # if S and S's child are all black, # V's double black mark would be shifted to P # so need to make recursive function self._delete_balancing(V, P, S)3.2 C 노드가 루트 노드가 아닐 경우 기존 V의 형제 노드 S의 색상에 따라 분기문이 나뉜다.
a) S 노드 색상이 Black이고 S의 자식 노드 중 적어도 하나가 Red인 경우
S 노드에 대해 rotation 수행
S가 부모 노드의 좌측 자식이고 S의 좌측 자식 노드가 Red인 경우(Left Left Case) - right(P) rotation
C 노드의 bh가 1 감소했으므로 S의 bh를 감소시키도록 right rotation 수행, 자식노드 r은 Black으로 바꿔서 증가한 우측 bh에 맞춰준다.
S가 부모 노드의 좌측 자식이고 S의 우측 자식 노드가 Red인 경우(Left Right Case) - left(S), right(P) rotation
S 노드에 대해 left rotation 수행 후 S와 r 노드의 색상을 바꾼다. 이후 LL Case처럼 right rotation을 수행한 뒤 S의 색상을 Black으로 바꾼다.
S가 부모 노드의 우측 자식이고 S의 우측 자식 노드가 Red인 경우(Right Right Case) - left(P) rotation
LL 케이스를 좌우 반전한 경우다.
S가 부모 노드의 우측 자식이고 S의 좌측 자식 노드가 Red인 경우(Right Left Case) - right(S), left(P) rotation
LR 케이스를 좌우 반전한 경우다.
b) S 노드의 색상이 Black이고 S의 자식 노드들도 모두 Black인 경우 재귀적으로 recoloring을 수행한다.
- C의 double black을 빼앗아 부모 노드 P에게 주고 S 노드를 Red로 바꾼다. - C 노드의 bh가 1 감소하였으므로 S도 Red로 만들어 bh 균형 유지
- P 노드가 Red였다면 red + double black = single black이 되어 P 노드를 Black으로 바꾸고 종료한다.
- P 노드가 Black이었다면 P 노드가 double black이 되어 처리루틴 3.2로 회귀한다.
c) S 노드의 색상이 Red일 경우
S가 부모 노드 P의 왼쪽 노드일 경우(Left Case) P를 오른족으로 내리는 right rotation 수행한 후 P와 S의 색상 swap
S가 부모 노드 P의 오른쪽 노드일 경우(Right Case) P를 왼쪽으로 내리는 left rotation 수행한 후 P와 S의 색상 swap
rotation과 recoloring을 수행하면 double black 노드인 C 노드에 대해 다시 새로운 현재 상황이 주어지고 처리루틴 3.2로 회귀한다.
```python
def _delete_balancing(self, V, P, S):
S_l, S_r = S.left, S.right
if S_l is None:
S_l = Node(None) # temporary Node
S_l.parent = S
S_l.color = "Black"
if S_r is None:
S_r = Node(None) # temporary Node
S_r.parent = S
S_r.color = "Black"
if S.color == "Black" and (S_l.color == "Red" or S_r.color == "Red"):
if S == P.left and S_l.color == "Red":
S_l.color = "Black"
self._right_rotate(P)
elif S == P.left and S_r.color == "Red":
S_r.color = "Black"
self._left_rotate(S)
self._right_rotate(P)
elif S == P.right and S_r.color == "Red":
S_r.color = "Black"
self._left_rotate(P)
elif S == P.right and S_l.color == "Red":
S_l.color = "Black"
self._right_rotate(S)
self._left_rotate(P)
elif S.color == "Black" and S_l.color == S_r.color and S_l.color == "Black":
V.color = "Black"
if P.color == "Red":
P.color = "Black"
return
else:
# if S and all S's child ar black
# give V's double black to P
# if P is black, balancing routine for V would be shifted to P
P.color = "BBlack"
S.color = "Red"
PP = P.parent
if PP and P == PP.left:
S = PP.right
elif PP and P == PP.right:
S = PP.left
if PP is None:
S = None
self._delete_balancing(P, PP, S)
elif S.color == "Red":
S.color, P.color = P.color, S.color
if S == P.left:
self._right_rotate(P)
elif S == P.right:
self._left_rotate(P)
self._delete_balancing(V, P, S)
def _find_min_successor(self, node):
if node.left is None:
return node
else:
return self._find_min_successor(node.left)
### python 전체 코드
```python
class Node:
def __init__(self, data):
self.data = data
self.parent = None
self.left = None
self.right = None
self.color = "Red" # Initial color is red
class RedBlackTree:
def __init__(self):
self.root = None
self.inserted_node = None
def find(self, data):
return self._find_data(self.root, data)
def _find_data(self, root, data):
if root is None or root.data == data:
return root
elif root.data >= data:
return self._find_data(root.left, data)
elif root.data < data:
return self._find_data(root.right, data)
def insert(self, data):
self.root = self._insert_node(self.root, data, None)
self._balancing(self.inserted_node)
return
def _insert_node(self, cur, data, parent):
if cur is None:
cur = Node(data)
cur.parent = parent
self.inserted_node = cur
else:
if data < cur.data:
cur.left = self._insert_node(cur.left, data, cur)
elif data > cur.data:
cur.right = self._insert_node(cur.right, data, cur)
return cur
def _balancing(self, node):
P = node.parent
if P is None: # if node is root node
node.color = "Black"
else: # if node isn't root node
if P.color == "Red": # if parent node is red
G = P.parent # must exist grandparent
U = None
if G.left == P:
U = G.right
elif G.right == P:
U = G.left
if U is not None and U.color == "Red":
# parent, uncle -> Black, grandparent -> Red
P.color, U.color = "Black", "Black"
G.color = "Red"
# rebalncing from grandparent
self._balancing(G)
else: # uncle is None or uncle.color is black
if P == G.left and P.left == node: # LL Case
G.color, P.color = P.color, G.color
self._right_rotate(G)
elif P == G.left and P.right == node: # LR Case
self._left_rotate(P)
G.color, node.color = node.color, G.color
self._right_rotate(G)
elif P == G.right and P.right == node: # RR Case
G.color, P.color = P.color, G.color
self._left_rotate(G)
elif P == G.right and P.left == node: # RL Case
self._right_rotate(P)
G.color, node.color = node.color, G.color
self._left_rotate(G)
def delete(self, data):
node = self._get_delete_node(self.root, data)
if node is None:
return False
self._delete_node(node)
return True
def _get_delete_node(self, node, data):
if node.data > data:
return self._get_delete_node(node.left, data)
elif node.data < data:
return self._get_delete_node(node.right, data)
elif node.data == data:
# check left, right child
left = node.left
right = node.right
if left is not None and right is not None:
# delete node has both child
# swap value of minimum successor and delete node
min_successor = self._find_min_successor(node.right)
node.data, min_successor.data = min_successor.data, node.data
return min_successor
else:
return node
def _delete_node(self, V):
C, S = None, None
P = V.parent
if V.left is not None:
C = V.left
elif V.right is not None:
C = V.right
if P is None:
self.root = None
return
elif V == P.left:
S = P.right
elif V == P.right:
S = P.left
if C is None:
C = Node(None) # temporary Node
C.parent = V
C.color = "Black"
if V.color == "Red" or C.color == "Red":
# if V has child and V or C node color is red
# make C color black and just delete V
if P is None:
self.root = V
else:
if C.data is not None:
C.parent = P
C.color = "Black"
if P.left == V:
P.left = C
elif P.right == V:
P.right = C
elif C.data is None:
if P.left == V:
P.left = None
elif P.right == V:
P.right = None
V = C
elif V.color == "Black" and C.color == "Black":
C.parent = P
if V == P.left:
if C.data is None:
P.left = None
else:
P.left = C
elif V == P.right:
if C.data is None:
P.right = None
else:
P.right = C
V = C
V.color = "BBlack"
if P is None:
V.color = "Black"
self.root = V
else:
# if S and S's child are all black,
# V's double black mark would be shifted to P
# so need to make recursive function
self._delete_balancing(V, P, S)
def _delete_balancing(self, V, P, S):
S_l, S_r = S.left, S.right
if S_l is None:
S_l = Node(None) # temporary Node
S_l.parent = S
S_l.color = "Black"
if S_r is None:
S_r = Node(None) # temporary Node
S_r.parent = S
S_r.color = "Black"
if S.color == "Black" and (S_l.color == "Red" or S_r.color == "Red"):
if S == P.left and S_l.color == "Red":
S_l.color = "Black"
self._right_rotate(P)
elif S == P.left and S_r.color == "Red":
S_r.color = "Black"
self._left_rotate(S)
self._right_rotate(P)
elif S == P.right and S_r.color == "Red":
S_r.color = "Black"
self._left_rotate(P)
elif S == P.right and S_l.color == "Red":
S_l.color = "Black"
self._right_rotate(S)
self._left_rotate(P)
elif S.color == "Black" and S_l.color == S_r.color and S_l.color == "Black":
V.color = "Black"
if P.color == "Red":
P.color = "Black"
return
else:
# if S and all S's child ar black
# give V's double black to P
# if P is black, balancing routine for V would be shifted to P
P.color = "BBlack"
S.color = "Red"
PP = P.parent
if PP and P == PP.left:
S = PP.right
elif PP and P == PP.right:
S = PP.left
if PP is None:
S = None
self._delete_balancing(P, PP, S)
elif S.color == "Red":
S.color, P.color = P.color, S.color
if S == P.left:
self._right_rotate(P)
elif S == P.right:
self._left_rotate(P)
self._delete_balancing(V, P, S)
def _find_min_successor(self, node):
if node.left is None:
return node
else:
return self._find_min_successor(node.left)
def _left_rotate(self, node):
c = node.right
p = node.parent
if c.left is not None:
c.left.parent = node
node.right = c.left
node.parent = c
c.left = node
c.parent = p
if p is None:
self.root = c
elif p is not None:
if p.left == node:
p.left = c
elif p.right == node:
p.right = c
def _right_rotate(self, node):
c = node.left
p = node.parent
if c.right is not None:
c.right.parent = node
node.left = c.right
node.parent = c
c.right = node
c.parent = p
if p is None:
self.root = c
elif p is not None:
if p.left == node:
p.left = c
elif p.right == node:
p.right = c
def check(node):
if node.left is not None:
check(node.left)
if node.parent != None:
print(
f'key: {node.data}, parent: {node.parent.data}, color: {node.color}')
else:
print(f'key: {node.data}, root: {node.parent}, color: {node.color}')
if node.right is not None:
check(node.right)
rbt = RedBlackTree()
a = [2, 1, 8, 9, 7, 3, 6, 4, 5]
for x in a:
rbt.insert(x)
check(rbt.root)
print()
rbt.delete(4)
check(rbt.root)
'Algorithms > Data Structure' 카테고리의 다른 글
| B+트리, B*트리(B+Tree, B*Tree) (5) | 2021.08.31 |
|---|---|
| B-트리(B-Tree) (0) | 2021.08.31 |
| 세그먼트 트리 비재귀 구현 (0) | 2021.08.16 |
| 세그먼트 트리(Segment Tree) (0) | 2021.08.14 |
| 최소 신장 트리(Minimum Spanning Tree) (0) | 2021.08.02 |