[알고리즘] 레드 블랙 트리 (Red-Black Tree) 의 특징

  이번 포스트에서는 Red Black Tree에 대해 다뤄보겠다. Red Black Tree는 이진검색트리 (BST; Binary Search Tree)에서 파생된 자료구조이다. 기존의 이진검색트리는 최악의 경우, 트리의 구조가 잘못 형성되어 한 쪽 (왼쪽/오른쪽)으로 치우친 경우 검색, 삽입, 삭제 과정이 Θ(n)까지 떨어질 수 있는 문제가 존재했다. 이러한 일을 방지하고자 트리의 균형을 맞추려는 시도가 이루어졌고, 그 중 하나가 레드 블랙 트리이다. 레드 블랙 트리는 개념적으로 노드의 색을 red와 black으로 설정하여 다음과 같은 규칙을 설정하여 트리의 균형을 맞춘다.

 

1. Root 노드는 Black이다.
2. 모든 Leaf(NIL)은 Black이다.
3. Red 노드의 자식 노드는 Black이다.
4. Root 노드에서 Leaf 노드로 이르는 임의의 경로에서 만나는 Black 노드의 수는 모두 동일하다.

레드 블랙 트리 (출처 : 위키피디아)

 

  위에서 말하는 Red/Black 과 같은 색상은 어디까지나 개념적인 내용이다. 그리고 2번에서 모든 Leaf (NIL) 이라 하였는데, 실제로는 아무 값도 없는 노드로, 이진검색트리에서의 leaf 노드의 자식 뻘로 보면 된다. 레드 블랙 트리의 삽입/삭제 과정을 일관되게 정리하기 위해 만들어진 개념인 것 같다. 그리고 실제로 레드 블랙 트리를 구현할 때 NIL을 실제로는 하나의 노드로 만들어서 가리키게 하는 것이 효율적이다.

 

              레드 블랙 트리의 균형 증명     

  처음 레드 블랙 트리를 접했을 때 트리의 균형을 맞추는 것을 수학적으로 어떻게 증명하는 지 궁금했는데, 레드 블랙 트리의 높이가 O(logN)으로 제한된다는 것으로 이해하면 될 것 같다. 이를 증명하는 과정에서 3번과 4번이 핵심적으로 적용된다.

  비교적 간단하게 생각하는 방법도 있고, 엄밀하게 증명하는 과정도 있다. 둘 다 기본적으로 root 부터 leaf까지 이르는 경로에서 만나는 black node의 수가 O(logN)으로 제한되어 있고, 레드 블랙 트리의 특성 3번에 의해 트리의 최대 높이 역시 O(logN)을 따른다는 아이디어이다.

(참고로 ⌊ ⌋ 기호는 내림 기호이고 ⌈ ⌉는 올림 기호이다.)

  간단하게 생각한 방법에서는 레드블랙트리를 완전 이진트리라고 가정하고 루트에서 리프까지 이르는 과정에서 만나는 블랙 노드의 최대 수가 완전이진트리의 최대 높이와 동일하다는 아이디어로 출발한다. 같은 n개의 노드를 가지고 트리를 구성할 때, 한쪽으로 치우친 트리를 만들면 경로가 길어지는 경우도 생김과 동시에 경로가 짧아지는 경우도 생기고, 결국 모든 경로에서 만나는 black node 수가 동일해야 하므로 만나는 black node의 수가 가장 짧은 경로의 수를 넘을 수 없게 된다. 따라서 루트에서 리프까지 만나는 블랙 노드의 최대 개수는 n개의 노드를 완전이진트리로 구성했을 때 최대 높이를 넘을 수 없다. 

  이제 레드 노드에 대해 생각해보자면, 레드 노드의 자식은 반드시 블랙 노드이기 때문에, 경로에서 레드 노드의 개수는 블랙 노드의 개수를 넘을 수 없다. 따라서 루트에서 리프까지의 노드 수는 최대 2(⌊logN⌋+1)을 넘을 수 없기 때문에 레드 블랙 트리의 최대 높이는 O(logN)이다.

 

  위 아이디어를 좀 더 수학적으로 증명한 과정이다. 위에서 계속 루트에서 리프까지 이르는 경로에서 만나는 블랙노드의 수라고 했던 것을 간단하게 bh(x)라고 정의한다. bh(x)는 x 노드에서 리프까지 이르는 경로에서 만나는 블랙노드의 수를 의미하는데, x 자신은 제외한다. 그리고 여기서 x를 루트로 하는 서브트리의 내부노드 (NIL을 제외한 노드) 수 n>=2^(bh(x))-1이라는 사실을 증명할 수 있다. 서브트리의 높이 h에 대한 수학적 귀납법으로 증명하는데, 증명 과정이 꽤 흥미로워서 읽어보면 좋을 것 같다. 어쨌든 이 정리와 레드블랙 트리의 3번 성질에 의해 마찬가지로 레드 블랙 트리의 높이가 O(logN)임을 증명할 수 있다.

 

  이로써 레드블랙트리는 최대 높이가 O(logN)을 따르는 균형 잡힌 트리임을 알 수 있고, 나중에 정리할 레드블랙트리의 삽입/삭제 과정에서 최악의 경우 레드블랙트리의 높이에 따르는 알고리즘이 존재하기 때문에, 삽입 삭제 과정도 최대 O(logN)임을 알 수 있게 될 것이다.