Red-Black Tree

알고리즘 문제를 해결하다가, 이중 우선순위 큐 문제를 만났다. 문제 시간 제한이 6초라고 되어있길래, Binary Search Tree(BST)로 구현하려고, HashMap을 사용했다. 다만 만든 트리 구조가 최악의 경우 더하는 연산이 O(n)이기 때문에, 시간 초과가 났다. AVL이 생각이 났는데, 어떻게 구현하는지를 알지 못해 알아보던 도중 자바에 TreeMap 구조가 Red-Black Tree(RBT)라는 걸 알게되었다. TreeMap 이전에 RBT를 더 자세히 공부하고 싶어 위키트리 내용을 최대한 풀어서 정리했다.

Red-Black Tree

RBT는 자료의 추가, 삭제, 검색에서 최악의 경우도 일정한 Worst Case를 보장한다. 이런 특성은, 실행 시간이 중요한 경우, 일정 시간 실행을 보장해야 하는 경우 등 유용하게 쓰인다. 앞서 생각했던 AVL Tree는 균형에 대한 더 엄격한 기준이 있어서, 삽입과 삭제시 더 많은 회전이 필요하다 (균형을 위한)

특성

RBT는 각각의 노드가 레드, 블랙 속성을 가지고 있는 BST이다. BST의 조건에 추가적으로 다음과 같은 조건을 만족해야 한다.

1. 노드는 레드 또는 블랙이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. 즉, 레드 노드는 연달아 나타날 수 없고, 블랙 노드만 레드 노드의 부모 노드가 될 수 있다.
5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

네 번째, 다섯 번째 속성때문에, 극단적인 최단 경로의 경우 블랙 노드만 존재하는 경우이고, 극단적인 최장 경로의 경우 레드와 블랙 노드가 섞여 나오는 경우이다. 이 경우를 가정했을 때에도, 최단 경로와 최장 경로의 차이는 최단 경로의 두 배보다 항상 작다.

동작

일단, 읽기 작업은 일반적인 BST처럼 진행하면 된다. 다만, 삭제와 삽입은 위 특성을 만족시키기 위해 추가적인 작업이 필요하다. 아래는 위키피디아에서 설명하는 알고리즘을 본인이 읽기 쉽게 정리한 내용이다. 사용된 이미지도, 위키피디아에서 가져왔다.

삽입

RBT에서 삽입은, BST의 삽입과 동일한 방식으로 우선 삽입 후, 색을 붉은 색으로 만든다. 그 다음 단계는 그 주위 노드의 색에 따라 다르다. RBT에서는 삼촌노드(uncle node)에 대한 개념이 나온다. 부모 노드의 형제 노드를 뜻한다.

function getUncle(node) {
    const g = getGrandparent(node);
    if (!g) return undefined;    // 할아버지 노드가 없으면, 형제노드는 당연히 없다.
    
    const uncle = g.left === node.parent ? g.right : g.left;
    return uncle;
}

이제 다음 삽입하는 경우의 수를 살펴보자.

• 처음 루트에 N이 삽입될 때
  이 경우, RBT의 첫 번째 속성을 위해 N은 검은색이 된다. 그 이후는 RBT가 유지된다.

  function insertCase1(node) {
      if (!node.parent) node.color = BLACK;
      else insertCase2(node);
  }

• 새로운 노드의 부모 노드가 검은색인 경우
  이 경우도 RBT가 유지된다.

  function insertCase2(node) {
      if (node.parent.color === BLACK) return;
      insertCase3(node);
  } 

• 부모 노드와 삼촌 노드가 모두 붉은색인 경우
  레드 블랙 트리의 다섯 번째 특성을 유지하기 위해서 부모 P와 삼촌 U를 검은색으로 바꾸고, 할아버지 G를 붉은 색으로 바꾼다. 이렇게 되면, 새로 추가되는 노드 N은 검은 부모를 갖게 된다.

  

  다만 이 경우에, 할아버지 노드에서 두 번째 속성 또는 네 번째 속성을 만족하지 않을 수 있다. 이를 위해 지금까지 설명한 세 가지 케이스를 할아버지 노드에도 적용한다.

  function insertCase3(node) {
      const u = getUncle(node);
      if (u && u.color === RED) {
          node.parent.color = BLACK;
          u.color = BLACK;
          const g = getGrandparent(node);
          g.color = RED;
          insertCase1(g);
      } else insertCase4(node);
  }

• 부모는 붉은색인데, 삼촌은 검은색이고, N이 부모의 오른쪽(왼쪽) 자식 노드이고, 부모는 할아버지의 왼쪽(오른쪽) 자식 노드인 경우
  조건부터 아주 복잡한데, 위 순서대로 따라와보면 확인해야 하는 조건은 새로운 노드의 위치와 부모 노드의 위치라는 사실을 알 수 있다. 이 경우, N과 P의 역할을 변경하기 위해 왼쪽 회전을 해야한다.

  function insertCase4(node) {
      const g = getGrandparent(node);
      if (node === node.parent.right && node.parent === g.left) {
          rotateLeft(n.parent);
          n = n.left;   //과거에 부모 노드였던 것을 새로운 노드로 바꿔줌
      } else if (n === n.parent.left && n.parent === g.right) {
          rotateRight(n.parent);
          n = n.right;  // 위와 마찬가지
      }
      insertCase5(n);
  }

  이런 설명은 없지만, insertCase4는 부모 노드와 새로운 노드의 선을 직선으로 맞추는 느낌이 있다. 이는 다음 케이스로 넘어가기 위한 준비 과정처럼 보인다.

  

  그 이후, 부모 노드였던 P가 RBT의 다섯 번째 특성을 어기는 문제를 해결해야 한다. 그런데, 현재 상황이, 부모 노드였던 P를 새로운 노드로 판단한다면, 4번째 조건 중 “N이 부모의 오른쪽 자식 노드이고,” 부분만 바뀌게 되므로, 다음 다섯 번째 조건에서 해결할 수 있다.

왼쪽회전은 오른쪽 자식 노드를 그 노드의 부모 노드와 바꾸는 과정이다. 대략 아래와 같은 느낌

p = n.parent;
c = n.right;
if (c.left) c.left.parent = p;
n.right = c.left
n.parent = c;
c.left = n;
c.parent = p;
if (p) {
  if (p.left == p) p.left = c;
  else p.right = c;
}

오른쪽 회전은 이와 반대 방향으로 돌리는 걸 의미한다.

• 부모 노드가 붉은 색이지만, 삼촌 노드가 검은색이고, 새로운 노드 N이 부모의 왼쪽(오른쪽) 자식 노드이고, 부모 할아버지 노드의 왼쪽(오른쪽) 자식인 경우
  위의 케이스에서 한 번 왼쪽 회전을 통해 이 케이스로 왔든, 처음부터 부모 노드의 왼쪽으로 들어왔든 이 케이스로 들어오게 된다. 이 경우에는 할아버지 노드 G에 대해서 오른쪽 회전을 진행한다. 이 결과로 이전 부모 노드인 P는 새로운 노드 N과 할아버지 노드 G를 자식으로 갖게 된다. P는 붉은색, G는 검은색일 수 밖에 없으므로 P와 G의 색을 바꾸면, RBT의 네 번째 속성을 만족하게 된다.

  function insertCase5(node) {
      const g = getGrandparent(node);
      node.parent.color = BLACK;
      g.color = RED;
      if (node === node.parent.left) rotateRight(g);
      else rotateLeft(g);
  }

삭제

아주 복잡한 삽입 과정이 끝났다. 이제 삭제 작업을 보자. 삭제 방식 역시 BST의 삭제 방법을 기본적으로 따른 후, 색을 맞춘다. BST에서 노드 N을 삭제할 때, N의 자식이 둘이라면, 왼쪽 자손 중 최대 또는 오른쪽 자손 중 최소 노드를 N 위치로 옮긴다. 이때 문제가 되는 것은, 옮긴 주변의 레드 블랙 특성을 위반하는지이다. 옮긴 노드는 해당 트리에서 최소 또는 최대라는 특성때문에 최대 1개의 자손만을 가질 수 있다. 결국, 삭제 작업은 최대 1개의 자식만 가진 노드를 삭제하는 것과 마찬가지이다. 따라서, 자식이 1개 이하인 상황을 가정하고 삭제를 설명한다.

삭제할 노드는 M, M의 자식을 C라고 하자. 우선 간단한 상황을 먼저 해결하자. 삭제 대상이 붉은 색이라면, 그냥 M을 삭제한 뒤, C를 M대신 치환하면 된다. 또, M이 검은 노드, C가 붉은 노드라고 가정하자, 검은 노드를 삭제하면 경로의 검은 노드의 수가 같아야 하고, 또는 붉은 노드의 부모는 검은 노드여야 한다는 원칙을 위반할 가능성이 있다. 하지만, C를 검은색으로 바꿔주면 모두 해결 가능하다.

---

어려운 상황은 M, C가 모두 검은 노드일 때 발생한다. 일단 M을 자식 노드 C로 치환한다. 이 상황에서 C를 N으로 명명하고, N의 형제 노드를 S, 부모 노드를 P라고 명명한다.

• N이 새로운 루트가 될 때
  이전 삭제한 노드가 루트였음을 의미하고, 이는 모든 경로에서 검은색을 하나 줄인 것이다. 이전 특성이 모두 유지되므로 상황은 종료

  function deleteCase1(node) {
    if (!node.parent) return;
    deleteCase2(node);
  }

• S가 붉은 노드인 경우, N이 P의 왼쪽(오른쪽) 자식인 경우
  현재 상황에서 부모 노드 P가 검은 노드임이 확실한 상황이다. (삼촌 노드가 붉은 색이기 때문에) 이 경우, P와 S의 색을 바꾸고, P에서 왼쪽(오른쪽) 회전하면, S가 N의 할아버지 노드가 된다. 이제 N이 검은색 형제 노드와 붉은 부모 노드를 가지고 있게 된다. 이 상황을 만든 후 다음 케이스에서 나머지 문제(모든 경로에서 검은 노드의 수가 같지 않다.)를 해결하도록 한다. 이후 상황에 대해서 S는 할아버지 노드가 된 기존 S가 아니라, 새롭게 바뀐 N의 형제 노드를 의미한다.

  

  function deleteCase2(node){
    const s = getSibling(node);
    if (s.color == RED) {
      node.parent.color = RED;
      s.color = BLACK;
      if (n === n.parent.left) rotateLeft(node.parent);
      else rotateRight(node.parent);
    }
  
    deleteCase3(node);
  }

• P, S, 그리고 S의 자식들이 검은색인 경우
  S를 붉은 노드로 만들면 된다. S를 지나는 모든 경로에서 검은 노드 수를 하나 줄여, N을 지나는 경로의 검은 노드 수와 맞출 수 있다. 그러나, P 이하의 트리에서 검은 노드의 수가 1개 줄은 것이기 때문에, P를 지나지 않던 경로가 있다면, P를 지나는 경로보다 검은 노드 수가 한 개 더 많게 된다. 따라서, P에 deleteCase1을 재귀적으로 적용할 필요가 있다.

  
  
  

  function deleteCase3(node) {
    const s = getSibling(node);
    if (
        node.parent.color === BLACK && 
        s.color === BLACK &&
        s.left.color === BLACK &&
        s.right.color === BLACK) {
         s.color = RED;
         deleteCase1(node.parent);
    } else {
      deleteCase4(node);
    }
  }

• S와 S의 자식들은 검은색이지만, P는 붉은색인 경우
  S와 P의 색을 바꿔주면 된다. 이는 S를 지나는 경로의 검은 노드 개수에 영향을 주지는 않지만, N을 지나는 경로에 대해서는 검은 노드의 개수를 1개 증가시킨다. 이를 통해 삭제된 원래 검은 노드의 개수를 보충한다.

function deleteCase4(node) {
  const s = getSibling(node);
  if (node.parent.color === RED && s.color === BLACK && s.left.color === BLACK && s.right.color === BLACK) {
    s.color = RED;
    n.parent.color = BLACK;
  } else deleteCase5(node);
}

• S가 검정, S의 왼쪽(오른쪽) 자식이 빨강, 오른쪽(왼쪽) 자식이 검정이고, N이 부모의 왼쪽(오른쪽) 자식인 경우
  S를 오른쪽(왼쪽) 회전시켜 S의 왼쪽 자식이 S의 부모 노드이자, 새로운 S(N의 형제)가 되도록 한다. 그리고 S의 색을 부모 노드와 바꿔준다. 이 상태를 만들고 나서, deleteCase6으로 넘겨준다.

  

  function deleteCase5(node) {
    const s = getSibling(node);
    if (s.color === BLACK) {
      if (node === n.parent.left && s.right.color === BLACK && s.left.color === RED) {
        s.color = RED;
        s.left.color = BLACK;
        rotateRight(s);
      } else if (n === n.parent.right && s.left.color === BLACK && s.right.color == RED) {
        s.color = RED;
        s.right.color = BLACK;
        rotateLeft(s);
      }
    }
  }
  deleteCase6(node);

• S가 검은색, S의 오른쪽(왼쪽) 자식이 빨강, N이 P의 왼쪽(오른쪽) 자식인 경우
  P를 왼쪽(오른쪽)으로 회전해서 S가 P와 S의 오른쪽(왼쪽) 자식 노드의 부모 노드가 되도록 한다. 그리고, P와 S의 색을 바꾸고, S의 오른쪽(왼쪽) 자식노드를 검은색으로 만든다.

  

  이렇게 만들어진 트리에서 N은 하나의 검은 조상 노드를 더 갖게 되었고, 따라서 N을 지나는 경로는 검은색을 하나 더 갖게 된다. 반면, N을 통과하는 케이스는 두 가지 경우의 수를 갖는다.

  1. N의 새로운 형제 노드를 지나는 경우: 변경되기 전과 같은 순서를 만난다. P -> S -> ... 이던게, S -> P -> ... 로 바뀐 것 뿐
  2. N의 새로운 삼촌 노드를 지나는 경우: 변형 되기 전에 P -> S -> S 오른쪽 자식 -> ... 경로를 가지던 것이, 변형 후, S -> S 오른쪽 자식 -> ...로 바뀌게 되었다. 하지만 붉은 노드가 하나 줄었기 때문에 경로 상에서는 같은 검은 노드를 만나게 된다.

  function deleteCase6(node) {
    const s = getSibling(node);
    s.color = node.parent.color;
    node.parent.color = BLACK;
  
    if (node == node.parent.left) {
      s.right.color = BLACK;
      rotateRight(node.parent);
    } else {
      s.left.color = BLACK;
      rotateRight(node.parent);
    }
  }

Reference

• https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC
• https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98
• https://coding-factory.tistory.com/557