[비선형 자료구조] 트리(4) - Red-Black(RB) 트리

저번 포스팅에선 AVL 트리에 대해 알아보았다.

[비선형 자료구조] 트리 링크

트리(1) - 이진 트리(Binary Tree)

트리(2) - 이진탐색트리

트리(3) - AVL 트리

이번 포스팅에서는 AVL 트리와 같이 자기 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)의 종류중 하나인 Red-Black 트리에 대해 알아보자. 마찬가지로 O(logN)의 시간복잡도를 가진다. 

 

Red-Black Tree(RB tree)

여러개의 규칙으로 이루어진 트리로 다소 이해하기 어려운 면이 있다. AVL 트리보다 균형을 맞추는 방법이 직관적이지는 않다.자바의 TreeSet과 TreeMap은 Red-Black 트리를 베이스로 한 구현을 사용한다.

RB 트리는 다음과 같은 조건을 만족해야 한다.

RB 트리 예시

• 모든 노드는 red 혹은 black의 색을 가진다.
• root 노드와 leaf 노드(NIL)는 Black이다.
• red 노드의 자식은 black 노드이다.(double red 불가능)
• 모든 leaf 노드에서 root 노드까지 가는 경로의 black 노드 수는 같다.(black depth)

NIL은 RB 트리에서 사용되는 leaf 노드로 규칙을 위한 자료를 갖지 않고 트리의 끝을 나타내는 노드이다. 간단히 Null Node라고 이해하면 편하다. 다른 트리에서 leaf 노드인 것 아래에 NIL이 붙어있다. NIL을 직접적으로 그려서 보여주지 않아도 비어있는 자리에는 NIL(black node)이 있다고 생각하면 된다.

색을 가진다는 것은 실질적으로 칠하는건 아니고 클래스를 구성할 때 거기에 색깔변수를 만들어서 걔가 black이냐 red냐 그런 구분으로 규칙을 맞춰나가는데 사용한다.

위 조건이 깨지면 리밸런싱(Rebalancing)을 진행한다.

 

삽입(Insert)

처음 들어오는 노드는 모두 red로 들어오고 이후에 바뀌기 때문에 double red가 발생할 수 있다. 이 경우, 부모 노드의 형제 노드의 색에 따라 해야할 일이 조금 달라진다.

삽입 case 1 (부모 노드의 형제 노드가 red 일 때)

부모 노드의 형제 노드가 red일 경우, Recoloring 작업을 수행한다. Recoloring은 말 그대로 색을 칠하는 것이다. Recoloring 작업 순서는 다음과 같다.

삽입 case 1 예시

1. 삽입 노드의 부모 노드와 부모 노드의 형제 노드를 black으로 바꾼다.
2. 부모 노드의 부모 노드를 red로 바꾼다.(부모의 부모가 root라면 다시 black으로 바뀐다.)
3. 부모의 부모 노드가 red로 바뀌었을 때, 부모의 부모의 부모 노드가 존재하고, red라면 위쪽에서 또 double red가 발생한다. 이 경우, case에 맞춰서 Recoloring 혹은 Restructuring을 진행해준다. root를 만나거나, double red가 발생하지 않는 경우, 작업이 종료된다.

말이 좀 어려울 수 있는데 그냥 double red가 없어질 때까지 작업을 반복해준다고 생각하면 된다.

삽입 case 2 (부모 노드의 형제 노드가 black 혹은 NIL일 때)

부모 노드의 형제 노드가 black 혹은 NIL일 때는 Restructuring 작업을 수행한다. 이 작업은 다음과 같은 과정을 거친다.

1. 삽입 노드, 부모 노드, 부모의 부모 노드를 오름차순 정렬한다.
2. 오름차순 정렬된 노드들 중 가운데 노드를 부모 노드로 하고, Restructuring을 한다. 위 그림을 예로 들면 20, 25, 30이니까 25가 부모노드, 나머지 둘이 자식 노드가 되는 것이다.
3. 부모 노드를 black, 자식 노드를 red로 칠한다.

삭제(Delete)

삭제에서 처리해줘야 하는 경우는 Double black case이다. double black 노드는 삭제 대상 노드가 black인데 삭제 후 그 자리에 오는 노드도 black인 case를 말한다. 예를 들어, 아래 예시에서 5를 지운다고 하면 5를 지우고 NIL이 오는데 NIL은 흑색노드니까 black 자리에 black이 오는 double black case라는 것이다.

삭제(기본)

삭제(기본) 예시

삭제 대상 노드가 black 이고 그 자리에 오는 노드가 red인 경우에는 자리에 온 노드를 black으로 바꾼다. (그대로 두면 double red 이기 때문)

삭제 case 1

double black 노드(삭제 대상 노드가 있던 위치)의 형제 노드가 black이고, 형제의 양쪽 자식 모두 black인 경우이다. 

이 경우, 다음과 같은 과정을 거친다.

1.  형제 노드를 red로 변경한다.
2.  이중 흑색 노드의 검은색 1개를 부모 노드로 전달한다.
3.  부모가 root가 아닌 이중 흑색 노드가 되면 해당 case 반복한다.(root 만나면 종료)

예시의 5를 삭제하면 NIL이 남는데 이 검은색 NIL을 위로 올린다는 것이다. 그럼 10에서도 double black이 된다. root가 아닌데 이런 double black 노드가 되면 이런식으로 root 전까지 반복해준다. 10에서도 같은 double black case가 적용되므로 50을 red로 바꿔주고 위로 올리는데 root이므로 끝이 난다.

삭제 case 2

double black 노드(삭제 대상 노드가 있던 위치)의 형제 노드가 red인 경우이다.

이 경우, 다음과 같은 과정을 거친다.

1. 형제 노드를 black으로 변경한다.
2. 부모 노드를 red로 변경한다.
3. 부모 노드를 기준으로 왼쪽으로 회전한다.(Left Rotation)
4. 그 다음 case 에 따라 반복 진행한다.

예시에서 10을 삭제하면 10이 NIL이 되는데 이건 black 노드라 double black 노드가 되는데 이 형제노드인 50이 red이다. 이 형제노드(50)을 black으로 바꾸고 부모노드(30)를 red로 바꾼다. 그 다음에 부모 노드를 기준으로 왼쪽으로 회전한다. 30(원래부모노드)의 오른쪽은 아래노드(50)의 왼쪽 노드(40)가 붙는다.

그러고 나면 예시는 double black case 1의 경우가 나온다. 그걸 적용하면 된다.

회전은 이전 포스팅인 AVL 트리에서 자세하게 다루었으므로 잘 모르겠다면 참고하면 좋다.

트리(3) - AVL 트리

삭제 case 3-1

double black 노드(삭제 대상 노드가 있던 위치)의 형제 노드가 black이고, 형제의 오른쪽 자식이 모두 red인 경우이다. 

이 경우, 다음과 같은 과정을 거친다.

1. 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경한다.
2. 부모 노드를 기준으로 왼쪽으로 회전한다.(Left Rotation)

double black 노드의 형제 노드가 black이고 이 형제 노드의 오른쪽 자식이 red인 경우이다. 이때는 부모 노드(30)와 형제 노드의 오른쪽 자식 노드(60) 두 노드를 검은색으로 변경한다. 그리고 부모 노드를 기준으로 왼쪽으로 회전시킨다.

삭제 case 3-2

double black 노드(삭제 대상 노드가 있던 위치)의 형제 노드가 black이고, 형제의 왼쪽 자식이 red인 경우이다. 

이 경우, 다음과 같은 과정을 거친다.

1. 형제 노드를 red 로 변경한다.
2. 형제 노드의 왼쪽 자식 노드를 black 으로 변경한다.
3. 형제 노드를 기준으로 오른쪽으로 회전한다.
4. case 3-1을 진행한다.

double black 노드의 형제 노드가 black이고, 이 형제 노드의 왼쪽 자식이 red인 경우이다. 형제 노드를 red로 바꾸고, 형제 노드의 왼쪽 자식 노드를 black으로 바꾼다. 그리고 형제 노드를 기준으로 오른쪽으로 회전시킨다. 그리고 double black case 3-1과 같아지므로 그걸 적용시켜주면 된다.

 

Red-Black Tree vs AVL Tree

• 알고리즘 시간 복잡도는 둘다 O(logN)이다. (이진 탐색 트리 형태를 가지기에)
• 균형 수준으로는 AVL 트리가 아무래도 좌우 depth 차이를 가지고 삽입, 삭제시마다 전 노드에 대해서 recursive하게 확인하면서 균형을 잡아가기에 RB 트리보다는 좀더 엄격하게 균형을 잡는다.
• RB트리는 색으로 구분하고 넘어가는 경우도 있기 때문에 균형수준은 AVL보다 떨어지지만 회전 수 연산이 감소한다.
• 어떤 데이터들이 쭉 주어진 상황에서 트리 체계가 한번 잡힌 다음에는 거의 탐색이 주로 사용된다고 한다면 아무래도 이진 탐색 트리를 하기 좋게 균형이 다 잡혀있는 case인 AVL이 좋다. 좀더 균형이 잡혀있는 AVL이 탐색이 몇 번이든 더 적을테니 말이다.
• 삽입, 삭제가 빈번한 경우에는 RB 트리가 유리하다고 한다. 일반적으로 데이터는 변화가 없는 케이스보다는 삽입, 삭제가 빈번한 경우가 많기 때문에 일반적으로는 균형을 찾는 이 트리 방법에서는 RB 트리를 좀더 많이 사용한다고 한다.

RB 트리 삽입 구현(java)

class Node {
    int key;
    int color;
    Node left;
    Node right;
    Node parent;

    public Node(int key, int color, Node left, Node right, Node parent) {
        this.key = key;
        this.color = color;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

class RedBlackTree {
    static final int BLACK = 0;
    static final int RED = 1;

    Node head;

    public void insert(int key) {
        Node checkNode = null; // rebalancing 대상 노드
        if (this.head == null) { // head(root)는 black
            this.head = new Node(key, BLACK, null, null, null);
        } else {
            Node cur = this.head;

            // 추가할 위치 탐색
            while (true) {
                Node pre = cur;

                if (key < cur.key) {
                    cur = cur.left;
                    if (cur == null) {
                        // 추가할 때는 먼저 red
                        pre.left = new Node(key, RED, null, null, pre);
                        // 추가한 노드를 rebalancing 대상의 노드로 짚어줌
                        checkNode = pre.left;
                        break;
                    }
                } else {
                    cur = cur.right;

                    if (cur == null) {
                        pre.right = new Node(key, RED, null, null, pre);
                        checkNode = pre.right;
                        break;
                    }
                }
            }
            // 추가 후 rebalancing
            reBalance(checkNode);
        }
    }

    public void reBalance(Node node) {
        // 추가한 노드의 부모가 있고 그 부모가 red 일 때 조정 필요
        while (node.parent != null && node.parent.color == RED) {
            Node sibling = null;

            // 부모 노드의 형제 노드 찾기
            if (node.parent == node.parent.parent.left) {
                sibling = node.parent.parent.right;
            } else {
                sibling = node.parent.parent.left;
            }

            // 부모 노드의 형제 노드가 Red 일 때 recoloring
            if (sibling != null && sibling.color == RED) {
                // 부모 노드 black 으로 변경
                node.parent.color = BLACK;
                // 부모 노드의 형제 노드 black 으로 변경
                sibling.color = BLACK;
                // 부모의 부모 노드는 red 로 변경
                node.parent.parent.color = RED;

                // 부모 노드가 root 인 경우는 다시 black 으로 바꾸고 break
                if (node.parent.parent == this.head) {
                    node.parent.parent.color = BLACK;
                    break;
                } else { // 부모 노드가 root 가 아닌 경우는 double red 재발생 할 수 있으므로 반복 검사
                    node = node.parent.parent;
                    continue;
                }
            } else { // 부모 노드의 형제 없거나 black 일 때, restructuring
                if (node.parent == node.parent.parent.left) {
                    // lr case 인 경우 우선 ll case 가 되도록 회전
                    if (node == node.parent.right) {
                        node = node.parent;
                        leftRotate(node);
                    }
                    // 부모 노드는 black 으로 변경
                    node.parent.color = BLACK;
                    // 부모의 부모 노드는 red 로 변경
                    node.parent.parent.color = RED;
                    rightRotate(node.parent.parent);
                } else if (node.parent == node.parent.parent.right) {
                    // rl case 인 경우 rr case 가 되도록 회전
                    if (node == node.parent.left) {
                        node = node.parent;
                        rightRotate(node);
                    }
                    node.parent.color = BLACK;
                    node.parent.parent.color = RED;
                    leftRotate(node.parent.parent);
                }
                break;
            }
        }
    }

    public void leftRotate(Node node) {
        // node 가 head 인 경우 회전 후 head 교체
        if (node.parent == null) {
            Node rNode = this.head.right;
            this.head.right = rNode.left;
            rNode.left.parent = this.head;
            this.head.parent = rNode;
            rNode.left = this.head;
            rNode.parent = null;
            this.head = rNode;
        } else {
            // 회전하기 전 자식 노드있는 경우 이동하는 작업
            if (node == node.parent.left) {
                node.parent.left = node.right;
            } else {
                node.parent.right = node.right;
            }
            node.right.parent = node.parent;
            node.parent = node.right;

            if (node.right.left != null) {
                node.right.left.parent = node;
            }
            node.right = node.right.left;
            node.parent.left = node;
        }
    }

    public void rightRotate(Node node) {
        // node 가 head 인 경우 회전 후 head 교체
        if (node.parent == null) {
            Node lNode = this.head.left;
            this.head.left = lNode.right;
            lNode.right.parent = this.head;
            this.head.parent = lNode;
            lNode.right = this.head;
            lNode.parent = null;
            this.head = lNode;
        } else {
            if (node == node.parent.left)
                node.parent.left = node.left;
            else
                node.parent.right = node.left;

            node.left.parent = node.parent;
            node.parent = node.left;

            if (node.left.right != null)
                node.left.right.parent = node;

            node.left = node.left.right;
            node.parent.right = node;
        }
    }
}