Red-Black Tree에서 Red 노드를 삽입하고 균형을 맞추는 이유?
Red-Black 노드는 모든 경로의 Black 노드의 개수를 동일하게 유지한다.
Red-Black Tree는 일반적인 이진 탐색 트리와 다르게 Black 노드의 개수를 통해 균형을 유지한다. Tree에 새로운 노드를 삽입하는 경우를 생각해보자. Black 노드를 삽입이 불가능한 것은 아니다. 중요한 것은 Red-Black 트리의 조건에 맞게 모든 경로에 대하여 동일한 Black Depth를 갖도록 균형을 맞춰주는 것이다.
Black 노드를 삽입하면, 언제나 균형이 깨진다. 새로운 노드가 추가되는 경로에만 Black 노드의 개수가 1개 증가하기 때문이다. 반면에 Red 노드를 삽입하는 경우에는 균형이 유지되는 경우가 존재한다. 리프 노드의 부모가 Black 노드인 경우에는 Red-Black 노드의 조건과 위배되지 않는다.
결론적으로, 효율적인 연산을 위해 Red 노드를 삽입한다.
Red-Black 트리는 균형을 유지하기 위해 노드를 새롭게 색칠한다.
Red-Black Tree는 이진 탐색 트리이므로 자식 노드가 2개 뿐이다. 두 자식 노드의 색깔이 같고, 부모 노드와 색깔이 다르다면, 서로 교체하더라도 문제가 발생하지 않는다. (자식 노드를 Black 에서 Red로 바꾸는 경우에는 Double Red 문제가 발생할 수도 있다. 이는 추후에 설명하겠다.)
모든 리프노드에서 Black Depth가 유지되고, Red-Black Tree의 조건에 위배되지 않는다. 이러한 점을 이용하여 Double Red 문제가 발생한 경우 기본적으로 Recoloring을 통해 해결할 수 있다. 자식 노드들이 부모 노드에게 Red를 모아서 넘겨준다고 생각하면 된다.
새로운 색칠로 해결이 안된다면, Rotate한다.
새로운 색칠이 가능한 경우는 Black Depth를 유지할 수 있는 경우이다.
위 그림은 새로운 노드가 추가 되었고 Double Red가 발생했지만, 삼촌 노드가 Black Node인 경우다. 이러한 경우에는 Red를 모아서 넘겨줄 수가 없다. 이 때는, Rotate를 사용해 균형을 맞춘다.
위 그림은 전체 Red-Black 트리의 일부라고 생각하면 된다. Rotate를 하며 각 노드의 위치가 변하더라도, 해당 위치의 Black Depth는 일정하게 유지되어야 한다.
현재 위치의 Black Depth를 파란색 숫자로 작성했고, 노드에 Key값을 임의로 설정했다.
만약 Recolor 기법과 같이 6번 노드를 Red로, 3번 노드를 Black으로 만든다면 어떤 문제가 발생할까?
위 그림에서 볼 수 있듯이 Double Red 문제는 해결되지만, 루트와 오른쪽 서브 트리의 Black Depth가 1씩 부족하다. 이 경우에 3번 노드를 6번 노드로 이동할 수 있다면, 오른쪽 서브트리에만 Black Depth를 1씩 증가시킬 수 있지 않을까?
위와 같이 오른쪽으로 Rotate를 하게 되면, 왼쪽 서브 트리는 Black Depth가 유지되고 오른쪽 서브 트리 전체에 Black Depth가 +1되는 효과를 얻을 수 있다.
위 그림은 전체 과정이다. NIL 노드에 번호를 붙여 노드가 더 많은 경우 어떻게 이동하는 지 알 수 있다.
Rotate를 이용한 Reconstruct를 간단한 정렬을 통해 쉽게 구현할 수 있다.
Double Red가 발생했을 때, 삼촌 노드가 Black 노드라면 위와 같이 Rotate를 적절하게 사용해서 해결할 수 있다. 이를 쉽게 구현하기 위해 다음과 같은 방법을 사용한다.
- 새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬한다.
- 중간값을 부모로, 나머지 둘을 자식으로 만든다.
- 새로운 부모를 Black 노드로 자식을 Red로 만든다.
Right Rotation과 결과가 같다.