레드블랙트리 (red-black tree) 삽입

레드블랙트리는 이진트리이자, 균형을 갖춘트리입니다. C++ 의 map 이 레드블랙트리 기반이며, jemalloc 에서도 사용됩니다.레드블랙트리의 정의는 다음과 같습니다.

1. 모든 노드는 red나 black의 색깔을 갖는다.
2. Root 노드는 항상 black이다.
3. 모든 leaf 노드는 센티넬 노드(sentinel node)로서 black이다. (일단 항상 2개의 다른 값으로 채워질 수 있는 NIL=NULL 자식을 가진다.)
4. Red 노드의 자식은 모두 black이다. (Black의 자식은 black/red 모두 가능)
5. 루트(root)에서 leaf로의 경로를 생각할 때, 모든 경로에 대해서 black의 숫자는 같다. (이것을 black height라고 한다.)

삽입

삽입시에 이진트리와 마찬가지로 자신의 위치를 찾아가서 매달리게되는데, 그 이후에 레드블랙트리의  정의에 맞게끔 재구성이 시작됩니다.

부모가 조부모의 오른쪽 자식인지 왼쪽 자식인지에 따라 두가지의 경우로 나뉘는데 이 두 경우는 서로 정확히 대칭이므로 여기서는 부모가 조부모의 왼쪽 자식인경우 위주로 설명합니다. 레드블랙 트리 삽입을 이해하는데 매우 중요한 포인트 입니다. 대부분의 블로그 설명에서 이거 빼놓은듯 싶네요. 

노드 삽입를 위해서 먼저 binary search tree에 대한 노드 삽입 알고리즘대로 노드를 일단 추가한다. 당연히 새롭게 삽입된 노드는 기존의 센티넬 노드의 자리에 추가되어야 한다. 즉, 새 노드는 두 개의 센티넬 노드를 자식 노드로 갖고 기존 센티넬 노드 자리에 들어가게 된다. 새롭게 삽입된 노드의 색깔은 무조건 R 로 한다. (단, root 노드로 삽입시 B)

A. Root로 삽입

1. void insert_case1(node n)
2. {
3.     if (n->parent == NULL)
4.         n->color = BLACK;
5.     else
6.         insert_case2(n);
7. }

N 이 root로 삽입되었다. 속성 2를 위해 B 로 설정한다.

B. 부모 P가 Black 인 경우

1. void insert_case2(node n)
2. {
3.     if (n->parent->color == BLACK)
4.         return; /* Tree is still valid */
5.     else
6.         insert_case3(n);
7. }

삽입되는 노드는 red로 설정되기 때문에 속성 4를 만족하며 N이 red로 삽입되면서 2개의 black nil 자식을 가지기 때문에 각각의 leaf까지 black의 수는 똑같으므로 속성 5도 만족하며 아직 valid 한 RB 트리.

이 상황에서 다시 노드를 삽입하면...

1. 센티넬 노드 자리에 센티넬 노드를 자식으로 갖는 노드를 추가했기 때문에 속성 1, 2는 만족한다.
2. R로 했기 때문에 속성 3, 5를 만족한다.

위반할 수 있는 속성은 속성 4 밖에 없다. 즉, 다른 속성에 위반되지 않도록 하면서 속성 4 를 만족하도록 트리를 변경해 주면된다. 속성 4 를 위반하는 경우는 새로운 노드의 부모 노드가 R인 경우 밖에 없다. 이 때에 대한 처리 방법은 아래의 C, D의 2가지 경우로 나뉜다.

C. 부모가 R, 삼촌도 R

1. void insert_case3(node n)     // 이미 부모는 R이 판명된 상태
2. {
3.     if (uncle(n) != NULL && uncle(n)->color == RED)
4.     {
5.         n->parent->color = BLACK;
6.         uncle(n)->color = BLACK;
7.         grandparent(n)->color = RED;
8.  
9.         insert_case1(grandparent(n));
10.     }
11.     else
12.         insert_case4(n);
13. }

부모가 R 이라면 할아버지는 반드시 B 여야 한다. (기존 트리가 RB트리 속성을 모두 만족하기 때문에 연속된 R을 갖을 수는 없다.) 부모와 삼촌이 모두 R 이라면 아래의 그림처럼 부모와 삼촌을 B로 바꾸고 할아버지를 R로 바꾼다. 이렇게 하면 모든 노드의 black height는 보전된다.

새롭게 생긴 R 노드, 즉 할아버지 노드에 대해서는 지금 적용한 삽입후 처리 알고리즘을 재귀적으로 적용할 수 있다. 할아버지 노드는 R 노드이고 B 를 자식으로 갖기 때문에 새롭개 삽입된 노드의 특징을 모두 지니기 때문에 같은 알고리즘이 적용될 수 있다. 만약 할아버지 노드가 루트 노드라면 할아버지 노드를 다시 B 로 칠하면 된다. 이 경우는 전체 트리의 black height가 1 증가하게 된다. (X의 black 자식으로 인해 height 1->2로 증가)

D. 부모가 R, 삼촌은 B

1. // 삽입된 노드와 부모, 부모의 부모가 일련의 왼쪽 라인을 타도록...
2. void insert_case4(node n)      
3. {
4.     if (n == n->parent->right && n->parent == grandparent(n)->left)
5.     {
6.         rotate_left(n->parent);
7.         n = n->left;
8.     }
9.     else if (n == n->parent->left && n->parent == grandparent(n)->right)
10.     {
11.         rotate_right(n->parent);
12.         n = n->right;
13.     }
14.     insert_case5(n);
15. }
16.  
17. // 노드와 부모와 부모의 부모, 모두 같은 방향의 자식 관계라면... 색 반전하면서 회전
18. void insert_case5(node n)
19. {
20.     n->parent->color = BLACK;
21.     grandparent(n)->color = RED;
22.  
23.     if (n == n->parent->left && n->parent == grandparent(n)->left)
24.     {
25.         rotate_right(grandparent(n));
26.     }
27.     else
28.     {
29.         /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
30.         rotate_left(grandparent(n));
31.     }
32. }

CASE D-1  (부모의 오른쪽 자식일때)

부모를 중심으로 왼쪽으로 회전한다. 여전히 레드블랙특성 4를 위반한다. CASE D-2 로 이동한다.

CASE D-2 (부모의 왼쪽 자식일때) 

조부를 중심으로 오른쪽으로 회전하고 부모와 조부의 색상을 맞바꾼다.

케이스 D 를 만나면 CASE D-2 의 수선을 마지막으로 상황이 종료된다.

케이스 C 를 만나면 상황이 끝날수도있고, 똑같은 상황이 다른노드에서 다시 시작될수도있다. 

재귀적으로 반복해서 루트까지 올라갈수도있다.

다시 한번 언급하지만  위의 CASE 들은 부모가 조부모의 왼쪽 자식을 기준으로 설명한것이다.

그 반대도 정확히 대칭이므로 반대로 생각하면 된다.

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 를 이용하여 시뮬레이션을 해보았다.

부모가 조부모의 왼쪽 자식인지 오른쪽 자식인지 염두해두고 살펴보자. 

                               100이 추가되며, 루트가 되면서 검정색이 되었다.

                             150이 빨강색 노드로 루트의 오른쪽에 여느 이진트리처럼 배치되었다.

                                 200이 추가된후에  좌회전되며 150이 루트가 되었다.

                               300 이 추가된후에 부모와 삼촌노드가 검정색으로 변경되었다. 

       180이 추가된후에 부모(175)와 삼촌(300) 가 검정이 되고 할아버지(200)이 빨강이 되었다.

다음 160번 노드 인서트되면서 대격변의 시작이다. 눈여겨 살펴보자.

160번 노드 삽입 

      삽입된 노드와 부모가 모두 빨강이라, 부모와 삼촌을 검정으로 바꾸고 할아버지를 빨강으로 바꿈 

할아버지 노드 = 그냥 삽입한 노드로 생각하고 다시 시작.  그 노드와 부모노드가 빨강이다. 

삼촌은 검정이다. 노드는 왼쪽자식이고 부모는 오른쪽 자식이다.  회전한다. 

                                                우회전 후 모습 

  노드와 부모가 모두 빨강, 노드는 오른쪽 자식이다. 부모는 오른쪽 자식이다. 회전을 통해 바로잡는다.

                                               좌화전후 모습 

                                          루트를 검정색으로 바꾸고, 정리한다.

---

레퍼런스:
http://www.yes24.com/24/goods/9345796?scode=032&OzSrank=3  https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
http://egloos.zum.com/sweeper/v/900135
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html