RB Tree [레드 블랙 트리]

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

 

Red-Black Tree

Red-Black Tree(이하 rb)는 이진 트리의 한 종류이다. 그 중에서도 balanced search tree의 하나이다.

rb는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 O(logn)의 시간복잡도를 가진다.
(평범한 이진 트리는, 최악의 경우 O(n)이다. 왜냐하면 높이가 n이 될 수 있기 때문에!!!)

즉, 균형 잡힌 트리라는 말은 트리의 높이가 어느정도 유지가 된다는 뜻이다. 때문에 rb는 높이가 logn이고 시간복잡도가 O(logn)이 된다.

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

특징

1. 노드는 레드 혹은 블랙 중 하나

2. Root node는 블랙!

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

4. 레드 노드의 자식노드는 양쪽 모두 블랙이다. (레드 노드의 부모노드는 블랙만 가능하다.)

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

 

이 5가지 특징이 RB를 잘 나타내준다.

4에서 최단 경로는 모두 블랙인 노드, 최장 경로는 블랙 - 레드가 번갈아 나오는 경우일텐데
5에서 모두 같은 개수의 블랙 노드가 있으므로, 최장 경로의 거리는 최단 경로의 거리의 2배 이상이 될 수 없다!!

(*참고 NIL은 null leaf로 자료를 갖지 않고, 트리의 끝을 나타내는데 쓰인다! )

 

구현

삽입(Insertion)

이진 탐색 트리와 똑같이 노드를 삽입한다. ( 부모보다 크면 오른쪽, 작으면 왼쪽) 색은 붉은색!

삼촌노드(Uncle Node)는 같은 높이의 옆 노드(형제 노드말고 부모가 다른) 의 부모 노드를 뜻한다.

 

특성 3. 모든 리프노드는 검은색이다는 항상 만족한다.
특성 4, 5. 노드의 추가, 검은 노드 -> 붉은 노드로의 전환, 회전 등에 의해 항상 지켜지진 않는다.

추가하려는 노드 N이 루트인 것부터 시작하여 5가지 케이스로 나누어 실행한다. (wiki 참고)
개략적인 방식은, 추가하는 노드를 붉은 노드로 추가한 후 RB의 특성 5가지에 맞게 회전과 색변환을 해준다.

 

삭제(Removal)

이진검색트리에서의 삭제를 이해하는게 우선이라고 생각한다. 중위순회를 했을 때, 삭제하고자 하는 값의 바로 좌, 우의 값을 찾아야한다.
중위순회를 할 경우 결국 작은 값부터 오름차순으로 방문하게 되고, 삭제하고자 하는 노드를 N이라고 하면

오름차순에서 N의 좌우에 있는 노드는 왼쪽 서브트리의 최대값, 오른쪽 서브트리의 최솟값으로
각 노드들은 자식이 1개이거나 0개이다. 이 개념을 가져와서 RB트리에 적용한다.
개략적인 방식은 이진탐색의 삭제와 유사하고 그 이후 RB의 특성을 유지하기 위해 색변환을 해준다.


글에 디테일을 점점 추가해보자...!