레드블랙트리,RedBlackTree

정의

레드블랙트리는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로 '대칭형 이진 B트리'를 발전시켜 만들어 졌다. 레드 블랙 트리는 최악의 경우에도 우수한 실행시간을 보인다. 

 

시간 복잡도

트리에 n개의 원소가 있을 때 O(lonN)의 시간 복잡도로 삽입/삭제/검색이 가능하다.

 

특성

1. 노드는 레드 or 블랙

2. 루트 노드는 블랙이다.

3. 모든 리프 노드들(NIL)은 블랙이다.

4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다.(즉, 레드 노드는 연달아 나타날 수 없다. 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)

5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

 

사용예

C++11 기준 stl container map은 레드블랙트리로 만들어져 있다.

 

삽입 Flow

- 이진 탐색 트리 삽입 flow를 진행하고, redblack 특성을 만족시키기 위한 flow가 진행된다.

 

삭제 Flow

- 이진 탐색 트리 삭제 flow를 진행하고, redblck 특성을 만족시키기 위한 flow가 진행된다.

 

PPT