[자료구조 with JAVA] 이진 탐색 트리 - Red Black Tree

01. Red-Black Tree

• 조건
  1. Root 노드와 Leaf 노드의 색: Black
  2. Red 색 노드의 자식의 색: Black (Double Red 불가)
  3. 모든 Leaf 노드에서 Root 노드까지 가는 경로의 Black 노드 수 같음
• 조건이 깨지는 상황: Rebalancing 실행 

02. 삽입

1. (case 1) 노드 삽입 후 Double Red 발생 1: 부모 노드의 형제 노드가 Red인 경우
   • ReColoring 진행
     • 삽인한 노드의 부모와 부모 형제 노드를 Black으로 변경
     • 부모의 부모 노드를 Red로 변경
     • 부모의 부모 노드가 Root인지 Double Red인지에 따라 조건 진행
2. (case 2) 노드 삽입 후 Double Red 발생 2: 부모 노드의 형제 노드가 Black or Null
   • ReStructuring 진행
     • 조정 대상: 삽입한 노드(cur), 부모 노드(parent), 부모의 부모 노드(p.p)
     • 조정 대상 노드를 오름차순 정렬
     • 가운데 노드를 부모 노드(parent)로 선정 → Black
     • 나머지 두 노드를 자식 노드로 선정 → Red

03. 삭제

• (기본) 삭제 대상 노드: Black, 그 자리에 오는 노드: Red
  • 해당 자리로 오는 Red → Black으로 변경
• (이중 흑색 case)
  1. (이중 흑색 case 1) 삭제 대상 노드: Black, 그 자리에 오는 노드: Black
     
     • 이중 흑색 노드의 형제 노드: Black, 형제의 양쪽 노드: Black인 경우
       • 형제 노드: Red로 변경
       • 이중 흑색 노드의 검은색 1개를 부모 노드에 전달
       • 부모 노드가 Root가 아닌 이중 흑생 노드가 될 경우 (이중 흑색 case 1) 반복
  2. (이중 흑색 case 2) 이중 흑색 노드의 형제 노드가 Red인 경우
     • 형제 노드: Black 변경
     • 부모 노드: Red 변경
     • 부모 노드 기준으로 왼쪽으로 회전
     • 그 다음 (이중 흑색 case)에 따라 진행
  3. (이중 흑색 case 3-1) 이중 흑색 노드의 형제 노드: Black, 오른쪽 자식 노드: Red
     • 부모 노드, 형제 노드의 오른쪽 자식 노드: Black
     • 부모 노드를 기준으로 왼쪽으로 회전
  4. (이중 흑색 case 3-2) 이중 흑색 노드의 형제 노드: Black, 왼쪽 자식 노드: Red
     • 형제 노드: Red
     • 형제 노드의 왼쪽 자식 노드: Black
     • 형제 노드 기준으로 오른쪽으로 회전
     • (이중 흑색 3-1) 진행

04. Red-Black Tree vs AVL Tree

• 알고리즘 시간복잡도: 둘 다 O(logN)
• 균형 수준
  • 엄격도: AVL Tree > Red-Black Tree
  • Red-Black Tree: 색으로 구분하는 경우로 인해 회전 수 감소
• 실 사용시
  • Tree 체계 잡힌 후, 탐색 많을 경우: AVL Tree
  • 삽입 / 삭제 빈번한 경우: Red-Black Tree

05. JAVA로 구현하기

---

(1) 노드 구현

// 노드 구현
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;
    }
}

---

(2) Red-Black Tree  구현

// Red-Black Tree 구현
class RedBlackTree{
    final int BLACK = 0;  //Black을 0으로 지정
    final int RED = 1;  //Red를 1로 지정

    Node head;  //Tree의 root 노드 정보

    // 값을 트리에 추가하는 기능
    public void insert(int key){
        Node checkNode = null;
        if(this.head == null){  //만약 트리가 비어있다면
            this.head = new Node(key, BLACK, null,null,null);  //Black으로 헤드에 추가
        } else {  //트리가 비어있지 않다면
            Node cur = this.head;  //루트 노드부터 탐색

            while(true){
                Node pre = cur;  //pre 변수에 현재 노드의 정보를 저장
                if(key < cur.key){  //찾는 값 < 현재 노드의 값
                    cur = cur.left;  //왼쪽으로 이동
                    if(cur == null){  //왼쪽 노드가 비어있다면
                        pre.left = new Node(key, RED, null,null, pre);  //왼쪽 노드에 추가
                        checkNode = pre.left;  //rebalancing check -> 추가했으므로 리밸런싱이 필요한지 체크함
                        break;
                    }
                } else {  //찾는 값 >= 현재 노드의 값
                    cur = cur.right;   //오른쪽으로 이동
                    if(cur == null){  //오른쪽 노드가 비어있다면
                        pre.right = new Node(key, RED,null,null,pre);  //오른쪽 노드에 추가
                        checkNode = pre.right;  //rebalancing check -> 추가했으므로 리벨런싱이 필요한지 체크
                        break;
                    }
                }
            }
            reBalance(checkNode);  //리벨런싱 체크
        }
    }

    // 추가된 노드를 리벨런싱함
    public void reBalance(Node node){
        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;  //형제 노드 <- 반대쪽(부모의 왼쪽 형제 노드자리) 저장
            }

            //(case 1) 부모의 형제 노드가 red인 경우 -> recoloring 
            if(sibling != null && sibling.color == RED){
                node.parent.color = BLACK;  //부모의 색을 Black으로 변경
                sibling.color = BLACK;  //부모의 형제 노드의 색도 Black으로 변경
                node.parent.parent.color = RED;  //부모의 부모의 색은 Red로 변경

                if(node.parent.parent == this.head){  //만약 부모의 부모가 루트 노드인 경우
                    node.parent.parent.color = BLACK;  //루트의 색은 Black이어야 함
                    break;
                }else{  //루트 노드가 아님
                    node = node.parent.parent;  //현재 노드 <- 노드의 부모의 부모
                    continue;
                }
            } else {  //(case 2) 형제 노드가 black 또는 null -> Structuring
                if(node.parent == node.parent.parent.left){  //부모 노드 위치 == 부모 노드의 왼쪽 형제 자리
                    //LR case -> LL case가 되도록
                    if(node == node.parent.right){
                        node = node.parent;
                        //회전
                        leftRotate(node);
                    }
                    node.parent.color = BLACK;  //p
                    node.parent.parent.color = RED;  //p.p
                    rightRotate(node.parent.parent);  //자식들을 red로 설정하고, 가운데 노드, 즉 부모를 black으로 설정 
                }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;  //p
                    node.parent.parent.color = RED;  //p.p
                    leftRotate(node.parent.parent);  //자식들을 red로 설정, 가운데 노드, 즉 부모를 black으로 설정
                }
                break;
            }
        }
    }

    //RR case -> 왼쪽으로 회전 
    public void leftRotate(Node node){
        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;
        }
    }

    // LL case -> 오른쪽으로 회전
    public void rightRotate(Node node){
        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;
        }
    }

    //BFS-레벨 순회: (위쪽 레벨부터) 왼쪽 노드 -> 오른쪽 노드
    public void levelOrder(Node node){
        char[] color = {'B', 'R'};

        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()){
            Node cur = queue.poll();

            System.out.print("["+color[cur.color]+"] "+cur.key+" ");
            if(cur.left != null){
                queue.offer(cur.left);
            }

            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

---