1. RedBlackTree란?
- 각 노드는 red or black 노드이다.
- 루트 노드는 black 노드이다.
- 모든 리프노드(실제 내부노드가 아니라 nil 노드)는 black 노드이다.
- red노드의 자식은 black 이다. 즉, red 노드가 연속해서 나올 수 없다.
- 모든 노드에 대해 그 노드에서 리프노드 까지의 black 노드의 개수(black height)는 같다.
2. RedBlackTree가 필요한 이유
- RedBlackTree는 Binary Search tree 의 각 리프노드의 레벨이 심하게 차이나는 것을 방지하기 위한 자료구조이다.
- 배열과 같은 선형자료구조에서 탐색, 삭제, 삽입등이 o(n)의 시간을 가지는 것과 다르게 데이터를 정렬된 형태로 유지하면서 이중트리 형태로 데이터를 저장하면 탐색, 삭제, 삽입등에서 o(logn)의 시간 복잡도를 가질 수 있다.
- 하지만, 이러한 이중 탐색 트리는 leaf노드의 레벨이 차이가 날 경우 시간복잡도가 o(n)의 근접할 수 있기 때문에 각 leaf 노드의 레벨을 균일하게 맞춰 주어야한다.
- 이를 위한 자료구조로 AVL tree, RedBlackTree, 많은 관계형 데이터베이스 인덱스에서 사용하는 B+트리등이 있다.
- 프로그래밍 언어에서 Set, Map등의 자료구조는 Hashtable로 구현되거나 RedBlackTree로 구현된다.
3. RedBlackTree vs AVL Tree
- AVL 트리는 리프노드 레벨을 좀더 엄격하게 맞추기 때문에 탐색 속도가 더 빠르다.
- 삽입, 삭제시 RedBlackTree가 구조를 다시 맞추어줄때 더 적은 연산을 하기 때문에 더 빠르다.
- 각 노드의 정보가 AVL tree에서 더 많기 때문에 메모리 사용면에서 RedBlackTree가 더 효율적이다.
- 따라서 프로그래밍 언어의 자료구조에서는 RedBlackTree를 주로 사용하고, 탐색 속도가 중요하고 저장용량이 충분한 DataBase에서는 AVL Tree를 사용하는 경우가 많다.
4. n 개의 내부 노드를 가지는 레드 블랙 트리의 높이는 2log(2)(n+1)이하이다.
블랙노드 높이: 내 자식 노드(nil 노드 포함)중 블랙노드인 노드들의 개수.
- 증명
- 블랙노드 높이는 전체 노드 높이의 절반보다 항상 크거나 같다.
bh >= h/2
->레드 노드가 연속할 수 없기 때문에 블랙노드가 항상더 많거나 같기때문에 당연. - 어떤 노드의 블랙노드 높이가 bh일때 양 서브트리는 2^bh -1최소 만큼의 내부노드를 가진다.
->블랙 노드만 있는 경우가 최소. - 1, 2를 조합하면 n 개의 내부 노드를 가지는 레드 블랙 트리의 높이는 2log(2)(n+1)이하이다.
->n >= 2^bh - 1 >= 2^(h/2) - 1
5. Red Black Tree 연산 구현
- insert, delete 후 redBlackTree구조를 유지하는것이 핵심이다.
1)left-rotate vs right-rotate
- o(1)의 시간복잡도, 이진탐색 트리의 구조를 유지하는 연산
- insert, delete 후 깨어진 redblacktree를 복구하기 위해 사용.
2)insert
- insert시 항상 red node 입력
- 두가지 문제상황
- 입력 노드가 루트노드 일때-> 간단하게 처리가능
- 부모노드가 레드 노드일때(red-red violation) -> 두 연속되는 레드를 루트노드쪽으로 옮긴다. 이 경우 3가지 케이스가 존재한다.
(1) case1: 삼촌 노드가 레드노드인 경우
-
부모와 삼촌노드를 블랙으로, 할아버지를 레드로(부모가 레드였기 때문에 할아버지는 무조건 블랙)
-
red-red violation이 두 노드위로 옮겨갔다
(2) case2:삼촌 노드가 블랙노드이면서, 추가노드가 오른쪽 자식
- 추가노드의 부모에 대해서 left-rotation하면 case3가 됨.
- left-rotation을 하고나서도 Red Black Tree가 유지됨.
(3) case3:삼촌 노드가 블랙노드이면서, 추가노드가 왼쪽 자식
- 부모를 블랙, 할아버지를 red로 바꾸고, 할아버지노드에 대해 right-rotation한다.
알파, 베타, 감마, 델타는 같은 black height를 가진다.
- red-red violation 한번에 해결됨
iterator insert(iterator position, const value_type& value){
node_pointer new_node = search(value,_root);
if (new_node)
return (iterator(new_node));
new_node = _node_alloc.allocate(1);
_node_alloc.construct(new_node, Node<value_type>(create_value(value)));
new_node->left = _nil;
new_node->right = _nil;
if (position == begin()){
if (position != end() && _compare(value, *position))
_insert_into_tree(new_node, tree_min(_root));
else
_insert_into_tree(new_node, _root);
}
else if (position == end()){
if (position != begin() && _compare(*(--position), value))
_insert_into_tree(new_node, _header->parent);
else
_insert_into_tree(new_node, _root);
}
else
_insert_into_tree(new_node, _root);
_insert_fixup(new_node);
_size++;
node_pointer max_of_tree = tree_max(_root);
max_of_tree->right = _header;
_header->parent = max_of_tree;
return (iterator(new_node));
}
void _insert_fixup(node_pointer node){
if (node != _root && node->parent != _root){
while (node != _root && !node->parent->is_black){
if (node->parent == node->parent->parent->left){
node_pointer uncle = node->parent->parent->right;
if (!uncle->is_black){
node->parent->is_black = true;
uncle->is_black = true;
node->parent->parent->is_black = false;
node = node->parent->parent;
}
else {
if (node == node->parent->right){
node = node->parent;
_rotate_left(node);
}
node->parent->is_black = true;
node->parent->parent->is_black = false;
_rotate_right(node->parent->parent);
}
}
else{
node_pointer uncle = node->parent->parent->left;
if (!uncle->is_black){
node->parent->is_black = true;
uncle->is_black = true;
node->parent->parent->is_black = false;
node = node->parent->parent;
}
else{
if (node == node->parent->left){
node = node->parent;
_rotate_right(node);
}
node->parent->is_black = true;
node->parent->parent->is_black = false;
_rotate_left(node->parent->parent);
}
}
}
}
_root->is_black = true;
}
3)delete
y 가 삭제할 노드, x가 자식 노드(없거나, 하나밖에 없음)
(1) 삭제할 노드가 red인 경우 binary tree의 일반적인 삭제와 동일하게 문제없이 삭제 가능
- 삭제할 노드의 자식 노드가 없는 경우
->그냥 삭제 - 삭제할 노드의 자식 노드가 한명 있는 경우
->삭제하고 삭제노드의 부모노드에 자식 노드 연결 - 삭제할 노드의 자식 노드가 두명 있는 경우
->오른쪽자식 중에서 가장 작은 값을 삭제한다.
->오른쪽자식 중에서 가장 작은 값을 가진 노드를 삭제 하는데 자식이 하나밖에 없으므로 (삭제할 노드의 자식 노드가 한명 있는 경우)의 경우처럼 해결한다.
(2) 삭제할 노드가 black인 경우 redblack tree delete fix 필요
- y가 루트 노드이고 올라오는 x가 레드 인경우
->x를 블랙으로 바꾸면 해결됨. - 삭제할 노드가 블랙이면 서브트리 모든 노드들의 black height가 1씩 감소함.
->삭제노드의 하나밖에 없는 자식(x)에 black 성질을 하나 더 추가한다.
->double-black or red-black이 되는데 red-black의 경우 black으로 만들어준다.
->double-black의 경우 black 을 부모 쪽으로 올려주는 로직을 수행한다.
y를 제거하고 x가 double-black 인 상황은 다시 4가지 상황으로 나뉜다.
단, 형제 노드w는 nil노드가 될 수 없다.
case1:w가 red인 경우
- x의 부모에 대해서 left-rotation 하면 case 2, 3, 4중 하나가 된다.
case2:w가 black이고, w 자식도 모두 블랙 노드
- x와 w가 black을 부모에게 넘겨주고 w는 red로 x는 black으로. 부모는 extra black을 넘겨 받게 됨.
case3:w가 black이고, w 왼쪽 자식이 레드 노드, 오른쪽 자식은 블랙 노드
- w에 대해서 right-rotation하고 black height를 맞춰 주기위해 w와 w 왼쪽 자식이었던 노드들의 색을 바꾼다. case 4 가 된다.
case4:w가 black이고, w 오른쪽 자식이 레드노드, 왼쪽 자식은 unknown
- x 부모에 대해서 left-rotation적용하고 w를 red노드로, 원래 x의 부모에는 x의 extra black 을 넘겨준다.->black height가 모든 경로에 대해서 이전과 동일하게 유지된다.
다음과 같이 case들이 진행 된다.
void erase(iterator pos){
node_pointer y = pos.node(), x, for_free = y;
bool y_original_is_black = y->is_black;
if (is_nil(y->left)){
x = y->right;
transplant(y, y->right);
}
else if (is_nil(y->right)){
x = y->left;
transplant(y, y->left);
}
else {
node_pointer z = y;
y = tree_min(z->right);
y_original_is_black = y->is_black;
x = y->right;
if (y->parent != z){
transplant(y, y->right);
y->right = z->right;
z->right->parent = y;
}
transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->is_black = z->is_black;
}
free_node(for_free);
if (y_original_is_black)
erase_fixup(x);
_size--;
_nil->parent = NULL;
if (_size == 0)
_root = _header;
else{
if (_size != 1)
x = tree_max(_root);
else
x = _root;
x->right = _header;
_header->parent = x;
}
}
void erase_fixup(node_pointer x){
node_pointer brother;
while (x != _root && x->is_black){
if (x == x->parent->left){
brother = x->parent->right;
//case 1
if (!brother->is_black){
brother->is_black = true;
x->parent->is_black = false;
_rotate_left(x->parent);
brother = x->parent->right;
}
//case 2
if (brother->left->is_black && brother->right->is_black){
brother->is_black = false;
x = x->parent;
}
else{
//case 3
if (brother->right->is_black){
brother->left->is_black = true;
brother->is_black = false;
_rotate_right(brother);
brother = x->parent->right;
}
//case 4
brother->is_black = x->parent->is_black;
x->parent->is_black = true;
brother->right->is_black = true;
_rotate_left(x->parent);
x = _root;
}
}
else{
brother = x->parent->left;
//case 1
if (!brother->is_black){
brother->is_black = true;
x->parent->is_black = false;
_rotate_right(x->parent);
brother = x->parent->left;
}
//case 2
if (brother->right->is_black && brother->left->is_black){
brother->is_black = false;
x = x->parent;
}
else{
//case 3
if (brother->left->is_black){
brother->right->is_black = true;
brother->is_black = false;
_rotate_left(brother);
brother = x->parent->left;
}
//case 4
brother->is_black = x->parent->is_black;
x->parent->is_black = true;
brother->left->is_black = true;
_rotate_right(x->parent);
x = _root;
}
}
}
}
6. RedBlackTree 정리
- RedBlackTree는 BinarySearchTree의 시간복잡도를 o(logn)으로 확정 시켜주기위한 자료구조이며 같은 역할을 하는 AVL 트리와 달리 메인 메모리에 데이터를 저장하고 다루는 프로그래밍 언어에서의 자료구조로 적합하다.
Fail Fast