Red-Black Tree

Red-Black Tree

특징

1. 모든 node는 BLACK 또는 RED의 색을 가진다.
2. root node는 항상 BLACK이다.
3. leaf node도 항상 BLACK이다.
4. RED가 연속되어 있을 수 없다. (부모-자식간)
5. root node부터 leaf node사이의 BLACK의 개수는 동일하다.

• self-balancing BST로 일반 BST와 다르게 5번 규칙에 의해 skewed binary tree가 되지 않음이 보장된다. (삽입/삭제 O(lgN) 보장)

동작

• 색상을 RED = 0, BLACK = 1, DOUBLE-BLACK = 2로 생각하면 이해하기 편하다.

조회

• BST와 동일하게 수행

삽입

• 새로 삽입되는 노드는 항상 RED로 시작한다.

• 부모노드가 조부노드의 왼쪽 자식인 경우를 가정하고 설명(오른쪽일 경우 대칭적으로 수행)

1. 부모노드가 RED인 경우

1-1. 삼촌노드가 RED인 경우

조부노드는 BLACK이므로, 조부노드의 BLACK을 삼촌과 부모노드로 내리고 조부노드를 RED로 바꾼다. 즉, 삼촌=부모=BLACK, 조부=RED

         grand(B)                               grand(R)
       /          \                            /        \
   parent(R)     uncle(R)        =>      parent(B)      uncle(B)
     /                                      /
new_node(R)                           new_node(R)

조부노드가 RED가 되었으므로 조부노드를 기준으로 삽입규칙을 만족하는지 다시 확인한다.(루트에 도달할 시 BLACK으로 바꾸고 종료)

1-2. 삼촌노드가 BLACK인 경우

1-2-1. 새로 삽입한 노드가 부모노드의 오른쪽 자식인 경우

새로 삽입한 노드 기준 시계 반대방향 회전 후 parent기준 1-2-2케이스로 이동

                                           new_node(R)
       parent(R)                              /
      /         \               ->        parent(R)
left_son(B)   new_node(R)                  /
                                      left_son(B)

1-2-2. 새로 삽입한 노드가 부모노드의 왼쪽 자식인 경우

새로 삽입한 노드의 부모를 BLACK으로, 조부노드를 RED로 반전시키고 부모기준 시계방향 회전

       grand(B)
         /                                 parent(B)
      parent(R)              ->           /        \
       /                             new_node(R)  grand(R)
   new_node(R)

2. 부모 노드가 BLACK인 경우 -> DONE

삭제

• 삭제가 일어나면 그 위치를 대체하는 노드는 BST에서의 삭제연산과 동일한 방법으로 찾는다.

• 대체할 노드는 삭제된 노드의 색으로 변경하여 삭제된 노드의 자리에 삽입한다. (엄밀히 말하면 삭제된 노드의 색을 대체할 노드의 색상에 추가한다.)

1. 삭제된 노드가 RED인경우 -> DONE

2. 삭제된 노드가 BLACK인경우

2-1. 대체할 노드의 기존 색이 RED인 경우 -> DONE

2-2. 대체할 노드의 기존 색이 BLACK인 경우

• 삭제된 노드의 색을 DOUBLE-BLACK으로 바꾸고 다음 케이스별로 처리한다.

• DOUBLE-BLACK노드가 부모의 왼쪽인 경우를 가정하고 설명(오른쪽일 경우 대칭적으로 수행)

2-2-1. DOUBLE-BLACK 노드의 형제가 RED인 경우

• 부모의 색을 RED, 형제의 색을 BLACK으로 반전 후, 형제 기준 시계반대방향으로 회전한다. DOUBLE-BLACK노드 기준 2-2-2케이스로 이동

                                              brother_node(B)
        parent(B)                                /
      /           \               ->        parent(R)
new_node(BB)  brother_node(R)                  /
                                      new_node(BB)

2-2-2. DOUBLE-BLACK 노드의 형제가 BLACK인 경우

2-2-2-1. 형제의 양쪽 자식이 모두 BLACK인 경우

DOUBLE-BLACK노드와 형제노드의 BLACK을 부모에게 전달한다.

        parent(?)                               parent(?+B)
      /           \                           /           \
new_node(BB)  brother_node(B)      ->   new_node(B)    brother_node(R)
              /           \                             /             \
        left_son(B)    right_son(B)                left_son(B)    right_son(B)

만약 부모노드의 기존 색이 RED였다면 BLACK으로 변하고 종료되지만, 기존 색이 BLACK이었다면 DOUBLE-BLACK으로 바꾸고 부모노드 기준으로 다시 DOUBLE-BLACK을 처리한다. (루트가 DOUBLE-BLACK인경우 BLACK으로 바꾸고 종료)

2-2-2-2. 형제의 왼쪽 자식이 RED, 오른쪽 자식이 BLACK인 경우

형제의 왼쪽자식과 형제노드를 각각 BLACK, RED로 반전시키고, 형제의 왼쪽자식 기준으로 우회전 한다. 2-2-2-3케이스로 이동

        parent(?)                                    parent(?)
      /           \                                /           \
new_node(BB)  brother_node(B)                new_node(BB)    left_son(B)
              /           \           ->                          \
        left_son(R)    right_son(B)                           brother_node(R)
                                                                    \
                                                                 right_son(B)

2-2-2-3. 형제의 왼쪽자식이 BLACK, 오른쪽 자식이 RED인 경우

형제노드 기준으로 시계반대방향으로 회전한 뒤, (변경 전 기준)부모노드의 색을 형제노드에게, 부모노드와 오른쪽 자식을 BLACK으로 변경한다.

        parent(?)                                       brother_node(B)                           brother_node(?)
      /           \                                     /              \                         /              \
new_node(BB)  brother_node(B)         ->          parent(?)       right_son(R)  ->          parent(B)          right_son(B)
              /           \                      /         \                                 /      \
        left_son(B)    right_son(R)        new_node(BB)  left_son(B)                 new_node(BB)  left_son(B)