[ Open Data Structures ] - Red-Black Trees - 1

Red-Black Tree(이하 RBT)는 다방면으로 사용되는 자료구입니다. JAVA Collections Framework, C++ STL를 비롯한 많은 Library implementation에 등장하며 Linux OS system kernel에서도 찾아볼 수 있습니다. 이렇듯 이 자료구조가 사랑받는 이유엔 다음과 같은 이유가 있습니다.

1. n개의 값을 가지는 RBT는 높아봐야 2logn의 높이를 가진다.

2. Add/Remove Operation이 최악의 경우 O(logn)의 Running Time을 가진다.

3. Add/Remove Operation 중 수행되는 Rotation의 대략적인 수행 횟수는 상수[Constant]이다.

1, 2번의 특징은 Skiplist와 Treap의 장점을 충분히 뛰어넘습니다. 왜냐하면 Skiplist와 Treap은 가장 먼저 Radomization에 크게 의존해야 O(logn)의 Running time이 보장되기 때문입니다. Scapegoat는 높이에 대한 상한이 필요하며 역시 O(logn)이 보장됩니다. RBT는 구현이 상당히 복잡하고 이해하기 어렵다는 단점이 있습니다. 게다가 조금이라도 Rotation작업에 실수가 생기면 치명적인 에러를 유발하며 추적하기가 대단히 까다롭습니다. 즉, 거의 대부분의 작업에 심혈을 기울이고 섬세한 조정이 필요하다는 말입니다. 바로 해치우고 싶지만 2-4Tree 라는 자료구조를 살펴보는 것이 RBT를 이해하는 것에 큰 도움을 줄 것입니다.

2-4 Tree

2-4Tree는 다음과 같은 특징을 가지는 자료구조(Tree)입니다.

Property 1.1 ) 모든 Leaf node는 같은 깊이를 가진다.(Height)

Property 1.2 ) 모든 Internal node는 2, 3 또는 4개의 Children node를 가진다.(Degree)

Lemma 1.1) n개의 Leaf node를 가지는 2-4Tree의 높이는 최대 log(n)을 넘을 수 없다.

먼저 Lemma 1.1에 대한 증명부터 공부합니다.

Figure a

Addition

Addition operation은 크게 어렵지 않습니다. 만약, leaf node u를 어떤 leaf의 부모 node w의 child node로써 addition operation을 수행한다면 그저 u를 w의 child로 만들어주면 됩니다. 이 경우에 property 1.1을 위반하는 일은 없습니다. 하지만 Height를 위반하지 않더라도 u를 추가하기 전에 이미 w가 4개의 Children node를 가지고 있었다면 w의 child에 u를 추가하는 작업은 Degree(Property 1.2)를 위반하게 될 것입니다. 이런 경우엔 node w를 w, w`으로 Split하고 각각 두 개, 세 개의 Children nod를 달아주는 것으로 해결할 수 있습니다. 

Split 이후에 w는 기존의 node였기 때문에 w의 어떤 Parent node가 존재하는 것이 명백합니다. 원래부터 있었기 때문입니다. 하지만 w`의 경우에는 새롭게 생겨난 node이기 때문에 Parent node가 존재하지 않을 수 있습니다. 그래서 w`을 w parent의 Child node로 집어 넣어줍니다. 그러면 w의 parent가 또 Degree Rule을 위반할 여지가 생길 겁니다. 그렇기 때문에 다시 재귀적으로 w parent를 검사하여 경우에 따라서 Split해야 합니다. 이 과정은 Degree property를 위반하지 않는 임의의 node를 만나거나 Root node를 Split 하는 경우에 이를 때까지 반복합니다. 이 과정은 모든 Leaves의 깊이를 동시에 증가시키면서 Height property를 위반하지 않도록 주의해야 합니다. 2-4Tree의 높이는 log(n)을 넘을 수 없기 때문에 새로운 leaf node를 추가하는 작업 역시 log(n)이내에 해결할 수 있습니다.

Remove Operation

이 단계 이후에 Root node 역시 Degree Property를 위반하기 때문에 추가적인 작업을 해야합니다.

삭제 작업은 추가 작업에 비해 훨씬 까다롭습니다. Leaf node u를 parent node w로부터 제거하려면 일단은 제거합니다. 만약 w가 삭제 작업 전에 두 개의 children node를 가지고 있었다면 삭제 작업 이후엔 Degree property를 위반한 셈이 될 것입니다. 이를 해결하기 위해 w의 형제 node인 w`을 살펴봅니다. w의 형제node w`의 존재가 자명한 이유는 Degree Property에 기인합니다.

만약, w`이 세 개나 네 개의 Children node를 가지고 있다면 w에게 하나를 떼서 붙여주도록 합니다. 이후엔 w`에는 두 개나 세 개의 children node가 남고 w는 두 개의 node를 children node를 가지고 있게 되므로 Degree property를 만족합니다. 

반면에, w`도 넉넉하지 못해서 두 개의 children node를 가지고 있을 경우가 분명 존재합니다. 이 경우엔 w`과 w를 논리적으로 병합해서 w가 세 개의 children node를 가진 node로 만드는 겁니다. 그리고 더 이상 존재의미가 없는 w`을 w`의 parent로부터 삭제하고 또 같은 과정을 부모 노드에서 반복합니다. 이 과정 역시 Root node에 도달하거나 두 개의 Children nodoe를 가진 node u나 두 개의 children node를 가진 형제 node u`을 만날 때까지 계속 되어야 합니다. Root node를 만난 경우에 root node가 한 개의 child node를 가지게 되었다면 root node를 삭제하고 child node를 포함한 새로운 root node를 만들어야 합니다. Addition이 각 Leaves의 깊이를 동시에 증가시켰던 것처럼 이 Deletion역시 모든 Leaves의 깊이를 동시에 감소 시켜서 height property를 만족합니다. Addition과 같은 원리로 이 작업은 O(log(n))의 Running Time을 갖습니다.