[CS] Red-Black Tree

BST의 일종

BST의 문제점을 해결하기 위해 탄생

 

BST의 문제점이란?

BST는 부모 노드의 왼쪽 자식 노드는 부모보다 작아야 하고 오른쪽 자식 노드는 부모보다 커야 한다.

이 조건을 만족하는 BST 중 다음을 생각해보자.

부모 노드보다 작은 자식만 생기게 되는 경우. 이 경우 왼쪽으로만 쭉 길어지게 된다. 탐색에 걸리는 시간 복잡도 또한 O(n)이 되고 만다. 삭제와 삽입 또한 마찬가지다.

이러한 상황을 불균형이라고 하는데 불균형을 해결하기 위해 red-black tree가 나오게 되었다.

 

Red-Black tree는 어떻게 해결했는가?

red-black tree를 활용하게 되면 worst case에서도 탐색, 삽입, 삭제를 모두 O(logn)에 할 수 있게 된다. 그 이유는 불균형이 발생하게 되면 원칙에 따라 재배열이 이루어져 균형이 잡힌다. Root Node로부터 최소 경로와 최대 경로의 비율 차이가 2를 넘지 않게 된다.