Rotation
RBTree의 삽입과 삭제에 대해서 살펴보기 전에, 먼저 Rotation에 대해 알고 가야 합니다.
Insert와 Delete 각각의 연산은 RB트리 상에서 O(lg n)시간 안에 수행됩니다. 이때 트리를 수정하기 때문에 RBTree의 속성들을 위반할 수 있습니다.
따라서 속성을 복원하기 위하여 일부 노드들의 색상과 포인터 구조를 변경해야 하는데, 이때 Rotation을 활용합니다.
이때 위반될 수 있는 RBTree의 속성 5가지는 다음과 같습니다.
- 모든 노드는 red / black의 색깔이 있어야 한다.
- root 노드는 black이어야 한다.
- leaf 노드는 black이어야 한다.
- red노드의 child 노드는 모두 black이다.
- 각 노드에서 leaf노드로 가는 모든 경로에 있는 블랙 노드의 수는 항상 같아야 한다.
회전에는 좌회전, 우회전이 존재합니다.
좌회전과 우회전이 대칭구조를 이루기 때문에 좌회전에 대해서만 다루겠습니다.
그림의 우측에서 x에 대해 좌회전을 수행할 때, 노드의 자식인 y가 T.nil(센티넬을 사용한다면)이 아니라고 가정합니다. 마찬가지로 x도 트리 안에서 우측 자식이 T.nil 이 아닌 노드가 됩니다.
좌회전을 통해서 x를 루트로하는 서브트리는 y가 루트가 되는 서브트리가 됩니다.
코드는 좌회전에 대한 C코드입니다.
void rotate_left(rbtree *t, node_t* target)
{
node_t* y = target->right;
target->right = y->left;
if (y->left != t->nil) {
y->left->parent = target;
}
/* y의 좌측 자식을 x(target)의 우측에 연결합니다 */
y->parent = target->parent;
if (target->parent == t->nil)
{
t->root = y;
}
else if (target == target->parent->left)
{
target->parent->left = y;
}
else
{
target->parent->right = y;
}
/* y를 기존 x의 위치(x의 부모와 연결)에 삽입합니다 */
y->left = target;
target->parent = y;
/* y의 좌측 자식으로 x를 설정합니다 */
}각 코드의 진행 상황을 그림으로 그려보면 다음과 같습니다.
Insert
새로운 노드를 z라 가정하면, 이를 일반 BST에 삽입한 뒤, 이것의 색을 red로 칠합니다.
이후 RB트리의 특성이 보존됨을 보장하기 위해서 RB_insert_fixup을 호출하여서 노드를 재 색칠하거나 회전을 수행합니다.
이때, 삽입되는 노드의 색깔은 RED여야 하는데, 이는 삽입 후에도 5번 속성을 만족하기 위함입니다.(경로의 블랙 수를 바꾸지 않기 위해)
삽입시 주로 위반하게 되는 속성은 4번 속성입니다.
- 이때, 새로 삽입된 노드의 부모가 RED입니다.
삽입 시 4번 속성이 위반되는 Case는 3개입니다.
삽입은 크게
- 부모가 조부모의 왼쪽 자식
- 부모가 조부모의 오른쪽 자식
두가지의 경우로 분류되는데, 여기서는 부모가 조부모의 왼쪽 자식인 케이스에 대해서만 설명하겠습니다.
부모가 조부모의 오른쪽 자식인 경우는 해당 경우의 좌와 우를 바꾸면 됩니다.
FIXUP이 작동하는 와중의(코드로 치면 while이 유지되는) 불변하는 조건은 다음 세가지와 같습니다
1. z는 적색이다
2. z.p가 루트면 흑색이다
3. 특성 2 또는 4만 위반된다.(1,3,5는 이미 만족)
따라서, while 루프가 종료되는 조건은
1. z.p는 흑색이어서 종료시점에 특성 4가 위반되지 않음
2. 이때 루프 불변식에 의해 위반되는 유일한 특성은 2번 특성입니다. -> 루트를 흑색으로 칠해주고 끝내면 됩니다.
또한, z.p가 적색인 동안만 루프를 돌기에 z.p는 루트가 될수가 없습니다. 따라서 z.p.p는 항상 존재합니다.
이때 z의 부모의 형제 - 즉 삼촌 - 에 따라서 경우 1, 2 , 3이 구분이 됩니다.
1. z의 삼촌 y가 적색
삽입된 노드의 부모가 red이고, 삼촌(조부모의 오른쪽 자식)이 red일때, 4번의 위반을 해결하면서 5번을 유지하려면, 부모와 - 형제 / 그리고 조부모의 색깔을 바꿔주면 됩니다.
사진과 같이 말이죠.
z.p와 y를 흑색으로 칠해서, z와 z.p가 모두 적색이어서 4번을 위반하는 문제를 해결하고, z.p.p를 새로운 z로 놓고 while 루프를 반복합니다.
z.p.p를 z^이라 두면,
1. z^은 적색이고
2. z^p 인 z.p.p.p 노드의 색을 변경하지 않았기에, 해당 노드가 루트이면 흑색으로 유지됩니다
3. 특성 2또는 4만이 위반돼야 하는데,
- z^가 다음 반복에서 루트이면, 특성 2만이 위반되는 특성이고
- z^가 다음 반복에서 루트가 아니라면, z^.p가 RED인 경우에 특성 4가 위반됩니다.
따라서 루프 불변식은 z를 z^로 옮긴 이후에도 유지됩니다.
2. z의 삼촌 y가 흑색, z는 부모의 오른쪽 자식.
경우 2는 경우 3으로 만든 이후에 해결하기 때문에 이에 대한 사진 먼저 첨부하겠습니다.
이때 4번 속성이 위반되고, 이를 해결하기 위해 red하나를 넘겨야하는데, BST의 특징을 유지하면서 회전을 통해 넘겨주어야 합니다.
따라서 어떤 방식으로 회전을 주어야 할지가 관건입니다.
문제는 조부모까지 가는 경로가 꺾여있기 때문에, 꺾인 부분을 펴주어서 앞으로 살펴볼 case3와 같은 방식으로 만들어줘야 합니다.
따라서 z의 부모 새로운 z로 만든뒤, 새로운 z를 기준으로 좌회전을 하면 Case3의 모양으로 변화합니다.
3. z의 삼촌 y가 흑색, z는 부모의 왼쪽 자식.
현재 red 두개가 한쪽으로 몰려있기 때문에 4번 속성이 위반됩니다.
따라서 한쪽으로 몰려있는 red 하나를 반대편으로 옮겨주면 됩니다.
이때 BST의 특징을 유지하면서 값을 넘겨주기 위해서, 앞서 살펴본 회전(Rotation)을 사용합니다.
따라서 이때, 부모와 조부모의 색을 바꿔준 뒤, 조부모를 기준으로 회전을 해주면 red하나가 성공적으로 반대편으로 건너갑니다.
경우 2, 3의 경우에도 루프 불변성이 유지됩니다.
- 경우 2에서 z는 z.p를 가리키며, 이때 z.p는 적색입니다. 경우3에서는 z의 색변화가 없습니다
- 경우 3에서 z.p는 흑색이 되고, 다음 반복수행시 z.p가 루트라면 루트 = 흑색 조건이 만족됩니다
- 경우 2와 3을 거쳐서 위반됐던 특성 4는 고쳐지며, 실행 과정에서 적색으로 바뀐 노드(그림에서는 c)가 회전에 의해 BLACK의 자식이 되기 때문에 특성2는 위반되지 않습니다.
따라서 경우 2,3은 4번 규정의 단독 위반을 바로잡을 뿐입니다.
C언어로 구현한 전체 코드는 다음과 같습니다
Insert - C
node_t *rbtree_insert(rbtree *t, const key_t key) {
// TODO: implement insert
node_t * z = (node_t *)calloc(1, sizeof(node_t));
z->key = key;
node_t * y = t->nil; // 부모노드 역할
node_t * x = t->root; // 부모를 끌고가는 역할
while (x != t->nil)
{
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->parent = y;
if (y == t->nil)
t->root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
z->left = t->nil;
z->right = t->nil;
z->color = RBTREE_RED; // 삽입되는 z는 적색
rb_insert_fixup(t, z);
return t->root;
}Insert-fixup
void rb_insert_fixup(rbtree *t, node_t * target)
{
while (target->parent->color == RBTREE_RED) // 종료조건: 루프 종료시 target의 부모는 BLACK
{
if (target->parent == target->parent->parent->left) // 대분류1. target.p는 조부모의 왼쪽 자식
{
node_t * y = target->parent->parent->right; // 삼촌 y
if (y->color == RBTREE_RED) { // 경우 1: target의 삼촌 y가 적색
target->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
target->parent->parent->color = RBTREE_RED;
target = target->parent->parent;
}
else
{
if (target == target->parent->right) // 경우 2: target의 삼촌 y가 흑색, target이 부모의 오른쪽 자식 -> 경우3으로 만듬
{
target = target->parent;
rotate_left(t, target);
}
/* 경우 3: target의 삼촌 y가 흑색, target이 왼쪽 자식 */
target->parent->color = RBTREE_BLACK;
target->parent->parent->color = RBTREE_RED;
rotate_right(t, target->parent->parent);
}
}
else // 대분류2. z.p는 조부모의 오른쪽 자식
{
node_t * y = target->parent->parent->left; // 삼촌 y
if (y->color == RBTREE_RED) // 경우 1: target의 삼촌 y가 적색
{
target->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
target->parent->parent->color = RBTREE_RED;
target = target->parent->parent;
}
else
{
if (target == target->parent->left) // 경우 2: target의 삼촌 y가 흑색, taget이 부모의 왼쪽 자식 -> 경우3으로 만듬
{
target = target->parent;
rotate_right(t, target);
}
/* 경우 3: target의 삼촌 y가 흑색, target이 오른쪽 자식 */
target->parent->color = RBTREE_BLACK;
target->parent->parent->color = RBTREE_RED;
rotate_left(t, target->parent->parent);
}
}
}
t->root->color = RBTREE_BLACK;
}Delete
노드를 삭제하는 것 또한 일반적인 BST와 동일하게 삭제한 후,
RB트리의 속성 위반 여부를 확인 한 후 이에 대해 재조정을 거칩니다.
이때 RB트리의 속성 위반 여부는 "삭제 되는 색"에 따라 달라집니다.
삭제되는 색은, 노드의 자녀 수에 따라 달라집니다
- 삭제되는 색 = 삭제되는 노드의 색 : 삭제하는 노드의 자녀가 없거나, 하나인 경우
- 삭제되는 색 = 삭제되는 노드의 successor의 색 : 삭제하려는 노드의 자녀가 둘인 경우
(successor: 노드의 우측 서브트리에서 가장 작은 값 - 그러니깐, 바로 다음 값)
삭제되는 색이 무엇인지 알아봤으니, 삭제되는 색에 따라 어떤 속성이 위반되는지 알아봐야겠죠??
- 첫번째로, 삭제되는 색이 red라면 어떠한 속성도 위반하지 않습니다.
- 삭제되는 색이 black이라면 RB트리의 2번,4번,5번 속성을 위반할 수 있습니다.
따라서, 삭제되는 색이 Black인 경우에만 재조정을 거쳐주면 됩니다.
우선, 2번 속성(루트는 black이어야 한다)이 위반됐다면, 그냥 루트 노드를 black으로 바꿔주면 됩니다.
주로 해결해야 하는 속성 위반은 5번입니다.
5번 속성은 임의의 노드에서 그 노드의 자손 nil 노드들까지 가는 경로들의 black 수는 같다. 였습니다.
이를 해결하기 위해 노드에 "삭제된 색의 위치를 대체한 노드" 에 "extra black"을 부여합니다. (앞서 삭제되는 색이 삭제되는 노드의 자녀수에 따라 어떻게 달라지는지 알아보았습니다.)
-
이 extra black은 경로를 카운팅할때 하나의 black으로 카운트됩니다.
-
만약 black노드에 extra black이 부여되면, 이는 doubly black이
-
red노드에 extra black이 부여되면, 이는 red and black이 됩니다.
이제 extra black을 부여해주었으니, 추가된 black을 해결해주기만 하면 됩니다.
-
일단 red-and-black이 된 경우, 이를 black으로 바꿔주면 끝입니다.
-
doubly black이 된 경우, 이를 어떻게 없앨것인지가 관건입니다.
doubly black의 extra black을 없애는 방법은 총 4가지 case로 분류가 됩니다.
그리고 이는 "doubly black의 형제의 색"과 "그 형제의 자녀들의 색"에 따라서 나뉘어집니다.
여기서는 삭제된 색을 대체한 노드 x가 부모의 왼쪽 자식일때만을 가정하고 얘기합니다.(오른쪽 자식인 경우 왼쪽/오른쪽을 바꿔주면 됩니다)
Case4: doubly black의 오른쪽 형제가 black & 그 형제의 우측 자식이 red
- 이때는 결과론적으로, 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀와 & 부모를 black으로 바꾼 후, 부모를 기준으로 왼쪽으로 회전하면 해결됩니다.
case3: doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 black
이 경우는 형제의 우측 자녀가 red가 되게 만든 이후, case4를 적용해주면 됩니다.
따라서 형제와 형제의 왼쪽 자식의 색을 바꾸고, 형제에 대해 우회전을 해주어서 경우4로 변환해줍니다.
case2: doubly black의 형제가 black & 형제의 두 자식이 모두 흑색
- fixup을 적용하는 노드 x의 doubly black과 형제의 black의 black을 모아서, 부모에게 전달합니다
- x는 여전히 black이고, 형제는 red가 됩니다.
- 부모는 extra black을 부여받은 상황입니다
- 따라서 부모의 상황에 따라서 Case 1,2,3,4 중 하나를 적용해서 해결해줍니다.
case1: doubly black의 형제가 적색
-
이때는 형제를 black으로 만든 후, case 2,3,4 중 하나로 해결해주면 됩니다.
-
이때, 회전 후에도 5번 속성을 만족하기 위해서, 왼쪽으로 회전하기 전 B와 D의 색상을 바꿔줍니다.
-
이 이후 B를 기준으로 왼쪽으로 회전한 후, case 2,3,4 중 하나로 해결해줍니다.
전체 코드는 다음과 같습니다.
rb-erase-fixup
void rb_erase_fixup(rbtree *t, node_t* x)
{
while (x != t->root && x->color == RBTREE_BLACK) // 루트가 아니며, doubly black인동안.
{
if (x == x->parent->left) // 대분류 1. fixup을 적용하는 x는 자신의 부모의 좌측자식
{
node_t* w = x->parent->right; // 형제
if (w->color == RBTREE_RED) // 경우 1. 형제가 RED인경우
// 부모와 형제의 색을 바꾸고, 부모를 기준으로 왼쪽으로 회전한 후, doubly black기준으로 경우 2,3,4중 하나로 해결
{
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
rotate_left(t, x->parent);
w = x->parent->right; // 새로운 형제
}
if ((w->left->color == RBTREE_BLACK) && (w->right->color == RBTREE_BLACK)) // 경우 2. 형제가 BLACK, 형제의 두 자녀 모두 BLACK
// 형제와 나의 BLACK을 모아서 부모에게 전달(형제는 RED로 변화), 부모를 기준으로 extra black 다시 해결
{
w->color = RBTREE_RED;
x = x->parent; // 부모에게 상황 위임
}
else {
if (w->right->color == RBTREE_BLACK) // 경우 3. 형제가 BLACK, 형제의 우측자식이 BLACK, 좌측은 RED
// 형제의 오른쪽 자녀를 RED로 만들어서 경우4를 적용시킬 준비
{
w->left->color = RBTREE_BLACK;
w->color = RBTREE_RED;
rotate_right(t, w);
w = x->parent->right;
}
// 경우 4. 형제가 BLACK, 형제의 오른쪽 자녀가 RED
w->color = x->parent->color; // 형제의 색깔은 부모의 색으로
x->parent->color = RBTREE_BLACK; // 형제의 오른쪽 자녀와 부모를 BLACK으로
w->right->color = RBTREE_BLACK;
rotate_left(t, x->parent); // 부모를 기준으로 왼쪽으로 회전
x = t->root;
}
}
else // 대분류 2. fixup을 적용하는 x는 자신의 부모의 우측자식 - 대분류1과 왼쪽 오른쪽이 반대
{
node_t* w = x->parent->left;
if (w->color == RBTREE_RED)
{
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
rotate_right(t, x->parent);
w = x->parent->left;
}
if ((w->left->color == RBTREE_BLACK) && (w->right->color == RBTREE_BLACK))
{
w->color = RBTREE_RED;
x = x->parent;
}
else
{
if (w->left->color == RBTREE_BLACK)
{
w->right->color = RBTREE_BLACK;
w->color = RBTREE_RED;
rotate_left(t, w);
w = x->parent->left;
}
w->color = x->parent->color;
w->parent->color = RBTREE_BLACK;
w->left->color = RBTREE_BLACK;
rotate_right(t, x->parent);
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
}rb-erase
int rbtree_erase(rbtree *t, node_t *z) {
node_t * y = z;
color_t y_original_color = y->color;
node_t* x;
if (z->left == t->nil) // 좌측이 nil(우측도 nil일수 있음)
{
x = z->right;
rb_transplant(t, z, z->right);
}
else if (z->right == t->nil) // 좌측자식 하나 - 위 두가지경우에는 삭제되는 색 = 삭제되는 노드의 색
{
x = z->left;
rb_transplant(t, z, z->left);
}
else // 자식 둘 - 삭제되는 색 = 삭제되는 노드의 successor의 색
{
node_t * y = tree_minimum(t, z->right); // y가 successor(왼쪽서브트리에서 가장 작은 값)
y_original_color = y->color;
x = y->right; // 이 경우에도 successor의 자리를 대체하는 x에 대해 fixup을 돌려줘야 한다
if (y->parent == z)
{
x->parent = y;
}
else /* 우측서브트리가 남기때문에(y가 z.right 서브트리의 유일 원소가 아니기에), 남은 서브트리에 대한 작업 필요 */
{
rb_transplant(t, y, y->right); // y의 우측자식 y자리로 옮겨주고
y->right = z->right; // y의 우측자식을 z의 우측서브트리로 둠
y->right->parent = y;
}
rb_transplant(t, z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if (y_original_color == RBTREE_BLACK)
rb_erase_fixup(t, x);
free(z);
return 0;
}