1. 설명
Dictionary ADT(Abstract Data Type; 추상 자료형)를 구현하는 방법은 여러 가지가 있다. 그중 하나인 Binary Search Tree(이하 BST)는 평균 O(logN)의 삽입, 삭제, 탐색 시간을 가지지만, 최악의 경우 O(N)의 시간 복잡도를 가진다. 이렇게 최악인 경우는 BST에서 원소들이 한 방향으로만 쏠리게 되면 생기게 된다. Best인 케이스는 Tree가 Complete Binary Tree이겠지만 현실은 그렇게 호락호락하지 않다. 그래서 편하게 BST로 구현하고 Worst가 O(N)인 상황을 기도로 피하기에는 여러 가지 애로사항들이 많다.
Red-Black Tree는 BST가 가진 문제들을 해결해 줄 수 있다. Wikipedia에는 Red-Black Tree를 이렇게 정의하고 있다.
A red-black tree is a kind of self-balancing binary search tree in computer science.
Wikipedia
여기서 두 가지 사실을 볼 수 있다. Self-balancing이라는 말과 BST라는 것. 즉, BST이지만 어떤 특수한 조건을 만족해서 Self-balancing을 가능하게 한다는 것이다. Red-Black Tree는 이름에서도 알 수 있듯이 노드의 색이 Red 아니면 Black이다. 이 색과 어떤 특정한 조건을 활용하여 Worst Case 삽입, 삭제, 탐색을 모두 O(logN)에 가능하게 만들 수 있다. Red-Black Tree는 BST의 조건 외에도 추가적으로 4가지의 조건을 만족한다.
1. Root Property : Root 노드는 Black이다.
2. External Property : 모든 leaf 노드는 Black이다.
3. Internal Property : Red 노드의 자식 노드들은 Black이다.
4. Depth Property : 모든 leaf 노드들은 동일한 Black Depth를 가진다.
여기서 Black Depth라는 용어가 나오는데, Black Depth는 해당 노드에서 Root 노드까지의 Black 노드들의 개수를 의미한다. 사실, Red-Black Tree를 유지하기 위해서 가장 신경을 써줘야 할 부분은 Internal Property이다. Insertion을 하다 보면 Red 노드의 부모가 Red인 Double Red 상황이 발생하기 때문에 이것을 적절히 잘 처리해 주는 것이 Red-Black Tree의 핵심이라고 할 수 있다.
2. 연산
기본적으로 BST의 형식을 따라가기 때문에 삽입, 삭제, 탐색 연산이 가능하다. 삭제와 탐색은 거의 동일하지만 삽입 연산에서 많은 차이가 있기 때문에 여기에 대해서 중점적으로 하려고 한다.
Insertion
BST와 동일하게 Root 노드부터 대소 비교를 하면서 자기 자리를 찾아간다.
External 노드 중 하나를 지우고 삽입할 값을 넣고 External 노드를 두 개 달아준다.
이때 새로 달아주는 노드의 색은 Red이다. 앞에서 말했다시피 새로 달아주는 노드의 색이 Red이기 때문에 Double Red인 상황이 발생할 수 있다.
Double Red 처리하기
노드를 새로 달아주고 달아준 노드부터 순차적으로 4가지 조건들을 만족하는지 확인하면서 올라가기 때문에 자신이 Red이고 자신의 부모 노드가 Red 이면 Double Red가 발생했다고 생각하고 이를 처리한다. 처리하는 방법은 상황에 따라 두 가지로 나눌 수 있다. 첫 번째는 자신의 부모 노드의 형제 노드가 Black 경우이고, 두 번째는 Red인 경우로 나눌 수 있다. 전자의 경우에는 Restructuring이 필요하고 후자의 경우에는 Recoloring이 필요하다. 그림으로 표현하면 다음과 같다.
① Rectructuring
Restructuring은 Double Red가 발생한 Subtree의 구조를 변경함으로 Double Red 문제를 해결한다. 그림으로 표현하면 다음과 같다.
그림을 보면 위의 4가지 상황이 모두 한 가지의 결과로 바뀌는 것을 볼 수 있다. 각 연산들을 수행할 때 위에서 말한 4가지 속성들이 맞춰지고 있는지 계속 검사하면서 연산들을 수행해야 한다. 각각의 조건들이 잘 지켜지고 있는지 확인해보자.
Root Property -> Subtree의 Root가 Black이기 때문에 이 Subtree의 Root가 전체 Tree의 Root이더라도 만족한다.
External Property -> External 노드의 색을 바꾸거나 순서를 뒤집는 일이 없으므로 만족한다.
Internal Property -> 각각의 케이스를 1~4번 케이스라고 하면 1, 4번의 경우에서 t0의 색이, 2, 4번의 경우 t3의 색이 Red 이면 Double Red가 발생한다고 생각할 수 있다. 하지만 애초에 Restructuring이 호출되는 조건이 t0가 Black 일 때 호출하기 때문에 Red가 될 수 없다. 또한 Insertion가 될 때마다 Double Red가 있는지 검사하기 때문에 첫 번째 그림에서 w에 해당하는 Subtree에서는 조건들을 모두 만족하고 있다. 마지막으로 위에서 특별히 언급한 노드들을 제외하고는 원래 Red 밑에 있던 노드들이기 때문에 Red가 될 수 없다.(밑에서부터 검사해서 올라왔기 때문에 + 반대쪽 Subtree의 Root는 Black이기 때문에 - Restructuring 호출 조건). 따라서 Internal Property도 만족한다.
Depth Property -> 그림을 보더라도 Root까지의 경로에서 Black 노드의 수가 변함이 없음을 알 수 있다.
Restructuring은 한 번의 구조 변화로 Double Red가 해결이 된다. 따라서 O(1)의 시간 복잡도를 가진다.
② Recoloring
Recoloring은 문제가 되는 노드들의 색을 적절히 변경함으로써 Double Red를 해결한다. 그림으로 표현하면 다음과 같다.
Recoloring도 마찬가지로 4가지의 속성들을 만족하는지 확인해보자.
Root Property -> 만약 이 Subtree가 전체 Tree라면 Root를 Black으로 바꿔준다.
External Property -> External 노드의 색을 바꾸거나 순서를 뒤집는 일이 없으므로 만족한다.
Internal Property -> Recoloring을 하게 되면, Double Red인 부분을 Internal Property를 만족하는 방향으로 변경하기 때문에 만족한다.
Depth Property -> 이 속성은 두 가지에서 걸릴 수 있는데, 먼저 Root Property에서 언급한 대로 Root가 전체 Tree의 Root일 경우 Root Property를 만족시키기 위하여 Black으로 바꿔줘야 하는 경우가 있다. 이 경우는 Tree 전체의 Black Depth가 1 증가하는 경우로 볼 수 있다. 또, Internal Property를 만족시키는 과정에서 Black 노드의 수가 변경될 수 있다. 하지만, 그림에서 볼 수 있듯이, 4의 Black이 2와 7에 각각 전파되는 느낌으로 이해를 한다면 4를 기준으로 좌측 Subtree와 우측 Subtree가 동일한 Black Depth를 가지게 되는 것을 볼 수 있다.
Recoloring은 Double Red가 발생한 Subtree가 전체 Tree라면 Subtree의 Root 노드를 Black으로 바꾸고 끝낼 수 있지만 그렇지 않은 경우에는 Subtree의 Root 노드가 Red로 남게 된다. 따라서 Subtree의 Root 노드의 부모가 Red라면 Double Red가 발생할 수 있다. 정리해보면, Recoloring을 한 번 수행하는 데 걸리는 시간은 O(1)이지만 Bottom-up 방식으로 올라가면서 최대 O(logN) 번 다시 호출될 수 있기 때문에 최악의 경우 O(logN)의 시간 복잡도를 가진다.
이제 Insertion의 시간 복잡도를 분석해보자. 먼저 BST의 Insertion처럼 삽입되는 값이 자기 자리를 찾아간다(O(logN)). 그다음에는 Double Red가 발생했는지를 확인한다. Restructuring을 호출해야 하는 경우에는 O(1)에 실행할 수 있지만, Recoloring을 호출해야 하는 경우에는 Worst Case O(logN) 만큼 호출해야 하기 때문에 O(logN)의 시간 복잡도를 가진다.
따라서 Insertion의 시간 복잡도는 O(logN)+O(1) or O(logN)+O(logN)이므로 Worst Case O(logN)이다.
최종적으로 연산들의 시간 복잡도를 생각해보면, Red-Black Tree는 제일 얕은 Depth와 깊은 Depth가 두 배 관계보다 작다. 또한 Red-Black Tree의 높이는 O(logN)에 Bound 된다. Red-Black Tree의 높이에 대한 증명은 아래의 링크로 대체한다.
https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Proof_of_asymptotic_bounds
Red-Black Tree의 높이가 O(logN)에 Bound 되기 때문에, 탐색은 O(logN)에 가능하다.
삭제의 경우에는 Red 노드가 지워졌을 경우에는 추가적인 연산이 필요 없지만, Black 노드가 지워졌을 경우에는 4가지의 속성을 만족하는지 검사하면서 Black Depth와 Double Red를 맞춰주기 위한 추가적인 연산이 필요하다.
정리해보면,
Insertion - O(logN)
Deletion - O(logN)
Search - O(logN)
Height of Tree - O(logN)로
정리할 수 있다!
(---------만세 드디어 끝났다---------)