[DevLog][DS]Red Black Tree: Operation

Red Black Tree

1. Concept [revisited]

다음과 같은 성질을 만족하는 이진 검색 트리 BST

1. 모든 노드는 red or black
2. root 노드는 black
3. leaf (nil)노드는 black
4. red 노드의 자식은 black
5. 한 노드에서 leaf(nil)로 가는 각 경로에 포함된 black 노드의 개수는 모두 같다.

2. Operations

typedef enum {RBTREE_BLACK, RBTREE_RED} color_t;
typedef int key_t;

typedef struct node_t {
    key_t key;
    color_t color;
    struct node_t* parent;
    struct node_t* left;
    struct node_t* right;
}

typedef struct rbtree {
    node_t* root;
    node_t* nil;
}    

위와 같은 구조를 가정하자. 다음과 같은 연산이 red black 트리의 기본 연산이다.

rbtree* new_rbtree();
void free_rbtree(rbtree*);

node_t* rbtree_insert(rbtree*, key_t);
int* rbtree_delete(rbtree*, node_t*);
node_t* rbtree_find(const rbtree*, key_t);
node_t* rbtree_min(const rbtree*);
node_t* rbtree_max(const rbtree*);

int rbtree_to_array(rbtree*, key_t*, int);

1. new_rbtree: 트리의 생성
2. free_rbtree: 트리의 삭제 (메모리 해제)
3. rbtree_insert: 트리에 새로운 노드 삽입
4. rbtree_delete: 트리에 있는 노드 삭제
5. rbtree_find: 트리에서 키 값을 갖는 노드 검색
6. rbtree_min/rbtree_max: 트리의 최소/최대값 반환
7. rbtree_to_array: 트리를 키 값 오름차순으로 배열에 담아 반환

이중에서 find, min/max, array 연산은 read-only 연산으로, 일반 이진검색트리와 동일하게 처리해줄 수 있다. 트리의 생성과 삭제 역시 마찬가지다. 중요한 부분은 노드의 삽입/삭제 연산인데, 이는 트리에 변화를 가하는 연산으로서 연산 후에도 red black 성질을 만족할 수 있도록 보장해야 하기 때문이다.

3. Insertion 삽입

1. Basic Idea

1. 일반 이진 탐색 트리와 같이 노드를 삽입할 곳을 찾는다.
2. 삽입한 노드가 red black 속성을 위반하는지 검사한다.
3. 위반할 경우, 속성을 복구한다.

2. Rule Violation

새로운 노드의 색을 red로 설정하고 삽입시키므로, 두 가지 속성이 위반될 수 있다.

1. Rule 2: 루트를 삽입했다면, 루트가 black이어야 한다는 속성을 위반한다.
2. Rule 4: red인 노드의 자식으로 새로운 노드를 삽입할 수 있다.

이 두 가지 위반은 동시에 일어나지 않는다 즉 2가 위반되면 4는 지켜지는데, 이는 2가 발생하는 경우는 빈 트리에 루트가 삽입되는 경우밖에 없기 때문이다. 또한 4가 발생하는 경우, red 노드는 루트가 될 수 없고, 속성 위반은 새로운 노드와 그 부모 사이에서만 일어나므로 루트가 black이어야 한다는 2번 규칙은 지켜지게 된다.

만약 삽입한 노드 z의 부모가 black 노드라면, 속성을 위반하지 않는다. 위 경우가 발생하지 않기 때문이다. 그러나 삽입한 노드 z의 부모가 red라면, fixup 연산을 통해 위 두 가지 위반을 검사하고 수정해야 한다. fixup의 케이스는 총 6개로, 1-3케이스는 4-6케이스와 대칭이다.

rbtree_insert_fixup(t, z)
    while z.parent.color == RED
        if z.parent == z.parent.parent.left
            u = z.parent.parent.right           // uncle
            if u.color == RED                   // case 1
                z.parent.color = BLACK
                u.color = BLACK
                z.parent.parent.color = RED
                z = z.parent.paret
            else if z = z.parent.right          // case 2
                    z = z.parent
                    rotate_left(t, z)
                z.parent.color = BLACK          // case 3
                z.parent.parent.color = RED
                rotate_right(t, z.parent.parent)
      else
          if z.parent == z.parent.parent.right
            u = z.parent.parent.left // uncle
            if u.color == RED                   // case 4
                z.parent.color = BLACK
                u.color = BLACK
                z.parent.parent.color = RED
                z = z.parent.parent
            else if z = z.parent.left           // case 5
                    z = z.parent
                    rotate_right(t, z)
                z.parent.color = BLACK          // case 6
                z.parent.parent.color = RED
                rotate_left(t, z.parent.parent)

    t.root.color = BLACK

👀 while 루프 안에서 z.parent.parent가 항상 존재하는 이유는? while 루프로 진입함과 동시에 z와 z.parent의 색은 RED임이 보장된다. 삽입 연산 이전의 트리는 red black의 성질을 만족하므로 z.parent.parent는 black이고, 항상 존재한다. (red인 z.parent가 root가 될 수 없기 때문이다.)

대칭인 1-3만 보인다. 먼저 삼촌 노드를 정의한다.
u = x.parent.parent.right (x.parent.parent.left = x.parent인 경우)

CASE 1: u가 red인 경우

• z.parent.color = BLACK
• u.color = BLACK
• z.parent.parent.color = RED
• z = z.parent.parent

CASE1에서는 red parent - red child인 경우를 해소한다. 그리고 z = z.parent.parent를 통해 2단계 위로 올라간다. 만약 올라간 z의 부모가 red라면 while에 다시 진입하고, 아닐 경우 종료한다.

CASE 2: u가 black이고 z가 부모의 right child인 경우

• z = z.parent
• rotate_left(t, z);

CASE2는 CASE3를 예비한다. z를 한 단계 위로 올려준 후 left로 돌린다. z를 한단계 위로 올리는 이유는, CASE3 진입을 위해 z와 z.parent가 red인 상황을 만들어야 하기 때문이다.

CASE 3. u가 black이고 z가 부모의 left child인 경우

• z.parent.color = BLACK
• z.parent.parent.color = RED
• rotate_right(t, z.parent.parent)

CASE3는 위의 과정을 통해 red parent - red child의 위반을 해결한다.

🤔 root가 red인 위반은 어떻게 해소될까? z == root인 경우 z.parent.color == RED라는 조건에 부합하지 않으므로 while문에 진입하지 않는다. 그리고 마지막 라인인 t.root.color = BLACK을 통해 위반을 해소한다.

4. Deletion 삭제

1. Basic Idea

1. 일반 이진 탐색 트리와 같이 노드를 삭제한다.
2. 삭제된 노드를 대체하는 노드가 red black 속성을 위반하는지 검사한다.
3. 위반할 경우, 속성을 복구한다.

2. Rule Violation

삭제 연산은 삽입보다 속성을 위반할 수 있는 경우가 더 많다. 위반가능성은 삭제된 노드의 색에 의존한다. 노드를 삭제할 때 발생할 수 있는 속성 위반을 검토하기 위해, 삭제 상황에서 세 가지의 구분이 필요하다.

이름	설명
z	내가 삭제하려는 key값을 가진 노드
y	트리에서 삭제되는 노드
x	삭제된 자리를 대체하는 노드

[일반 이진검색트리의 삭제 연산]

1. leaf 노드일때는 삭제한다.
2. 자식이 하나만 있을 때는 자식을 자신의 위치로 교체하고 자신을 삭제한다.
3. 자식이 둘 다 있을 때는 오른쪽 서브트리에서 최솟값을 찾아 자신과 교체하고 최솟값 노드를 삭제한다.
   3.1. 최솟값 노드는 left 자식을 갖지 않기 때문에 항상 1번 또는 2번 케이스에 해당한다.
   3.2. 자신의 왼쪽 서브트리에서 최댓값을 찾아 교체해도 된다. 이 경우에도 최댓값 노드는 right자식을 갖지 않는다.

일반 이진검색트리에서 노드를 삭제할 때, 1번, 2번 케이스에 해당하는 경우 z와 y는 서로 같다. 이 경우 y = z 로 보고, x = y.child 로 설정해 준다. 그러나 3번 케이스에서는 z와 y를 구분해야 한다. z의 위치에 y = 오른쪽 서브트리의 최솟값이 옮겨지고, 결국 삭제되는 것은 y이므로 y의 자리를 대체하는 x는 x = y.right 이 되어야 한다.

위 그림에서 키값이 1인 노드나 2인 노드의 경우, 그 자신이 삭제되는 노드이다. 하지만 12를 키값으로 갖는 노드를 삭제하는 과정 중에 정말로 삭제되는 노드는 12의 오른쪽 서브트리의 최솟값인 14다. 따라서 y를 14번 노드로 설정하고, y의 색을 보아야 한다. red black 트리의 가장 핵심적인 조건인 한 노드에서 리프까지로 가는 각 경로의 black height가 모두 같다는 조건을 지키기 위해서는, 실제로 삭제되는 (그래서 그 자식과 부모가 서로 연결되는) 노드의 색이 중요하기 때문이다.

노드를 삭제할 경우, 삭제되는 노드의 색이 black인지, red인지에 따라 속성 위반 여부가 결정된다. 만약 삭제된 노드가 red인 경우에는 위반이 발생하지 않는데, 그 이유는 다음과 같다.

삭제된 노드 y가 red라고 할 때,

1. y.parent 에서 서브트리로 가는 각 경로의 black height는 변함이 없으므로 5번 속성이 보존된다.
2. y.color == red이므로, y.left/y.right와 y.parent의 색은 black이다. 따라서 y가 삭제되고, y의 자식 중 하나가 y를 대체하게 되어도 속성4를 위반하지 않는다.
3. y는 leaf 또는 root가 아니므로 2, 3번 속성이 보존된다. 색의 변화가 없으므로 1번 속성도 마찬가지.

하지만 삭제된 노드가 black이라면, 삭제 후 red black의 속성을 복구하는 연산이 필요하다.

1. Rule 2: 삭제된 노드가 루트인 경우, 루트가 black이어야 한다는 조건이 위반될 수 있다.
2. Rule 4: 한 노드가 삭제되고 나서 그 자식과 부모가 연결되었을 때, Red의 자식이 Red인 경우가 발생할 수 있다.
3. Rule 5: 한 노드가 삭제되고 나서, 그 부모로부터 리프로 가는 black height이 서로 달라질 수 있다.

Rule 5의 위반을 수정하기 위해, y를 대체하는 노드 x에 여분의 black을 추가해줄 수 있다. 즉, x를 포함하여 리프까지의 경로에 포함되는 black의 수를 black_count라고 할 때, 현재 x의 black parent가 삭제된 상황이기 때문에, x의 black_count는 x의 형제 노드 w의 black_count보다 1만큼 적다. 따라서, x에 여분의 black을 추가해줌으로서 black_count를 1 증가시킨다. 이러한 노드를 double black이라고 한다. x를 double black으로 하면 5번 규칙은 복구되지만, 모든 노드가 red or black이어야 한다는 1번 규칙은 깨지게 된다.

🤔 double black인 x를 resolve할 수 있는 방법은? x의 형제인 w와 black_count를 동일하게 맞춰주는 것이다. 이는 w를 red로 만들거나, x와 w의 부모를 다르게 한 뒤 x에만 black parent를 붙여 줌으로서 해소될 수 있겠다.

즉, 1번 2번 4번 속성이 깨질 수 있으므로, 삭제된 자리를 새로 차지하게 된 노드 x가 red black 속성을 위반하지 않도록 수정해야 한다. 이를 rbtree_delete_fixup이라고 할 때, fixup의 케이스는 총 8가지로 나뉜다. 삽입과 유사하게, 1-4는 5-8과 대칭이다.

if y.color == black
    rbtree_delete_fixup(t, x)

...

rbtree_delete_fixup(rbtree* t, node_t* x)
    while (x != t.root && x.color == BLACK
        if x == x.parent.left
            w = x.parent.right // sibling
            if w.color == RED
                // case 1
               if w.left.color == BLACK && w.right.color == BLACK
                // case 2
            else
                if w.left.color = BLACK
                    // case 3
                else
                    // case 4
        else
            // symmetric to x == x.parent.left (left -> right)
            // case 5 to 8

    x.color = BLACK

🤔 while문 안에서 w가 항상 nil이 아님을 보일 수 있는가?

1. while문 진입은 1. y.color == BLACK 2. x.color == BLACK을 보장한다.
2. 만약 w == t.nil, y.parent로부터 leaf까지 가는 경로의 black height이 같지 않게 된다. (x가 nil이더라도)
3. 이는 legal한 red black tree의 5번 속성을 위반하므로, 삭제 연산 전 이러한 경우는 발생하지 않는다.
   

---

CASE 0: x의 색이 RED인 경우

x의 색이 red일 경우, while문에 진입하지 않고 x.color를 black으로 바꾸어 준 다음 종료한다. 왜 이게 가능한가? x가 red이고 y의 자리를 대체하므로, 색을 black으로만 바꿔주면 5번 조건의 위반을 해결할 수 있다. 또한 red node는 root또는 leaf가 될 수 없으므로 black으로 바꿔주어도 속성을 위반하지 않는다. (이 경우 fixup 함수에 진입하자마자 while문을 건너뛰고 x.color = BLACK 라인만 수행한 후 종료한다)

나머지 CASE 1-4에서는 x.color == BLACK이다. 또, w를 x의 sibling으로 설정한다. (x == x.parent.left라면 w = x.parent.right)

CASE 1: w의 색이 BLACK인 경우

• w.color = BLACK
• x.parent.color = RED
• rotate_left(t, x.parent)
• w = x.parent.right

CASE 2-4로 가기 위한 단계라고 볼 수 있다. 따라서, w.color를 black으로 바꿔주되, 이 과정에서 속성을 보존하는 것을 목표로 한다. 이 경우, x가 가진 double black은 해소하지 못하고, 필연적으로 다른 단계로 가게 된다.

CASE 2: w의 색이 BLACK이고, w의 자식이 모두 BLACK인 경우

• w.color = RED
• x = x.parent

black_count(x) = black_count(w)-1이므로, w.color를 red로 만듦으로서 double black을 해소할 수 있다. 그리고 x가 다시 x의 부모를 가리키게 만듦으로서 while 조건문 검사를 한다. 만약 x.color가 여전히 black이라면, w.color를 red로 만든 것이 4번 속성에 위배되지 않는다고 확신할 수 있다. 그러나 x.color가 red라면, while문에 다시 진입하지 못하고 마지막 라인인 x.color = BLACK을 수행함으로서 4번 속성을 보존한다.

CASE 3: w의 색이 BLACK이고, w의 오른쪽 자식이 BLACK인 경우

• w.color = RED
• w.left = BLACK
• rotate_right(t, w)
• w = x.parent.right

CASE 4로 가기 위한 단계이다. recoloring & rotation을 통해 w의 오른쪽 자식의 색을 RED로 바꿔준다.

CASE 4: w의 색이 BLACK이고, w의 오른쪽 자식이 RED인 경우 (else)

• w.color = x.parent.color
• w.right.color = BLACK
• x.parent.color = BLACK
• rotate_left(t, x.parent)
• x = t.root

이 경우, 위와 같은 연산을 통해 x의 double black을 제거할 수 있다. (즉, CASE 4는 무조건 while loop를 종료시킨다) 이는 연산을 통해 x에 black parent를 붙여줌으로서 x와 w간의 black_count의 불균형을 해소했기 때문이다.

---

중요한 것은 결국 삽입과 삭제를 하면서 레드 블랙 트리의 속성을 만족시키는 것이다. 그래야만 balanced tree를 위해 5번 속성을 보존할 수 있기 때문이다. 또한, 이 모든 연산이 최대 $O(\logN)$에 수행됨이 중요하다. insert_fixup에서는 CASE1, delete_fixup에서는 CASE2만이 유일하게 z가 상단으로 올라가는 경우이다. 나머지는 모두 상수개의 로테이션과 recoloring만이 수행되므로, 부모 또는 조부 노드로 올라가는 경우의 시간복잡도만 생각할 수 있다. 즉, 트리의 균형을 유지하는 비용 자체가 (fixup의 시간복잡도가) $O(\logN)$이므로 레드 블랙 트리라는 자료구조가 효율성을 달성할 수 있는 것이다.