레드-블랙 트리( Red-black tree )

레드-블랙 트리( 이하 RBT )는 특수한 형태의 이진 탐색 트리로, 삽입 및 삭제 시 균형을 유지하는 '자가 균형 이진 탐색 트리' 이다.

일반적인 이진 탐색 트리는 최악의 경우에 O(N)의 시간 복잡도를 갖지만, 균형을 유지하는 RBT는 최악의 경우에도 O(logN)의 시간 복잡도를 갖는다.

< 레드-블랙 트리 >

 

1. 특징

 

- RBT의 노드는 기존과 조금 다른데, 부모에 대한 참조와 노드의 색깔에 대한 변수가 추가된다. 그리고 리프 노드는 값을 가지지 않는 NULL 노드로서 사용된다.

 

- RBT의 연산은 기본적으로 이진 탐색 트리의 것을 사용하되, 균형을 유지하기 위한 로테이션과 색 변경 등의 연산이 추가된다.

 

2. 필요조건

 

- 모든 노드는 레드 또는 블랙이다.

 

- 루트 노드는 블랙이다.

 

- nil(null) 노드는 블랙이다.

 

- 레드 노드의 자식 노드는 모두 블랙이다.

( 레드 노드는 연속될 수 없고, 레드 노드의 부모 노드는 블랙이다. )

 

- 어느 노드로 부터 모든 하위 nil 노드까지의 경로 상에 nil 노드를 제외한 블랙 노드의 수는 같다.

 

3. 구현