C언어 레드-블랙 트리 삭제 알고리즘(Red-Black Trees in C, deleting or removing algorithm)

C언어 레드-블랙 트리 삭제 알고리즘(Red-Black Trees in C, deleting or removing algorithm)

- 많은 검색-트리 구조 중 하나이다.

- 기본 동적 명령들이 최악의 경우에도 O(lg n) 시간이 걸리도록 보장하기 위해 안정(balanced) 되었다.

- 각 노드마다 하나의 추가적인 비트를 가지고 있다.

- 편리한 상태처리를 위해 NIL을 나타내는 센티널 노드가 있다.

- 다음 5가지의 특성을 만족하는 이진 트리이다.

(1) 각 노드는 빨강 또는 검정색이다.

(2) 루트(root)는 검정색이다.

(3) 모든 leaf(NULL)은 블랙이다.

(4) 만약 노드가 빨강이면, 해당 노드의 자식은 모두 검정이다.

(5) 각 노드에 대해, 해당 노드에서 자식 노드까지의 모든 경로들은 같은 수의 블랙 노드들은 포함한다.

[ Fig. 1 ] RED-BLACK TREES, cite : introduction to algorithms 3/E

1. 동작 원리

(1) 로테이션(Rotations)

- 레드-블랙 트리는 수행 시간을 보장하기 위해 트리를 수정한다. 그 결과 레드-블랙 트리의 특성을 위반하게 되기 때문에, 몇몇 노드의 색을 바꾸거나, 포인터 구조를 바꿔야하는데 이러한 작업을 로테이션이라 한다.

Fig. 2의 그림과 같이, left_rotate와 right_rotate가 있다. 특정 노드를 기준으로 회전 시키는 것과 같다.

[ Fig. 2 ] left and right rotation, cite : introduction to algorithms 3/E

(2) 노드 위치 옮기기(transplant)

삭제 알고리즘에서 중요한 부분을 차지하는 기능으로, 삭제될 노드의 자노드를 삭제될 노드의 자리에

옮기는(tranplant) 처리를 수행한다. Fig.3을 보면 z가 삭제될 노드이고, r, l, y가 자노드이다.

[ Fig. 3 ] process of transplant, cite : introduction to algorithms 3/E

(3) 레드-블랙 특성(red-black propertises)을 삭제 위한 조건

이전 포스에서 설명한 삽입 알고리즘보다 더욱 까다롭다. 노드 삭제를 위한 기본 구조는

이진 탐색 트리와 동일하다. 하지만 레드-블랙 특성 유지를 위해 2가지 포인터와 하나의 변수가 추가 된다.

y 포인터 : 삭제되거나 이동될 노드를 가르킨다. 자노드가 없거나, 하나인 경우에는 y가 가르키는 z가 삭제가

되지만, 자노드가 둘 다 있을 경우에는 y는 이동될 노드를 가르킨다(최소값의 키를 가진 노드).

x 포인터 : y의 원래 위치, 즉 이동되기 전이나 삭제되기 전 위치를 가르킨다. x가 가르키는 노드로부터

레드-블랙 특성 유지를 위한 작업을 수행한다.

y-original-color : y 노드의 원래 색상을 저장한다. 자노드 위치에 있던 y 를 삭제될 노드로 이동시키면서,

삭제될 노드의 색상을 부여하기 때문에 y 노드의 색상이 변경될 수 있기 때문이다.

x포인터와 y의 원래 색상을 이용하여 레드-블랙 특성을 유지한다.

만약 y의 원래 색상이 '빨강'이었다면, 다음과 같은 이유로 노드 삭제 후에도 특성이 유지된다.

(1) 빨간색 노드는 트리의 black-height에 영향을 미치지 않는다.

(2) 빨간색 노드는 인접(부노드 빨강, 자노드 빨강)을 만들지 않는다. y는 z의 위치로 이동되기 때문에

z의 색상을 가지게 된다. 따라서 인접을 만들 수 없다. 또한 y가 빨간색이었다면, x는 y의 자노드였기 때문에

특성 4에 의거하여 무조건 '검정'이어야 한다.

(3) y가 '빨강'이었다면, y는 루트노드가 될 수 없었다, 그리므로 루트는 검정으로 남아있다.

만약 y의 원래 색상이 '검정'이었다면, 3가지의 문제가 발생할 수 있다.

(1) y가 '검정'이었고, y의 자노드가 '빨강'인 경우에 y의 자노드가 root가 되면 특성 2를 위반한다.

(2) y가 '검정'이었으면, y의 부모노드(y.p) 및 자노드(x)가 '빨강'일 수 있다. 그럼 y가 이동될 경우

x가 y의 위치에 대처되므로, 인접이 발생하여 특성 4를 위반한다.

(3) y가 '검정'이었으면, y가 트리의 다른 경로로 이동 될 경우, 원래 경로는 하나 더 적은 black-height를

갖게 되므로, 특성 5를 위반하게 된다.

만약 x가 가르키는 노드가 '빨강'이 경우에는 단순히 x를 '검정'으로 바꿔주면 특성이 유지가 된다.

y의 원래 색상이 검정이었기 때문에, y의 원래 위치에 대체된 x를 '빨강'에서 '검정'으로 바꿔줌으로

특성을 그대로 유지시킬 수 있다.

그러나 x가 검정일 경우에는 y의 이동으로 인해 black-height가 1줄어든 상태이다.

따라서 이러한 경우에 레드-블랙 특성을 유지하기 위한 조건으로는 총 8가지가 있다.

하지만 4개의 특성은 대칭적인 구조이므로, 4가지 특성만 고려하면 된다.

실질적으로 특성을 유지시키는 것은 CASE 2와 4이고, CASE 1은 CASE 2,3에 맞게 변환시켜주는 역할, CASE 3은 CASE 4에 맞게 변환 시켜주는 역할이다.

CASE 1 : 형제 노드가 '빨강'일 경우

이 경우는, 형제 노드의 색을 '검정'으로 바꿔주고, 형제 노드를 기준으로 로테이션을 수행한다.

로테이션 후 x의 형제 노드를 업데이트한다.(기존 형제 노드의 자노드로서 특성 상 무조건 '검정'이다.)

그럼 특성에는 영향을 주지 않지만, 형제 노드가 '검정'이 되므로 다음 CASE에 진입할 수 있게 된다.

CASE 2 : 형제 노드가 '검정'이고, 형제 노드의 자노드가 모두 '검정'일 경우

형제 노드를 '빨강'으로 바꾸어 주면, black-height가 동일해지므로 특성 5를 유지시킬 수 있다.

CASE 3 : 형제 노드가 '검정'이고, 형제 노드의 좌노드가 '빨강', 우노드가 '검정'일 경우

형제 노드를 '빨강'으로 바꾸어 로테이션을 수행한다. 그럼 기존 형제 노드가 '빨강'의 자노드가 되므로

CASE 4에 진입할 수 있게 된다.

CASE 4 : 형제 노드가 '검정'이고, 형제 노드의 우노드가 '빨강'일 경우

마지막 경우로서, x의 노드가 있는 경로에는 아직 black-height가 1 적다.(y가 이동되었기 때문에)

따라서 형제 노드를 '빨강'으로 바꾸어주면서 로테이션을 수행한다. 그리고 형제 노드의 자노드를

검정으로 바꿔주면서, 형제 노드 쪽의 경로의 black-height에는 영향을 주지 않게된다.

그리고 원래 부모 노드에 있던 '빨강' 노드(특성 4에 의하여 부모 노드는 '빨강'이다)를 x 노드의 경로에

추가시키면서 '검정'색으로 바꾼다. 이로서 x의 black-height가 다시 복구되므로 특성을 유지하게 된다.

[ Fig. 4 ] process of removing from the tree, cite : introduction to algorithms 3/E

2. 함수 설명

void left_rotate( ROOT *, NODE *)

= 좌측 로테이션을 수행하는 함수이다. 두 번째 매개변수로 전달하는 노드를 중심으로 회전시킨다.
void right_rotate( ROOT *, NODE *)

= 우측 로테이션을 수행하는 함수이다. 두 번째 매개변수로 전달하는 노드를 중심으로 회전시킨다.

void delete_node( ROOT *, int)

= 트리에서 노드를 삭제하는 함수로, 이진탐색 트리와 유사하다.
void delete_fixup( ROOT *, NODE *)

= 노드 삭제 시 레드-블랙 특성을 유지시켜주는 함수
void tree_transplant( ROOT *, NODE *, NODE *)

= 노드의 위치를 이동시켜주는 함수

3. 함수 구현

/* void tree_transplant( ROOT *, NODE *, NODE *) It maintains the propertise of the tree. */ void tree_transplant( ROOT *r, NODE *t, NODE *c) {     if( t->p == r->nil)     {         r->r    = c;     }     else if( t == (t->p)->left)     {         (t->p)->left    = c;     }     else     {         (t->p)->right   = c;     }     c->p    = t->p; // link target's parent to child's parent. }

/* void left_rotate( NODE **, NODE *) This function transforms the configuration of the two nodes on the right into the configuration on the left by changing a constant number of pointers. */ void left_rotate( ROOT *r, NODE *x) {     NODE *temp;     temp        = x->right;     // turn temp's left subtree into x's right subtree     x->right    = temp->left;     if( temp->left != r->nil)     {         (temp->left)->p = x;     }     temp->p = x->p; // link x's parent to temp     if( x->p == r->nil)     {         r->r    = temp;     }     else if( x == (x->p)->left)     {         (x->p)->left    = temp;     }     else     {         (x->p)->right   = temp;     }     temp->left  = x; // put x on temp's left     x->p        = temp; }

/* void right_rotate( NODE **, NODE *) This function transforms the configuration of the two nodes on the left into the configuration on the right by changing a constant number of pointers. */ void right_rotate( ROOT *r, NODE *y) {     NODE *temp;     temp        = y->left;     // turn temp's right subtree into y's left subtree     y->left     = temp->right;     if( temp->right != r->nil)     {         (temp->right)->p = y;     }     temp->p = y->p; // link y's parent to temp     if( y->p == r->nil)     {         r->r    = temp;     }     else if( y == (y->p)->left)     {         (y->p)->left    = temp;     }     else     {         (y->p)->right   = temp;     }     temp->right = y; // put y on temp's right     y->p        = temp; }

/* void delete_node( ROOT *, int) remove the node that has the key from the tree. */ void delete_node( ROOT *r, int key) {     NODE *target    = r->r; // the node that we want to remove.     NODE *temp      = NULL; // the node that is moved or removed.     NODE *x         = NULL; // temp's original position     char t_clr;     // find the node that has the key     while( key  != target->key)     {         if( target->key > key)         {             target  = target->left;         }         else         {             target  = target->right;         }     }     t_clr   = target->clr;     // the target has the child on the right.     if( target->left == r->nil)     {         x   = target->right;         tree_transplant( r, target, target->right);     }     // the target has the child on the left.     else if( target->right == r->nil)     {         x   = target->left;         tree_transplant( r, target, target->left);     }     else     {         temp    = target->right;         // find the minimum key         while( temp->left != r->nil)         {             temp    = temp->left;         }         t_clr   = temp->clr;         x   = temp->right;                 // because temp will move target's position,         // temp's right child is moved temp's position.         tree_transplant( r, temp, temp->right);         temp->right         = target->right;         (temp->right)->p    = temp;         // temp takes target's position         tree_transplant( r, target, temp);         temp->left      = target->left;         (temp->left)->p = temp;         temp->clr       = target->clr;     }     if( t_clr== BLACK)     {         delete_fixup( r, x);     }     free(target); }

/* void delete_fixup( ROOT *, NODE *) This function restore the red-black propertises. when the node is removed, because problems about the propertises may arise. */ void delete_fixup( ROOT *r, NODE *x) {     NODE *s = NULL; // sibling node.     while( (x != r->r) && ( x->clr == BLACK))     {         if( x == (x->p)->left)         {             s   = (x->p)->right;             // case 1 : x's sibling s is red             if( s->clr == RED)             {                 s->clr      = BLACK;                 (x->p)->clr = RED;                 left_rotate( r, x->p);                 // update x's sibling                 s   = (x->p)->right;             }             // case 2 : x's sibling s is black, and both of s's children are black.             if( (s->left)->clr == BLACK && (s->right)->clr == BLACK)             {                 s->clr  = RED;                 x       = x->p;             }             // case 3 : x's sibling s is black, s's left child is red, another is black.             else if( (s->left)->clr == RED && (s->right)->clr == BLACK)             {                 s->clr          = RED;                 (s->left)->clr  = BLACK;                 right_rotate( r, s);                 // update x's sibling                 s   = (x->p)->right;             }                         // case 4 : x's sibling s is black, s's right child is red.             if( (s->right)->clr == RED)             {                 s->clr          = (x->p)->clr;                 (s->right)->clr = BLACK;                 (x->p)->clr     = BLACK;                 left_rotate( r, x->p);                             x   = r->r;             }         }         else         {             s   = (x->p)->left;             // case 1 : x's sibling s is red             if( s->clr == RED)             {                 s->clr      = BLACK;                 (x->p)->clr = RED;                 right_rotate( r, x->p);                 // update x's sibling                 s   = (x->p)->left;             }             // case 2 : x's sibling s is black, and both of s's children are black.             if( (s->left)->clr == BLACK && (s->right)->clr == BLACK)             {                 s->clr  = RED;                 x       = x->p;             }             // case 3 : x's sibling s is black, s's right child is red, another is black.             else if( (s->right)->clr == RED && (s->left)->clr == BLACK)             {                 s->clr          = RED;                 (s->right)->clr = BLACK;                 left_rotate( r, s);                 // update x's sibling                 s   = (x->p)->left;             }                         // case 4 : x's sibling s is black, s's left child is red.             if( (s->left)->clr == RED)             {                 s->clr          = (x->p)->clr;                 (s->left)->clr  = BLACK;                 (x->p)->clr     = BLACK;                 right_rotate( r, x->p);                             x   = r->r;             }         }     }     x->clr  = BLACK; }

 

4. 실행 결과