Red-Black Tree flow diagram

산술비교가 가능한 대용량 데이터에 대해 삽입/삭제/검색을 해야하는 경우 적용할 알고리즘.  C++의 std::map을 사용하면 굳이 몰라도 되긴하지만, C에서는 없으니까, 오픈소스를 가져다 이용한다.

 Red / Black  지정에 대한 규칙은 다음과 같다.

1. 하나의 노드는  Black  아니면   Red 로 한다.
2. Root 노드는 반드시  Black 이다.
3. 모든 Leaf 노드는  Black 이다.
4.  Red  노드의 Child 노드 양쪽(left/right)은 항상 모두  Black 이다. 그러므로,  Black  노드만  Red  노드의 Parent 노드가 될 수 있다.
5. 어떤 노드로부터 시작되어 Leaf 노드에 도달하는 모든 경로에는 Leaf 를 제외하고 모두 같은 개수의  Black 노드가 있다.

위와 같은 다섯가지 조건을 만족하게끔 알고리즘이 구성되어 있다.  그러다보니, Root 노드로부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두배보다 항상 작게 된다. 그래서 대략 균형잡힌 트리라고 볼 수 있겠다. 삽입/삭제/검색에 대해 최악의 경우에도 시간복잡도가 보통의 이진트리와 비교해보면 훨씬 효율적이라고 볼 수 있다.  삽입/삭제/검색에 대한 시간복잡도면에서 AVL 알고리즘이 이와 유사하긴 하지만, Red/Black 알고리즘이 효율성에서 훨씬 앞서고 있으며 보다 많이 사용되고 있다.(거의 대부분)

Download document (RedBlack Tree.pdf)