레드블랙트리

레드-블랙트리

 

- 이진탐색트리의 일종

- 균형잡힌 트리 : 높이가 o(logn)

- search, insert, delete연산을 최악의 경우에도 o(logn)시간에 지원

 

- 각 노드는 하나의 키, 왼쪽 자식, 오른쪽 자식, 부모노드의 주소를 저장

- 자식노드가 존재하지 않을 경우 NIL노드라고 부르는 특수한 노드가 있다고 가정

- 결국 모든 리프노드는 NIL노드

- 루트의 부모도 NIL노드라고 가정

- 노드들은 내부노드와 NIL노드로 분류

* 실제로 구현할 때 NIL노드를 구현하지는 않음

 

레드-블랙 트리 -> 기본적으로는 이진탐색트리

1. 각 노드는 red 혹은 black

2. 루트노드는 black

3. 모든 리프노드는 black

4. red노드의 자식노드들은 전부 black -> red노드는 연속되어 등장 x : 가장 중요

5. 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 존재한다.

레드-블랙 예시

특징

1. 노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 에지의 개수이다.

2. 노드 x의 블랙-높이 bh(x)는 x로부터 리프노드까지의 경로상의 블랙노드의 개수이다.

 

==> 높이가 h인 노드의 블랙-높이는 bh>=h/2이다

- 조건 4에 의해 레드노드는 연속될 수 없으므로 당연

 

==> 노드 x를 루트로드로 하는 임의의 부트리는 적어도 2^bh(2)-1개의 내부노드를 포함한다.

==>n개의 내부노드를 가지는 레드블랙트리의 높이는 2log(n+1)이하이다.

 

search

- 이진탐색트리랑 같음

 

Left and Right Rotation

- 시간복잡도 o(1)

- 이진탐색트리의 특성을 유지