RB 트리 (RED-BLACK TREE)

• 레드-블랙 트리는 자가 균형 이진 탐색 트리로, 모든 노드가 빨간색 혹은 검은색이며, 루트 노드는 검은색, 모든 리프 노드는 검은색이다. 빨간색 노드의 자식은 검은색이며, 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

• 레드-블랙 트리는 이진 탐색 트리의 단점을 보완하기 위해 사용되며, 최악의 경우에도 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

• 레드-블랙 트리의 특성 중 하나는 루트 노드부터 가장 먼 리프 노드까지의 거리가, 가장 가까운 노드 경로까지의 거리의 두 배 보다 항상 작다는 것이다.

• 레드-블랙 트리에서는 경계 노드를 사용하여 NIL을 표현하며, 이를 통해 노드의 NIL자식을 정상적인 자식 노드와 동일하게 다룰 수 있다. 이를 위해 하나의 경계 노드를 두어 모든 NIL, 즉 모든 리프와 루트의 부모를 표현한다.