RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식의 자료구조이다.

먼저 레드 블랙 트리를 알아보기 전에 BST가 무엇인지 한번 더 알고 넘어가자.

BST(Binary Search Tree)는 이진 탐색 트리이다.
효율적인 탐색을 위해 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장 방법이 무엇일까를 고민해야 한다. 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.

  • 규칙1 : 이진 탐색 트리의 노드에 저장된 키는 유일하다.
  • 규칙2 : 루트 노드의 키가 왼쪽 서브트리를 구성하는 어떠한 노드의 키보다 크다.
  • 규칙3 : 루트 노드의 키가 오른쪽 서브트리를 구성하는 어떠한 노드의 키보다 작다.
  • 규칙4 : 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

Red Black Tree

결론부터 말하자면 Red-Black-Tree에 데이터를 저장하게 되면 Search, Insert, Delete에 O(log n)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다. 동일한 노드의 개수일 때, depth가 최소가 되는 경우는 tree가 Complete Binary Tree인 경우이다.

1. Red-Black-Tree의 정의

Red-Black-Tree를 앞으로 RBT라고 부르도록 하겠다.
RBT는 다음의 성질을 만족하는 BST이다.

  • 각 노드는 Red 혹은 Black라는 색깔을 갖는다.
  • Root node의 색깔을 Black이다.
  • 각 leaf node(단말 노드)는 black이다.
  • 어떤 노드의 색깔이 red라면 두 개의 children의 색깔은 모두 black이다.
  • 각 노드에 대해서 노드로부터 descendant leaves까지의 단순 경로는 모두 같은 수의 black node들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다. [노드 x로부터 노드 x를 포함하지 않은 leaf node까지의 simple path 상에 있는 black node들의 개수]

[무슨 말일까…? 어렵다!]

2. RBT의 특징

  • Binary Search Tree이므로 BST의 특징을 모두 갖는다.
  • Root node부터 leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.
  • 노드의 child가 없을 경우, child를 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL은 leaf node로 간주한다.

RBT는 BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조이다. 그렇다면 이를 어떻게 해결할 것인가??

삽입

우선 BST의 특성을 유지하면서 노드를 삽입한다. 그리고 삽입된 노드의 색깔을 Red로 지정한다. Red로 지정하는 이유는 Black-Height의 변경을 최소화하기 위함이다. 삽입 결과 RBT의 특성 위배시 노드의 색깔을 조정하고 Black-Height가 위배되었다면 rotation을 통해 height를 조정한다. 이러한 과정을 통해 RBT의 동일한 height에 존재하는 internal node 들의 Black-Height가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2미만으로 유지된다.

삭제

삭제도 삽입과 마찬가지로 BST의 특성을 유지하면서 해당 노드를 삭제한다. 삭제될 노드의 child의 개수에 따라 rotation 방법이 달라지게 된다. 그리고 만약 지워진 노드의 색깔이 Black이라면 Black-Height가 1 감소한 경로에 black node가 1개 추가되도록 rotation을 하고 노드의 색깔을 조정한다. <지워진 노드의 색깔이 red라면 Violation이 발생하지 않으므로 RBT가 그대로 유지된다.