[Algorithm] 레드블랙 트리(red-black tree)

---

레드블랙 트리

 

출처: en.wikipedia.org

자가 균형 이진탐색트리로 특정 규칙을 설정하고, 이를 따르도록 하여 균형을 유지한다. 2-3-4 트리와 매우 유사하며, 모든 레드블랙 트리는 2-3-4 트리와 일대일 대응이 가능하다.

레드블랙 트리는 루트노드에서 리프노드까지 경로에 나타나는 노드의 색을 제한함으로써 그러한 경오 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장하고, 이를 통해 근사적 균형을 항상 보장한다.

레드블랙 트리의 특성은 다음과 같고, 이를 만족하는 이진탐색트리를 레드블랙 트리라 한다.

1. 모든 노드는 적색(red) 혹은 흑색(black)이다.
2. 루트노드는 흑색이다.
3. 모든 리프노드는 흑색이다.
4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
5. 각 노드로부터 그 노드의 자손인 리프노드로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

값이 있는 노드 중 리프노드의 자식노드를 NIL이라 하는데 NULL 노드라 생각하면 된다. 편의상 하나의 NIL 노드를 만들고, 모든 리프노드가 NIL 노드를 가리키게 구현하기도 한다. 이때 NIL 노드는 흑색으로 3번 조건인 모든 리프노드는 흑색이다를 만족하게 된다.

또한 레드블랙 트리 노드는 일반적인 트리와 다르게 부모노드 역시 가리키도록 설계된다.

이를 통해 $ n $ 개의 내부노드르 가지는 레드블랙 트리는 최대 $ 2 \log (n+1) $ 의 높이를 가진다. 엄격하게 균형을 만드는 AVL 트리(참고링크)가 탐색에서는 좀 더 빠르지만, 일반적으로 레드블랙 트리가 삽입 및 삭제에서 효율적이다.

 

---

회전 (Rotation)

 

삽입 및 삭제시 레드블랙 트리의 특성에 위배될 수 있고, 이때 회전을 사용하여 그 특성을 유지한다.

출처: en.wikipedia.org

회전은 위 그림과 같이 이뤄진다. 이 회전은 균형트리 성질을 유지하는 데에 중요한데, 어느 한 쪽 서브트리의 깊이가 너무 길어질 때 회전을 통해 조정하기 때문이다.

위 이미지를 통해서도 알 수 있지만 왼쪽회전(left rotate)를 하면서 L 노드 왼쪽 서브트리는 내려가고, R 노드 오른쪽 서브트리는 올라가는 것을 확인할 수 있다. 즉 L 노드 왼쪽 서브트리의 깊이는 더 깊어지는 대신 R 노드 오른쪽 서브트리의 깊이는 더 얕아지게 된다.

간단하게 코드로 구현하면 다음과 같다.

void left_rotate(Node* &root, Node* &pt) {
    Node* pt_right = pt->right;
    pt->right = pt_right->left;
    if (pt->right != NULL) {
        pt->right->parent = pt;
    }
    pt_right->parent = pt->parent;
    if (pt->parent == NULL) {
        root = pt_right;
    }
    else if (pt == pt->parent->left) {
        pt->parent->left = pt_right;
    }
    else {
        pt->parent->right = pt_right;
    }
    pt_right->left = pt;
    pt->parent = pt_right;
}
void right_rotate(Node* &root, Node* &pt) {
    Node* pt_left = pt->left;
    pt->left = pt_left->right;
    if (pt->left != NULL) {
        pt->left->parent = pt;
    }
    pt_left->parent = pt->parent;
    if (pt->parent == NULL) {
        root = pt_left;
    }
    else if (pt == pt->parent->left) {
        pt->parent->left = pt_left;
    }
    else {
        pt->parent->right = pt_left;
    }
    pt_left->right = pt;
    pt->parent = pt_left;
}

 

---

삽입

 

처음 값을 삽입할 때는 일반적인 이진탐색트리와 마찬가지로 탐색을 진행하고, 그 후 비어있는 공간에 값을 삽입한다. 이때 삽입되는 노드는 적색이 초기값이다. 그런데 여기서 끝나면 앞서 언급한 레드블랙 트리의 특성을 만족하지 못하게 되는 문제가 발생한다. 

다시 조건을 확인하면 다음과 같다.

1. 모든 노드는 적색(red) 혹은 흑색(black)이다.
2. 루트노드는 흑색이다.
3. 모든 리프노드는 흑색이다.
4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
5. 각 노드로부터 그 노드의 자손인 리프노드로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

적색노드가 리프노드에 삽입되었을 때 어떤 문제가 발생할지 생각해보면, 모든 노드는 적색 혹은 흑색이고, 모든 리프노드는 NIL 노드로 흑색이며 삽입된 노드가 적색이기에 각 노드로부터 그 노드의 자손인 리프노드로 가는 경로들은 모두 같은 수의 흑색노드를 포함한다. 즉 문제가 되는 것은 루트 노드가 흑색이 아닐 수 있다는 것과 노드가 적색이면 그 노드의 자식은 모두 흑색이 아닐 수 있다는 것이다.

만약 비어있는 트리에 값을 삽입하면 삽입된 노드는 루트노드가 되는데 이때 삽입된 노드가 적색이므로 이를 수정해주어야 한다. 또한 삽입된 노드의 부모노드가 적색이라면 적색노드의 자식이 적색이 되기 때문에 레드블랙 트리 조건을 만족하지 못하게 된다. 따라서 레드블랙 트리의 조건을 만족시키기 위해 이를 수정하는 함수를 만들고 수정한다.

루트노드가 적색인 것은 단순히 흑색으로 칠하면 되는 문제이니 제외하면, 문제가 되는 적색노드의 자식이 적색인 경우는 총 3가지 케이스로 나뉜다. 이때 부모노드가 조부노드의 왼쪽 자식이라 가정하겠다.

먼저 삼촌노드, 즉 조부노드의 자식노드 중 부모노드가 아닌 노드가 적색인 경우가 첫번째 케이스이다. 이 경우 먼저 부모노드와 삼촌노드를 흑색노드로 만들고 조부노드를 적색노드로 만든 후 조부노드를 기준으로 다시 레드블랙 트리 성질이 유지되나 검사한다.

두번째 케이스는 삼촌노드가 흑색노드이면서 현재노드(지금의 경우는 삽입된 노드)가 부모 노드의 오른쪽 자식인 경우이다. 이 경우 부모노드를 기준으로 왼쪽으로 회전시켜주고 현재노드를 부모노드로 수정해준다.

세번째 케이스는 두번째 케이스 이후 나오게 되는 모양이거나 삼촌노드가 흑색노드면서 현재노드가 부모노드의 왼쪽 자식인 경우이다. 이 경우 조부노드를 기준으로 오른쪽 회전을 해주고, 부모노드와 조부노드의 색을 바꾸면 된다. 현재노드는 부모노드로 업데이트 하고 다시 레드블랙 트리의 성질을 만족하나 검사한다.

코드로 보면 아래와 같다.

void fix_violation(Node* &root, Node* &pt) {
    Node* parent_pt = NULL;
    Node* grand_parent_pt = NULL;
    while ((pt != root) && (pt->color != BLACK) && (pt->parent->color == RED)) {
        parent_pt = pt->parent;
        grand_parent_pt = pt->parent->parent;
        if (parent_pt == grand_parent_pt->left) {
            Node* uncle_pt = grand_parent_pt->right;
            // Case 1: 삼촌 노드가 레드인 경우
            if (uncle_pt != NULL && uncle_pt->color == RED) {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            }
            else {
                // Case 2: pt가 부모의 오른쪽 자식인 경우
                if (pt == parent_pt->right) {
                    left_rotate(parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }
                // Case 3: pt가 부모의 왼쪽 자식인 경우
                right_rotate(grand_parent_pt);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
        else {
            Node* uncle_pt = grand_parent_pt->left;
            if ((uncle_pt != NULL) && (uncle_pt->color == RED)) {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            }
            else {
                if (pt == parent_pt->left) {
                    right_rotate(parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }
                left_rotate(grand_parent_pt);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
    }
    root->color = BLACK;
}

 

---

삭제

 

삭제는 더 많은 케이스에 더욱 복잡한 방식으로 진행되기에 생략하겠다. 아래 코드를 보거나, 위키백과(참고링크)를 참고하면 자세히 설명되어 있다.

 

---

구현

 

#include <iostream>
using namespace std;

enum Color { RED, BLACK };

class Node {
public:
    int key;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

    Node(int key) {
        this->key = key;
        this->color = RED;
        this->left = NULL;
        this->right = NULL;
        this->parent = NULL;
    }
};

class RedBlackTree {
private:
    Node* root;

    void left_rotate(Node* &pt) {
        Node* pt_right = pt->right;
        pt->right = pt_right->left;
        if (pt->right != NULL) {
            pt->right->parent = pt;
        }
        pt_right->parent = pt->parent;
        if (pt->parent == NULL) {
            root = pt_right;
        }
        else if (pt == pt->parent->left) {
            pt->parent->left = pt_right;
        }
        else {
            pt->parent->right = pt_right;
        }
        
        pt_right->left = pt;
        pt->parent = pt_right;
    }

    void right_rotate(Node* &pt) {
        Node* pt_left = pt->left;
        pt->left = pt_left->right;
        if (pt->left != NULL) {
            pt->left->parent = pt;
        }
        pt_left->parent = pt->parent;

        if (pt->parent == NULL) {
            root = pt_left;
        }
        else if (pt == pt->parent->left) {
            pt->parent->left = pt_left;
        }
        else {
            pt->parent->right = pt_left;
        }

        pt_left->right = pt;
        pt->parent = pt_left;
    }

    void fix_violation(Node* &pt) {
        Node* parent_pt = NULL;
        Node* grand_parent_pt = NULL;
        while ((pt != root) && (pt->color != BLACK) && (pt->parent->color == RED)) {
            parent_pt = pt->parent;
            grand_parent_pt = pt->parent->parent;
            if (parent_pt == grand_parent_pt->left) {
                Node* uncle_pt = grand_parent_pt->right;
                if (uncle_pt != NULL && uncle_pt->color == RED) {
                    grand_parent_pt->color = RED;
                    parent_pt->color = BLACK;
                    uncle_pt->color = BLACK;
                    pt = grand_parent_pt;
                }
                else {
                    if (pt == parent_pt->right) {
                        left_rotate(parent_pt);
                        pt = parent_pt;
                        parent_pt = pt->parent;
                    }
                    right_rotate(grand_parent_pt);
                    swap(parent_pt->color, grand_parent_pt->color);
                    pt = parent_pt;
                }
            }
            else {
                Node* uncle_pt = grand_parent_pt->left;
                if ((uncle_pt != NULL) && (uncle_pt->color == RED)) {
                    grand_parent_pt->color = RED;
                    parent_pt->color = BLACK;
                    uncle_pt->color = BLACK;
                    pt = grand_parent_pt;
                }
                else {
                    if (pt == parent_pt->left) {
                        right_rotate(parent_pt);
                        pt = parent_pt;
                        parent_pt = pt->parent;
                    }
                    left_rotate(grand_parent_pt);
                    swap(parent_pt->color, grand_parent_pt->color);
                    pt = parent_pt;
                }
            }
        }
        root->color = BLACK;
    }

    void transplant(Node* u, Node* v) {
        if (u->parent == NULL) {
            root = v;
        }
        else if (u == u->parent->left) {
            u->parent->left = v;
        }
        else {
            u->parent->right = v;
        }
        if (v != NULL) {
            v->parent = u->parent;
        }
    }

    Node* minimum(Node* node) {
        while (node->left != NULL) {
            node = node->left;
        }
        return node;
    }

    void fix_deletion(Node* x, Node* parent) {
        while ((x != root) && (x == NULL || x->color == BLACK)) {
            if (parent->left == x) {
                Node* w = parent->right;
                if (w && w->color == RED) {
                    w->color = BLACK;
                    parent->color = RED;
                    left_rotate(parent);
                    w = parent->right;
                }
                if ((w->left == NULL || w->left->color == BLACK) && (w->right == NULL || w->right->color == BLACK)) {
                    if (w) {
                        w->color = RED;
                    }
                    x = parent;
                    parent = x->parent;
                }
                else {
                    if (w->right == NULL || w->right->color == BLACK) {
                        if (w->left) {
                            w->left->color = BLACK;
                        }
                        w->color = RED;
                        right_rotate(w);
                        w = parent->right;
                    }
                    if (w) {
                        w->color = parent->color;
                    }
                    parent->color = BLACK;
                    if (w->right) {
                        w->right->color = BLACK;
                    }
                    left_rotate(parent);
                    x = root;
                    break;
                }
            }
            else {
                Node* w = parent->left;
                if (w && w->color == RED) {
                    w->color = BLACK;
                    parent->color = RED;
                    right_rotate(parent);
                    w = parent->left;
                }
                if ((w->left == NULL || w->left->color == BLACK) && (w->right == NULL || w->right->color == BLACK)) {
                    if (w) {
                        w->color = RED;
                    }
                    x = parent;
                    parent = x->parent;
                }
                else {
                    if (w->left == NULL || w->left->color == BLACK) {
                        if (w->right) {
                            w->right->color = BLACK;
                        }
                        w->color = RED;
                        left_rotate(w);
                        w = parent->left;
                    }
                    if (w) {
                        w->color = parent->color;
                    }
                    parent->color = BLACK;
                    if (w->left) {
                        w->left->color = BLACK;
                    }
                    right_rotate(parent);
                    x = root;
                    break;
                }
            }
        }
        if (x) x->color = BLACK;
    }

public:
    RedBlackTree() {
        root = NULL;
    }

    void insert(int key) {
        Node* pt = new Node(key);
        Node* parent = NULL;
        Node* curr = root;
        while (curr) {
            parent = curr;
            if (pt->key < curr->key) {
                curr = curr->left;
            }
            else if (pt->key > curr->key) {
                curr = curr->right;
            }
            else {
                delete pt;
                return;
            }
        }
        pt->parent = parent;
        if (!parent) {
            root = pt;
        }
        else if (pt->key < parent->key) {
            parent->left = pt;
        }
        else {
            parent->right = pt;
        }
        fix_violation(pt);
    }

    void remove(int key) {
        Node* z = root;
        while (z && z->key != key) {
            if (key < z->key) {
                z = z->left;
            }
            else {
                z = z->right;
            }
        }
        if (!z) {
            return;
        }
        Node* y = z;
        Color y_original_color = y->color;
        Node* x = NULL;
        Node* x_parent = NULL;
        if (!z->left) {
            x = z->right;
            x_parent = z->parent;
            transplant(z, z->right);
        }
        else if (!z->right) {
            x = z->left;
            x_parent = z->parent;
            transplant(z, z->left);
        }
        else {
            y = minimum(z->right);
            y_original_color = y->color;
            x = y->right;
            if (y->parent == z) {
                x_parent = y;
            }
            else {
                x_parent = y->parent;
                transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
            transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }
        delete z;
        if (y_original_color == BLACK) {
            fix_deletion(x, x_parent);
        }
    }
};