Red Black Tree - Summary

Binary Search Tree의 최악의 상황에 대해서도 균형된 시간 복잡도가 나올 수 있도록 새롭게 고안된 Balanced Binary Search Tree다.

즉, 최악의 경우 (한쪽에만 노드가 일렬로 정렬된 경우) 가 나오지 못하도록 제약 조건을 걸고 있다.

 

[제약 조건]

1. Root Property : 루트 노드의 색은 검정(Black)이다.

2. External Property : 모든 외부 노드들은 검정(Black)이다.

3. Internal Property : 빨강(Red)노드의 자식은 검정(Black)이다.  == No Double Red(빨간색 노드가 연속으로 나올 수 없다.) 

4. Depth Property : 모든 리프노드에서 Black Depth는 같다.  == 리프노드에서 루트노드까지 경로에서 만나는 블랙노드의 수는 같다. 

 

제약 조건에 검정과 빨강이 나오기 때문에 Red Black Tree라고 불린다.

 

값을 입력(Insert)하다 보면, Doubled Red가 나오는 경우가 발생한다. 이 경우 3번 제약 조건에 위배 되기 때문에 Red Black Tree에서는 Restructuring과 Recoloring과정을 통해 문제를 해결한다.

 

Restructuring

1. 나(z)와 내 부모(v), 내 부모의 부모(Grand Parent)를 오름차순으로 정렬

2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.

3. 올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다. 

 

Recoloring

1. 현재 inset된 노드(z)의 부모와 그 형제(w)를 검정(Black)으로 하고 Grand Parent(내 부모의 부모)를 빨강(Red)로 한다.

2. Grand Parent(내 부모의 부모)가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다.

 

[Red Black Tree의 시간복잡도]

1) ReStructuring의 시간복잡도

Restructuring은 어떤 노드를 Insertion을 한 후에 수행되기 때문에 시간 복잡도는 O(logn)이 걸리게 된다.

 

2) ReColoring의 시간복잡도

내가 지금 현재 넣는 트리는 Red Black Tree라는게 자명하다. Red Black Tree가 아니라면, Restructuring이든, Recoloring이든 일어나서 Red Black Tree화 했을 것이다.

 

insert를 하는데 "내 위치"를 찾아야하는데 이 때, O(logn)이라는 시간이 걸리게 된다.

Restructuring과 마찬가지로 Recoloring은 O(1)의 시간이 걸린다.

하지만, Recoloring은 Root까지 propagation될 수 있으므로 최악의 경우 O(logn)이 걸리게 된다. 

총 O(logn)이 걸리게 되는 것이다. 

 

Red Black Tree에 삽입(insertion)하는경우, Restructuring을 하든, Recoloring을 하든 O(logn)이 걸린다. 

 

Red Black Tree는 현재 고안된 이진 탐색 방법 중 가장 성능이 좋은 것으로 알려져 있다.

또한 C++ STL의 Map도 Red Black Tree로 만들어져 있다고 한다.