이진 탐색 트리의 한계와 이를 보완하는 Red Black Tree

Red Black Tree는 이진 탐색 트리의 일종이고, 이진 탐색 트리는 이진 트리의 일종이다.

 

이진 트리는 단순히 자식이 최대 2개인 트리로 그냥 위상적 개념이니 넘어가고, 이진 탐색 트리는 이 이진 트리에다가 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다는 규칙을 적용해 탐색을 용이하게 만든 트리구조이다.

이러한 이진 탐색 트리에서 탐색을 진행할 시, 탐색에 소요되는 시간는 최대 트리의 깊이가 되며 이는 평균 시간복잡도 O(logn)으로 표현된다.

하지만 평균 O(logn)의 시간복잡도는, 트리의 구성에 따라 최대 O(n)까지 늘어나게 된다. 예를 들어 루트 노드 생성 후 트리에 새 엘레먼트의 삽입이 항상 이전 값보다 큰 값만 들어올 경우, 트리의 깊이는 n이 되며 이는 linked list와 위상적으로 같다. 당연히 탐색에 걸리는 시간은 O(n)이다.

 

이처럼 이진 탐색 트리에서 탐색의 최악 시간복잡도는 트리의 깊이에 비례하고 이는 트리의 컨디션에 따라 늘 다르다. 이런 문제를 해결하기 위해 고안된 Red Black Tree는 트리의 깊이를 logn 선에서 유지시키기 위한 규칙들이 존재한다. RB트리의 각 노드 객체는 Red와 Black이라는 객체변수를 갖는데, 루트와 리프는 항상 Black이다. 또한 Red인 노드는 서로 연결될 수 없으며, 루트부터 각 리프를 연결하는 모든 부분그래프는 Black 노드의 출현 개수가 같다.

 

이러한 규칙을 적용했을 때 대체 왜 트리 깊이가 logn 선에서 균형을 유지하는지는 그래프 이론을 수학적으로 깊게 파야할테니 넘어가자. 알고리즘을 고안한 사람이 잘 증명했을 거라 믿는다... 대신 노드의 삽입과 삭제의 반복에서도 이러한 규칙을 유지하기 위해, RB트리만의 삽입, 삭제 로직이 어떻게 동작하는지에 대해 다뤄보자.

 

삽입 연산에서는 일단 이진 탐색 트리의 규칙에 따라 자기 위치에 삽입된 노드를 Red로 칠한다. 이를 통해 루트-리프 부분그래프의 Black 출현 개수는 유지된다. 하지만 이로 인해 두 Red 노드가 연결될 수 없다는 규칙의 위반이 발생할 수 있는데, 이때는 두 Red 노드의 주변 컨디션에 따라 둘중 하나의 색의 Black으로 바꾼다. 이에 따라 루트-리프 부분그래프의 Black 출현 개수 규칙에 위반이 생길 경우, 자식 중 하나가 부모가 되고 부모는 반대편 자식이 되는 rotation 과정을 거쳐 규칙을 만족하도록 수정한다.

 

삭제 연산도 마찬가지로, 일단 삭제하고 룰 위반이 발생한다면 각 케이스에 따라 다른 수정 과정을 거친다. 예를 들어 삭제하는 노드가 Black일 경우 반드시 Black의 출현 개수가 달라지는데, 이때 자식 중 Red 노드가 있다면 그것을 삭제 노드의 위치에 연결 후 Black으로 칠하는 것으로 출현 개수를 복구할 수 있고, 둘 모두 Black인 경우 주변 노드의 컨디션에 따라 적절한 노드에 대해 rotation 및 recoclor를 실행해야 복구가 가능하다.

 

RB트리는 "worst case의 시간복잡도를 줄인다"는 강력한 효용을 갖고 있기 때문에 이진 탐색 트리의 상위 호환에 가깝지만, 단점도 존재한다. 먼저 위의 복잡한 규칙 및 그 준수를 위한 삽입/삭제 연산이 이해와 구현상의 어려움으로 존재하고, 구현에 성공했다 하더라도 이 유지보수 과정 전체가 오버헤드로 작용한다.

 

가장 큰 유의점은 값이 같은 노드가 트리상에 존재해서는 안된다는 것이다. 단순 이진 탐색 트리는 값이 같은 노드를 항상 왼쪽, 항상 오른쪽 등 임의로 fix하는 것으로 값이 중복되는 노드도 관리가 가능하지만, RB트리는 값이 같은 노드가 중복 존재하여 서로 부모자식 관계일 경우, 위의 삽입 삭제 과정의 rotation에 의해 트리 부모자식간의 대소관계가 깨질 수 있다. 이를 개선하기 위해서는 값이 같은 노드간에 고유성이 없을 시 객체변수로 중복값의 갯수를 관리하거나, 고유성이 존재할 경우 등장시 트리의 2차원 구조와는 독립적인 3차원의 방향으로 linked list를 추가적으로 생성하는 등의 구현이 필요하다.