레드-블랙 트리에서 새로운 노드를 삽입할 때, 새로운 노드는 항상 적색으로 입력한다.
만약 트리가 레드블랙 트리의 특성을 위반하면, 두가지 operation 을 통해 트리의 구조를 조정한다.
(1) Recolor (2) Rotation.
키 값이 20인 노드를 삽입하는 과정을 생각해보자,
중요 : target Node를 20으로 설정하고 시작.
target node(18) -> color = red, parent -> color = red
특성4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
-> 어라? 위반했네..
case 1 결과 :
-> 18을 루트노드인 서브트리는 레드-블랙 트리의 특성을
(fix-up 과정의 마지막에 트리의 루트노드를 흑색으로 칠해주는 과정이 있다. 만약, 18이 루트노드 였다면, 흑색으로 색칠하여 레드-블랙 트리의 특성을 보전할 수 있다.)
-> target node를 18 로 설정한다. (할아버지)
target node(18) -> color = red, parent -> color = red
특성4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
-> 어라? 위반했네..
case 2결과 :
사실 지금까지 했던 것은 case 2 - (1) 이었다.
case 2 - (1) 인 경우에는 case 2 - (2)의 형태로 바꾸고 case 2 - (2) 를 진행한다고 생각하면 된다.
case 2 - (2) 는 부모노드가 할아버지노드의 왼쪽 자식이며, target 또한 부모노드의 왼쪽자식일 때이다.
(혹은 오른쪽 자식의 오른쪽 자식이 target일 때)
여기까지 정리해보면,
1. Fix-up 과정은 부모노드가 적색일 때 일어난다.
2. case 1 은 부모노드와 삼촌 노드가 모두 적색일 때,
3. case 2 는 2가지로 나뉜다.
case 2 : 부모노드는 적색, 삼촌노드는 흑색일 때.
case 2 - (1) :
grandparent -> left -> right = target 또는 grapndparent -> right -> left = target.
case 2 - (2) :
grandparent -> left -> left = target 또는 grandparent -> right -> right - target
처음에 case 2 - (2) 형태로 들어올 수도 있고,
case 2 - (1) 형태이면 이어서 case 2 - (2) 를 바로 진행하게 된다.
(또는 grandparent -> right -> right - target)
target 노드 = 10
Recolor : 부모노드(18)를 흑색으로 바꾼다, 할아버지 노드(30)를 적색으로 바꾼다.
우회전 실시!
while 문의 조건이 target의 부모노드가 적색 노드일 때다. target node(18)의 부모노드는 nil 노드로, 흑색으로 설정되어 있다. 따라서, while 문이 종료된다.
target 노드가 case 1 의 결과처럼 적색 노드이고, 루트노드일 경우가 있으므로, while문이 끝나고 마지막에 루트노드의 색을 흑색으로 칠하고 insertion fix-up을 종료한다.
레드-블랙 트리의 특성을 만족하는 트리가 완성되었다.
슈도 코드는 다음과 같다.
* 주의 : else if 가아니라 else안에 if문임.
void left_rotate(rbtree *t, node_t *x){
node_t *y;
y = x->right;
x->right = y->left;
if (y->left != t->nil){
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == t->nil){
t->root = y;
}
else if (x == x->parent->left){
x->parent->left = y;
}
else{
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void right_rotate(rbtree *t, node_t *x)
{
node_t *y;
y = x->left;
x->left = y->right;
if (y->right != t->nil){
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == t->nil){
t->root = y;
}
else if (x == x->parent->right){
x->parent->right = y;
}
else{
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
void *rb_insert_Fixup(rbtree *t, node_t *z)
{
node_t *uncle;
while (z->parent->color == RBTREE_RED){
if (z->parent == z->parent->parent->left){
uncle = z->parent->parent->right;
//경우1
if (uncle->color == RBTREE_RED){
z->parent->color = RBTREE_BLACK;
uncle->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
}
//경우2 (경우 2는 경우 3을 경유)
else {
if (z == z->parent->right){
z = z->parent;
left_rotate(t, z);
}
//경우3
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
right_rotate(t, z->parent->parent);
}
}
//반대로
else
{
uncle = z->parent->parent->left;
//경우1
if (uncle->color == RBTREE_RED){
z->parent->color = RBTREE_BLACK;
uncle->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
}
//경우2 (경우2는 경우3을 경유)
else {
if (z == z->parent->left){
z = z->parent;
right_rotate(t, z);
}
//경우3
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
left_rotate(t, z->parent->parent);
}
}
}
t->root->color = RBTREE_BLACK;
}
node_t *rbtree_insert(rbtree *t, const key_t key){
// TODO: implement insert
node_t *parent = t->nil;
node_t *p = t->root;
//새 노드가 들어갈 자리 찾기
while (p != t->nil){
parent = p;
if (key < p -> key){
p = p->left;
}
else{
p = p->right;
}
}
node_t *new_node = (node_t *)calloc(1, sizeof(node_t));
new_node->parent = parent;
// 트리의 첫 노드일 때 - 루트가 된다
if (parent == t->nil){
t->root = new_node;
new_node->color = RBTREE_BLACK;
}
//찾은 부모노드보다 새로운 노드가 작을때 - 왼쪽 자식으로
else if (key < parent->key){
parent->left = new_node;
new_node->color = RBTREE_RED;
}
//크거나 같을때 - 오른쪽 자식으로
else{
parent->right = new_node;
new_node->color = RBTREE_RED;
}
//새로운 노드 설정
new_node->key = key;
new_node->left = t->nil;
new_node->right = t->nil;
rb_insert_Fixup(t, new_node);
return t->root;
}
포인터 변수, 메모리 할당(malloc, free), stack & heap 메모리, call by reference, call by value, 단순 이진 탐색 트리와 달리 최악의 경우에도 O(log(n))을 보장하는 RB 트리의 위대함. RB 트리는 이진탐색트리를 유지하면서 RB 트리의 특성을 만족시키기 위해 color demotion, color promotion, rotation 등을 통해 근사적인 균형을 이룬다.