레드블랙트리

조건

1. 노드는 레드 혹은 블랙이다

2. 루트노드는 블랙이다.

3. 모든 리프 노드는 블랙이다.

4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. 

(레드 노드가 연달아 나올 수 없고, 블랙 노드만이 레드 노드의 부모가 될 수 있다.)

5. 어떤 노드로부터 시작되어 리프노드에 도달하는 모든 경로에는 리프노드를 제외하면 모두 같은 개수의 블랙 노드가 있다/

레드-블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.

AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형이 잡혀 있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전(rotations)이 필요하다.

레드-블랙 트리는 함수형 프로그래밍에서 특히 유용한데, 함수형 프로그래밍에서 쓰이는 연관 배열이나 집합(set)등을 내부적으로 레드-블랙 트리로 구현해 놓은 경우가 많다. 이런 구현에는 삽입, 삭제시 O(log n)만큼의 시간이 필요하다.

레드-블랙 트리는 2-3-4 트리와 등장변환이 가능하다(isometry). 다시 말해서, 모든 2-3-4 트리에는 구성 원소와 그 순서(order)가 같은 레드-블랙 트리가 최소한 하나 이상 존재한다는 말이다. 2-3-4 트리에서의 삽입, 삭제 과정은 레드-블랙 트리에서의 색 전환(color-flipping)과 회전(rotation)과 같은 개념이다. 그러므로 2-3-4 트리는 레드-블랙 트리의 동작 과정(logic)을 이해하는 데 많은 도움을 주며, 이런 이유로 많은 알고리즘 교과서들이 실제로는 잘 쓰이지 않음에도 불구하고 2-3-4 트리를 레드-블랙 트리가 나오기 바로 전에 소개하고 있다.

위 조건들을 만족하게 되면, 레드-블랙 트리는 가장 중요한 특성을 나타내게 된다: 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있다(balanced). 따라서, 삽입, 삭제, 검색시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(또는 깊이)에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이라고 할 수 있다.

왜 이런 특성을 가지는지 설명하기 위해서는, 네 번째 속성에 따라서, 어떤 경로에도 레드 노드가 연이어 나타날 수 없다는 것만 알고 있어도 충분하다. 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 될 것이다. 다섯 번째 속성에 따라서, 모든 경로에서 블랙 노드의 수가 같다고 했기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두배 이상이 될 수 없다.

트리 구조를 나타낼 때, 어떤 노드는 자식(child)를 하나만 가질 수도 있고, leaf node는 데이터를 담고 있을 수 있다. 레드-블랙 트리도 이와 같은 방법으로 나타내 볼 수도 있지만, 그런 표현 방식으로는 레드-블랙 트리의 특성이 변하게 되고, 알고리즘과 상충되게 나타날 수 있다. 그래서, 이 문서에서는 "nil leaves" 나 "null leaves"를 사용하고 있는데, 이 "null leaf"는 위의 그림에서와 같이 자료를 가지고 있지 않으며, 트리의 끝을 나타내는 데만 쓰인다. 트리 구조를 그림으로 표현할 때, 종종 이 "null leaf"를 생략하고 그리는 경우가 많은데, 그렇게 되면 그림상으로는 레드-블랙 트리의 특성을 만족하지 못하는 것처럼 보일 수 있으나 실제로는 그렇지 않다. 이렇게 함으로써, 모든 노드들은 설령 하나 또는 두개의 자식이 "null leaf" 일지라도, 두개의 자식(children)을 가지게 된다.

RB 트리는 최악의 경우에 대해 삽입, 삭제 시간에 있어서 가장 나은 성능을 제공한다. AVL 트리는 RB 트리보다 빡세게(-_- rigidly를 자연스럽게 한국말로 바꾸자니...쿨럭;;;) 균형이 잡혀 있으며 이런 빡빡함은 최악의 경우에 삽입, 삭제 동작시 RB 트리보다 더 많은 회전을 요구하게 된다. 물론 최악의 경우에라는 것이고 일반적으로 보다 타이트한 균형을 가지는 AVL 트리가 평균적인 탐색 시간은 더 빠를 것이다. 

하지만 삽입/삭제의 동작은 RB 트리가 우위이고 최악의 경우에 AVL 트리보다 탐색이 빠르다고 한다면 AVL 트리보다 RB 트리가 전체적으로 우위에 있다고 보여진다. AVL이나 RB 트리나 모두 threaded tree 형식을 채택했다.

Visual studio에 기본 탑재되는 STL에서도 트리 구조가 필요한 모든 컨테이너에서 RB 트리 방식을 쓰고 있다. STL에서는 일반적인 상황에서 최적의 성능을 가지는 자료 구조를 채택한다