[자료구조] Red Black Tree

[자료구조] Red Black Tree

1. 정의

• BST를 기반으로하는 트리 형식의 자료구조
• 검색, 삽입, 삭제의 시간이 $O(logN)$이 소요 됨

2. 규칙

• 모든 노드는 빨간색이나 검은색
• 루트는 항상 검은색
• 새로 추가되는 노드는 빨간색
• 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 함
• 어떤 경로에서도 빨간색 노드가 연속으로 2개가 있으면 안됨
• 모든 빈 노드(null)는 검은색이라고 가정

2.1 균형을 맞추는 방법

• 이모 노드가 검은색인 경우
  • 회전을 시킴
    • 회전 후에, 부모 노드는 검은색, 두 자식 노드는 빨간색이어야 함
• 이모 노드가 빨간색인 경우
  • 색깔을 전환
    • 전환 후에, 부모 노드는 빨간색, 두 자식 노드는 검은색이어야 함

3. 구현

public class RedBlackTree<K, V> {
  Node<K, V> root;
  int size;

  static class Node<K, V> {
    K key;
    V value;
    //이모 노드를 쉽게 찾기 위하여 저장
    Node<K, V> left;
    Node<K, V> right;
    Node<K, V> parent;
    boolean isLeftChild;
    boolean black;

    public Node(K key, V value) {
      this.key = key;
      this.value = value;

      left = null;
      right = null;
      parent = null;
      black = false;
      isLeftChild = false;
    }
  }
}

//추가 메서드
public void add(K key, V value) {

  Node<K, V> node = new Node<>(key, value;)

  if (root == null) {
    root = node;
    root.black = true;
    size++;
    return;
  }

  add(root, node);
  size++;
}

//재귀 add 메서드
private void add(Node<K, V> parent, Node<K, V> newNode) {
  if (((Comparable<K>) newNode.key).compareTo(parent.key) > 0) {
    if (parent.right == null) {
      parent.right = newNode;
      newNode.parent = parent;
      newNode.isLeftChild = false;
      checkColor(newNode);
      return;
    }
    add(parent.right, newNode);
    checkColor(newNode);
    return;
  }

  if (parent.left == null) {
    parent.left = newNode;
    newNode.parent = parent;
    newNode.isLeftChild = true;
    checkColor(newNode);
    return;
  }
  add(parent.left, newNode);
  checkColor(newNode);
  return;
}

  public void checkColor(Node<K, V> node) {
    //루트는 항상 검정색이므로 확인x
    if (node == root) {
      return;
    } 
    //노드가 두개 연속 빨간색 이라면
    if (!node.black && !node.parent.black) {
      correctTree(node);
    }
    checkColor(node.parent); // 재귀로 확인
  }

private void correctTree(Node<K, V> node) {
  //노드의 부모가 왼쪽 자식이면
  if (node.parent.isLeftChild) {
    if (node.parent.parent.right == null || node.parent.parent.right.black) { // 이모노드의 색깔이 검정색이면 (빈 노드도 검정색)
      return rotate(node);
    }
    // 이모 노드가 빨간색이면 색깔 반전
    node.parent.parent.right.black = true;
    node.parent.parent.black = false;
    node.parent.black = true;
    return;
  }
} else { //오른쪽 자식일 때
    if (node.parent.parent.left == null || node.parent.parent.left.black) { // 이모노드의 색깔이 검정색이면 (빈 노드도 검정색)
      return rotate(node);
    }
    // 이모 노드가 빨간색이면 색깔 반전
    node.parent.parent.left.black = true;
    node.parent.parent.black = false;
    node.parent.black = true;
    return;
}

//회전 메서드
public void rotate(Node<K, V> node) {

  if (node.isLeftChild) { //현재 노드가 왼쪽 자식
    if (node.parent.isLeftChild) { //부모 노드가 왼쪽 자식
      rightRotate(node.parent.parent);
      node.black = false;
      node.parent.black = true;
      if (node.parent.right != null) {
        node.parent.right.black = false;
      }
      return;
    }
    rightLeftRotate(node.parent.parent); //부모 노드가 오른쪽 자식
    node.black = true;
    node.right.black = false;
    node.left.black = false;
    return;
  } else { //현재 노드가 오른쪽 자식
    if (!node.parent.isLeftChild) { //부모 노드가 오른쪽 자식
      leftRotate(node.parent.parent);
      node.black = false;
      node.parent.black = true;
      if (node.parent.left != null) {
        node.parent.left.black = false;
      }
      return;
    }
    leftRightRotate(node.parent.parent); //부모 노드가 왼쪽 자식
    node.black = true;
    node.right.black = false;
    node.left.black = false;
    return;
  }
}

// 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮김
public void leftRotate (Node<K,V> node) {
    Node<K,V> temp = node.right;
    node.right = temp.left;
    // 부모 노드 node.right가 temp가 되면서 조부모 노드가 없어짐
    if (node.right != null) {
        node.right.parent = null;
        node.right.isLeftChild = false;
    }
    // node가 루트인 경우
    if (node.parent == null) {
        root = temp;
        temp.parent = null;
    }    else { // node가 루트가 아닌 경우
        temp.parent = node.parent;
        if (node.isLeftChild) {
            temp.isLeftChild = true;
            temp.parent.left = temp;
        } else {            
            temp.isLeftChild = false;
            temp.parent.right = temp;
        }
        temp.left = node;
        node.isLeftChild = true;
        node.parent = temp;
    }
}

//좌측-우측 회전
public void leftRightRotate(Node<K, V> node) {
  leftRotate(node.left);
  rightRotate(node);
}

//높이 반환 메서드
public int height() {
  if (root == null) {
    return 0;
  }
  return height(root) - 1;
}

public int height(Node<K, V> node) {
  if (node == null) {
    return 0;
  }

  int leftheight = height(node.left) + 1;
    int rightheight = height(node.right) + 1;

    if (leftheight > rightheight) {
        return leftheight;
  }

    return rightheight;
}

//검정 노드 확인
public int blackNodes(Node<K, V> node) {
    if (node == null) {
        return 1;
  }

    int rightBlackNodes = blackNodes(node.right);
    int leftBlackNodes = blackNodes(node.left);
    // 오른쪽과 왼쪽의 검은색 노드 개수가 다르면 에러를 내거나 고쳐줍니다.
    if (rightBlackNodes != leftBlackNodes){
        // throw an error
        // or fix the tree
  }
    // 검은색 노드이면 해당 노드의 수를 늘려줍니다.
    if (node.black) {
        leftBlackNodes++;
  }
    return leftBlackNodes;
}

---

※ 참조

• 자바로 구현하고 배우는 자료구조 - 네이버 부스트 코스

• Interview_Question_for_Beginner