공부기록
Red Black Trees 본문
red-black tree?
가장 유명하고 많이 사용되는 균형이진 트리이다. 즉 모든 연산의 시간복잡도가 _O(log N)_임을 보장한다.
노드가 red, black 색상을 가지며 아무것도 없는 nil을 leaf 노드라고 생각한다.
red-black tree는 다음 5가지 조건을 만족해야 한다.
- 모든 노드는 red, black의 색을 가진다.
- root 노드는 black이다.
- leaf 노드는 black이어야 한다.
- red 노드는 두 개의 자식을 가지며, red 노드의 child 노드는 색이 모두 black이어야 한다. black 노드의 자식은 어떠한 색을 가지든 상관이 없다.
- *tree의 전체 depth가 log N 이기 위해서, 각 노드에서 leaf 노드로 가는 경로들 중에 있는 블랙노드의 개수는 항상 같아야한다. *
다음 조건을 만족할 때 트리의 높이는 어느 경로이든 O(log N) 임을 보장하게 된다.
실제로 그런지 증명을 해보자.
탐색시간 O(log N) 의 증명
v를 전체트리, V를 전체 트리의 루트노드 라고 하자 , H(v) = v의 높이, bh(v) = V에서 leaf node로 가는데 있는, V를 제외한 black node의 개수라고 하자.
먼저 다음과 같은 사실 1, 'v의 subtree의 내부노드 개수는 최소 2^(bh(v)) - 1개가 존재한다.' 는 사실을 증명한다.
이에 대한 증명은 bh(v) 에 대한 귀납법으로 증명한다.
basecase는 root 노드가 nil인 경우이다. 이때 h(v) = 0 이고 bh(v) = 0 이다. 이때 v의 내부노드 갯수는 |v| >=2^(bh(v)) - 1 = 0 이므로 basecase가 성립한다.
다음의 가정을 증명한다.
h(v) <= k 에 대해서 |v| >= 2^(bh(v)) - 1 가 성립한다고 가정할 때, h(v) = k+1 일 때 |v의 서브트리| >= 2^(bh(v)) - 1 가 됨을 증명한다.
여기서, v의 left subtree w, right subtree z를 정의하자. v와 z의 height는 k보다 작거나 같다. 따라서 노드의 개수는 각각 다음과 같다.
|w| >= 2^(bh(w)) - 1
|z| >= 2^(bh(z)) - 1
그렇다면 노드 V를 합한 전체 노드의 개수는 2^(bh(w)) - 1 + 2^(bh(z)) - 1 + 1이 된다.
이때 bh(w), bh(z) 는 bh(v)이거나, bh(v)-1 이다. 즉, bh(w), bh(z) >= bh(v) - 1 이다.
구체적인 예를 들어보자.
w 트리의 루트노드 W가 red면 bh(w) == bh(v)이고, black이면 bh(w) == bh(v) - 1 이다. 이는 z의 경우도 마찬가지 이다.
그러면 |v| >= 2^(bh(v) - 1) - 1 + 2^(bh(v) - 1) - 1 + 1 == 2^(bh(v)) - 1 가 되므로 사실 1이 증명이 된다.
그리고 사실 2 '트리의 최대 높이를 h라 고 할 때, 한 경로에 있는 black 노드의 개수는 h/2개 이상이다.' 를 증명한다.
사실 이 것은 red-black 트리의 4번 조건에 의해 만족하게 된다.
트리에 있는 전체 노드의 개수를 N개 라고 하자. 전체 트리를 r이라고 할 때 다음과 같은 식이 성립한다.
N >= 2^(bh(r)) -1 >= 2^(h/2) - 1
즉 N >= 2^(h/2) - 1 이 된다. 이 때 다음과 같은 식을 유도할 수 있다.
N >= 2^(h/2) - 1
2^(h/2) <= N+1
h <= 2 log (n+1)
따라서 h = O(log N) 이 증명이 되고 성능이 보장이 된다.
red-black 트리는 정보를 정보를 참조하는 것은 기본 BST와 같다. 다만 데이터의 insertion, deletion이 red-black 트리의 조건을 만족하기 위해 굉장히 복잡하게 설계되어 있다.
red-black 트리의 insertion, deletion에 대해서 알아보자.
Rotation
red-black 트리는 변경연산을 하면서 자신의 특성을 유지하기 위해 rotation 연산을 한다. rotation 연산을 하면서도 BST을 성질을 지키면서, red-black 트리의 조건을 만족시키기 위한 연산을 하게 된다.
다음은 Left-Rotation 연산이다. Right이 코드를 대칭으로 바꾸기만 하면 된다. 이 연산의 복잡도는 O(1) 이다.
# T는 전체 트리이고, x는 회전하고자 하는 노드이다.
def left_rotate(T, x)
y = x.right
x.right = y.left
# y의 서브트리를 x의 오른쪽 서브트리로 바꾼다.
if y.left != None:
y.left.p = x
y.p = x.p
# x의 부모를 y의 부모로 삼는다.
if x.p == None:
T.root = y
elif x == x.p.left:
x.p.left = y
else :
x.p.right = y
x.left = x
# x를 y의 왼쪽에 붙인다.
x.p = yInsertion
노드 추가는 O(lg N)의 시간에 가능하다. 아이디어는 다음과 같다. 일반적인 BST 처럼, 추가할 수 있는 nil 자리에 갑값을 추가한다. 단 노드의 색은 항상 RED이다.
이렇게 추가한 뒤에 RB 트리의 조건을 위배하는 경우가 생길 수 있다. 이를 고치기 위한 FIXUP()를 호출하여 올바른 트리를 만들게 된다. fixup()은 recolor, rotation을 통해 RB 트리의 조건을 만족시키도록 트리를 수정한다.
코드는 다음과 같다.
# T는 트리 전체이고, z는 현재 추가된 노드이다.
def rb_insert_fixup(T, z):
while z.p.color == RED:
if z.p == z.p.p.left:
y = z.p.p.right
if y.color == RED:
#case1
z.p.color = BLACK
y.color = BLACK
z.p.p.color = RED
z = z.p.p
#case1 end
#case2
elif z == z.p.right:
z = z.p
left_rotate(T, z)
#case2 end
#case3
z.p.color = BLACK
z.p.p.color = RED
right_rotate(T,z.p.p)
#case3 end
else: (대칭으로 구현)
T.root.color = BLACK 새로운 RED 색상의 노드가 트리에 추가되었을 때, RED가 RED를 자식으로 가지는 상황이 연출될 때 fixup()가 항상 실행되게 된다.
fixup()에 의해 수정되어야 하는 케이스들은 다음과 같다.
Case 1 : z의 삼촌 y가 RED 이다.
먼저 삼촌 Uncle은 부모의 sibling 노드를 말한다. 이 경우 recolor만 수행한다. parent, uncle을 black으로 색상을 바꾸고 grandparent 노드는 red로 색상을 바꾼다. 그리고 z를 grandparent로 바꾸어 유효할 때 까지 계속해서 작업을 수행한다.
Case 2 : z의 uncle이 검은색이고 z가 오른쪽 아이인 경우
이 경우에는 z, parent, grandParent가 triangle을 형성하는 형태이다. 이때는 parent를 z로 삼고 left rotation을 수행한다. case3을 수행하기 좋은 형태로 바꾼다.
Case 3 : z의 uncle이 검은색이고 z가 왼쪽 아이인 경우
z, parent, grandParent가 linear한 상태이다. 이때는 parent를 black, grandParent를 red로 색상을 바꾸고 grandParent를 right rotate한다.
Deletion
red-black 트리의 deletion도 insertion과 흡사하다. BST와 같은 방식으로 노드를 삭제하고, RB Tree의 조건을 만족하도록 트리를 수정하는 것이다.
아래는 먼저 트리에서 노드를 삭제하는데 필요한 함수들이다.
def rb_transplant(T, u, v):
if u.p == None:
T.root = v
elif u == u.p.left:
u.p.left = v
else:
u.p.right = v
v.p = u.p 위의 함수는 T의 subtree u를 v로 바꾸는 함수이다.
def rb_delete(T, z):
y = z
y-original-color = y.color
if z.left == None:
x = z.right
rb_transplant(T, z, z.right)
elif z.right == None:
x = z.left
rb_transplant(T, z, z.left)
else:
y = tree_minimum(z.right)
x = y.right
if y.p == z:
x.p = y
else:
rb_transplant(T, y, y.right)
y.right= z.right
y.right.p = y
rb_transplant(T,z,y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK:
rb_delete_fixup(T,x)위의 함수는 노드를 제거하고, fixup()을 호출한다.
왜 삭제된 노드가 Black일때만 fixup()을 호출할까? 이유는 다음과 같다.
- red가 삭제된다면, black-height는 삭제되지 않았으니 상관이 없다.
- red가 삭제되었다면, black과 black이 인접해도 문제가 아니다. 하지만 black이 삭제되면 red끼리 인접할 수 있기 때문에 문제가 될 수 있다.
- 삭제된 노드가 red라면 루트가 아니고, 이 때문에
fixup()이 필요가 없다.
다음은 delete_fixup() 이다.
def rb_delete_fixup(T, x):
while x != T.root and x.color == BLACK:
if x == x.p.left:
w = x.p.right
# case1 start
if w.color == RED:
w.color = BLACK
x.p.color = RED
left_rotate(T, x.p)
w = x.p.right
# case1 end
# case2 start
if w.left.color == BLACK and w.right.color == BLACK:
w.color = RED
x = x.p
# case2 end
# case3 start
elif w.right.color == BLACK:
w.left.color = BLACK
w.color = RED
right_rotate(T,x)
w = x.p.right
# case3 end
# case4 start
w.color = x.p.color
x.p.color = BLACK
w.right.color = BLACK
left_rotate(T, x.p)
x = T.root
# case4 end
else:
(대칭으로 구현)Case 1 : x의 형제, w가 red 인 경우
w를 black으로 칠하고, x의 parent를 red로 칠한다.
그리고 x의 parent를 left rotate하고 w를 x의 parent의 오른쪽에 붙인다.
Case 2 : x의 형제 w가 black이고 w의 자식들이 모두 black인 경우
w를 red로 칠하고, x는 x의 parent를 가리키도록 한다. 그리고 다시 수행한다.
Case3 : x의 형제 w가 black이고 w의 왼쪽 자식이 red, 오른쪽 자식이 black인 경우
w의 왼쪽자식을 black으로 칠하고, w는 red로 칠한다. w를 right rotate하고, w를 x의 부모의 오른쪽 자식으로 바꾼다. 그리고 Case 4를 이어서 수행한다.
Case4 : x의 형제 w가 black이고, w의 오른쪽 자식이 red일 때
w의 색을 x의 부모의 색으로 칠하고, x의 부모의 색을 black으로 칠한다. 또한, w의 오른쪽 자식의 색을 black으로 칠한다.
x의 부모를 left rotate하고, x는 트리 T의 root가 된다. 이는 loop를 바로 종료시키기 위함이다.
출처
Introduction to algorithms 3rd Edition - 13 Red-Black Trees
'CS > Data Structure' 카테고리의 다른 글
| Linked List (0) | 2021.05.31 |
|---|---|
| Sorting (0) | 2021.05.30 |
| Queue (0) | 2021.05.29 |
| Linked List (0) | 2021.05.29 |
| Stack (0) | 2021.05.29 |