Red Black Tree

레드블랙트리는 BST(Binary Search Tree)의 일종으로 왼쪽엔 현재 키 값보다 작은 값, 오른쪽은 현재 키 값보다 큰 값을 가지는 균형잡힌 트리이다.

등장하게 된 배경은 일반적인 BST의 워스트 케이스에 대한 단점 해소인데, 한쪽 방향으로만 쭉 이어져 LinkedList처럼 되어버리는 케이스를 만들지 않게 할 수 있다.

레드블랙트리는 BST의 특징 + 다음 4가지의 조건을 만족해 균형을 잡는 트리이다.

1. 루트 노드는 Black이다.
2. 모든 리프 노드는 Black이다.
3. Red 노드의 자식은 Black이다 (No double red).
4. 모든 리프노드부터 루트노드까지 Black의 개수는 같다.

+) 삽입되는 노드는 Red이다.

삽입되는 노드는 Red이므로 연속적으로 노드를 삽입하다 보면 Double Red가 발생할 수 있다.

이를 해결하는 방법은 2가지가 존재한다.

1. Restructing
2. Recoloring

위 두 방법을 사용하는 경우는 Uncle node의 색에 따라 달라진다.

7번 노드를 기준으로, 부모인 9번 노드의 형제인 1번 노드가 Uncle Node이다.

Uncle Node가 위처럼 검정일 경우 Restructing, 그렇지 않고 빨간색인 경우 Recoloring을 수행한다.

Restructing

위 예시에서 Restructing을 진행해보자.

현재 노드(7)와 부모 노드(9), 그리고 부모의 부모 노드(5)를 이용한다.

• 먼저 세 노드를 오름차순으로 정렬한다 (5, 7, 9)

• 가운데 값(7)을 부모로 만들고 나머지 값(5, 9)를 그 자식으로 만든다.

• 부모가 된 가운데 값(7)을 Black으로 만들고 나머지를 Red로 만든다.

위처럼 과정을 진행하면 Double Red가 제거된다.

Recoloring

Recoloring은 Uncle node가 빨간색일 때 사용하는 것이므로 예제를 약간 변경해 보자.

현재 노드(7)와 부모 노드(9), 부모의 형제 노드(1), 그리고 부모의 부모 노드(5)를 모두 이용한다.

1. 현재 노드(7)의 부모(9)와 그 형제(1)를 Black으로 하고 부모의 부모(5)를 Red로 한다.

2. 부모의 부모(5)가 Root노드가 아닌 경우 Double Red 발생 가능성이 있고, 재귀적으로 수행한다.

1번 과정을 진행하면 아래와 같이 바뀐다.

이 트리에서 5가 루트 노드이므로, 루트 규칙에 의해 5번 노드는 Black으로 바뀌게 된다.

하지만 5번이 전체 트리의 루트가 아니고, 위 트리가 다른 트리의 서브트리라면??

5번 Red의 부모 위치에 Red가 존재할 수 있다.

이럴 경우에 5의 부모 위치로 올라가서 다시 Restructing 또는 Recoloring을 수행하게 될 수 있으며 최악의 경우 현재 위치에서 전체 트리의 루트 위치까지 진행할 수 있다.