Red-Black Tree (레드 블랙 트리)

정의

이진탐색 트리의 한 종류로서 균형 잡힌 트리이다.

이진탐색 트리의 조건을 기본적으로 만족하면서, 아래의 5가지 조건을 만족해야 된다.

 

* 자식이 없는 상태(Null, None, Nill)을 나타내는 노드가 존재한다.

 

1. 모든 노드는 Red/Black 두 가지중 하나의 색상값을 가진다.

2. Root노드는 반드시 Black 색상이다.

3. 없는 상태(Null, None, Nill)을 나타내는 노드는 Black 색상을 갖는다.

4. Red색상의 노드는 반드시 Black색상의 자식을 가져야 한다.(Black 노드는 Black/Red 어떤색이든 자식으로 가질 수 있다.)

5. 임의 노드에서 모든 Leaf 노드까지의 경로에서 시작 노드를 제외한, Black node의 개수(Black Height)는 동일하다.

-> 두 자식이 모두 같은 색의 노드라면, 부모와 색을 바꿔주어도 5번 조건은 성립한다.  

 

그러면? 위의 5가지 조건을 모두 지키면 과연 균형잡힌 트리일까?

 

 

증명.

임의 노드 v의 높이 h(v)

임의 노드 v의 black 높이(시작 노드를 제외한, Black node의 개수) bh(v)

 

사실1

v의 서브 트리의 internel 노드의 개수  >=  2^bh(v) - 1

 

귀납적 증명

 

h(v) = 0  일때(root만 존재할때),

bh(v) = 0 --> 2^bh(v) - 1 = 0

v의 subTree의 internel 노드의 개수 => 0개

0 >= 0  (성립함)  

 

k는 0을 포함한, 양의 정수

 

h(v) = k  일때,  v의 subTree의 internel 노드의 개수  >=  2^bh(v) - 1 성립한다고 가정한다.

 

h(v) = k+1 일때,

사실2.

 "Red색상의 노드는 반드시 Black색상의 자식을 가져야 한다"는 조건에 따라

 

root시작하여, leaf까지 어떤 경로에서던지,

bh(r) (black node의 개수) >= h(r) / 2

 

* bh(r) >= h(r) / 2

 

사실1에 의해서

루트의 서브 트리의 internel 노드의 개수  >=  2^bh(r) - 1

 

n(red-black trees노드의 개수 ) >= 2^(h(r) / 2) - 1

n+1 >= 2^(h(r) / 2)

 

log(n+1) >= h(r) / 2

 

2*log(n+1) >= h(r)

노드 n개인 red-black tree의 높이는 2*log(n+1)를 넘을수 없다.