C언어 레드-블랙 트리 삽입 알고리즘 (Red-Black Trees in C, insertion algorithm)

C언어 레드-블랙 트리 삽입 알고리즘 (Red-Black Trees in C, insertion 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) 레드-블랙 특성(red-black propertises)을 위한 조건

조건 설명에 앞에 몇몇 개념을 지칭하는 것이 설명에 도움이 될 것이다.

어떠한 노드 z를 예를 들면,

z의 상위 노드(z.p) = 부모 노드

z의 상위 노드의 상위 노드(z.p.p) = 할아버지 노드

z의 할아버지 노드의 자식 노드(z.p.p.left or right) = 삼촌 노드

위와 같이 지칭하고 시작하겠다.

레드-블랙 특성을 유지하기 위한 조건을 세분화하면 총 여섯가지가 된다.

하지만 조건에 좌우대칭을 이루고 있으므로, 실질적으로 3가지 조건으로 특성을 유지할 수 있다.

 

- CASE 1 : 부모 노드가 빨간색이고, 삼촌 노드도 빨간색인 경우

이 경우에는 레드-블랙 특성 4를 위반하게 된다. 따라서 부모 노드와 삼촌 노드를 모두 '검정'으로

바꾸면 이 문제를 해결할 수 있으나, 그렇게되면 특성 5를 위반하게 된다. 따라서 할아버지 노드를

'빨강'으로 바꾸어 특성을 유지시킬 수 있다.

- CASE 2 : 부모 노드가 빨간색, 삼촌 노드가 검은색이고, 현재 노드가 우측 자식일 경우

CASE 2의 경우에는 즉각적으로 로테이션을 통해 CASE 3의 상황으로 만든다.

부모 노드와 현재 노드가 빨간색이기 때문에 로테이션이 노드의 black-height나

특성 5에 영향을 미치지 않는다.

- CASE 3 : 부모 노드가 빨간색, 삼촌 노드가 검은색이고, 현재 노드가 좌측 자식일 경우

CASE 3의 경우 특성 5를 유지하기 위해 몇몇 노드의 색 변경과 로테이션을 수행한다.

로테이션 후에는 부모 노드를 기준으로 균형이 잡히게 된다. 따라서 부모 노드를 '검정'으로 변경하고

기준이었던 노드를 '빨강'으로 변경하여 레드-블랙 특성을 유지시킨다.

[ Fig. 3 ] process of preserving on propertises, cite : introduction to algorithms 3/E

2. 함수 설명

void create_nilnode( ROOT *)

= 센티널 노드를 생성하는 함수이다.
void left_rotate( ROOT *, NODE *)

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

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

= 트리에 노드를 삽입하는 함수이다. 이진-검색 트리와 큰 차이가 없다.

= NULL 대신 센티널 노드를 가르키는 것이 차이점이다.
void insert_fixup( ROOT *, NODE *)

= 레드-블랙 특성을 유지시켜주는 함수로, 앞서 설명한 CASE 에 맞게 동작한다.

3. 함수 구현

/* void create_nillnode( ROOT *) This function creates the nil node that the root node and leaves point it. It is called as the sentinel */ void create_nilnode( ROOT *r) {     r->nil  = (NODE*)malloc(sizeof(NODE));     (r->nil)->clr = BLACK;     r->r    = r->nil; }

/* 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 insert_node( NODE **, int) This function inserts a node that contains the key in the tree. it follows the binary-search trees structure. */ void insert_node( ROOT *r, int key) {     NODE *n     = (NODE *)malloc(sizeof(NODE));     NODE *temp  = r->r;     NODE *p     = r->nil;     n->left     = r->nil;     n->right    = r->nil;     n->clr      = RED;     n->key      = key;     // find the position that new node can be inserted.     while( temp != r->nil)     {         p   = temp;         if( key > temp->key)         {             temp    = temp->right;         }         else         {             temp    = temp->left;         }     }     n->p    = p; // link new node to p     if( p == r->nil)     {         r->r    = n;     }     else if( key > p->key)     {         p->right    = n;     }     else     {         p->left     = n;     }     insert_fixup( r, n); }

/* void insert_fixup( NODE **, NODE *) This function restores the RED-BLACK propertises. it examines the code into three major steps. when node z is inserted and colored red, it determines what violations of the red-black properties. */ void insert_fixup( ROOT *r, NODE *x) {     NODE *u = NULL;;     while( (x->p)->clr == RED)     {         if( x->p == (x->p->p)->left)         {             u   = (x->p->p)->right;             // process property 4 of the red-black properties.             if( u->clr == RED)             {                 (x->p)->clr = BLACK;                 u->clr      = BLACK;                 (x->p->p)->clr  = RED;                 x   = (x->p->p);             }             // process property 5             else             {                 if( x == (x->p)->right)                 {                     x   = (x->p);                     left_rotate( r, x);                 }                 (x->p)->clr     = BLACK;                 (x->p->p)->clr  = RED;                 right_rotate( r, (x->p->p));             }         }         else         {             u   = (x->p->p)->left;             // process property 4 of the red-black properties.             if( u->clr == RED)             {                 (x->p)->clr = BLACK;                 u->clr      = BLACK;                 (x->p->p)->clr  = RED;                 x   = (x->p->p);             }             // process property 5             else             {                 if( x == (x->p)->left)                 {                     x   = (x->p);                     right_rotate( r, x);                 }                 (x->p)->clr     = BLACK;                 (x->p->p)->clr  = RED;                 left_rotate( r, (x->p->p));             }         }     }     // correct the lone violation of property 2.     (r->r)->clr = BLACK; }

 

4. 실행 결과

아래 캡쳐 화면은 실행결과이다. 맨 좌측에서 우측으로, 루트 노드부터 자노드들 순서이며,

키 값 뒤에는 색상을 의미한다. R = RED, B = BLACK