[DevLog][DS] Red Black Tree: concept

Red Black Tree

다음과 같은 성질을 만족하는 이진 검색 트리

1. 모든 노드는 레드나 블랙
2. 루트는 블랙
3. 리프(NIL)는 블랙
4. 레드 노드의 자식은 모두 블랙
5. 한 노드로부터 그 자손인 리프 노드로까지 가는 경로에 포함된 블랙 노드의 개수가 같음

레드 블랙 트리는 이진 검색 트리로서, 각 노드 당 한 비트의 추가 메모리에 노드의 색깔(레드, 블랙)을 저장한다. 루트에서 리프까지의 경로에 나타나는 노드의 색을 제한함으로써 그러한 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장할 수 있다. 이로써 근사적으로 균형을 이룬 트리 가 된다.

경계노드 sentinel

각 노드마다 리프노드를 모두 NIL로 붙여주는 대신, 이를 표현하는 하나의 노드만을 사용할 수 있는데 이를 경계노드(sentinel)라고 한다. 표기는 T.nil. 레드블랙 트리의 모든 리프는 값의 의미를 갖지 않기 때문에 가능. (모두 붙여줄 수도 있다. 그러나 저장공간이 낭비된다.)

흑색 높이 black-height

한 노드에서 리프까지의 경로에 있는 흑색 노드의 개수를 말한다. 자기 자신은 제외한다. 레드블랙 특성의 5번째 조건 때문에 루트에서 리프로 내려가는 모든 경로의 black-height(bh)는 같다. 트리의 bh는 루트의 bh와 동일하다.

왜 좋은가?

n개의 내부 노드를 가지는 레드블랙 트리는 최대 $2\lg(n+1)%의 높이를 가진다.
n개의 노드를 갖는 일반 binary search tree의 높이가 n까지 가능한 것과 달리, 레드블랙 트리의 높이는 $2\lg(n+1)$ 로 제한된다.