[자료구조] RB Tree(레드-블랙 트리)

 

RB Tree란? 

Red-Black Tree는 이진 탐색 트리의 한 종류이다. 가장 기본적인 형태의 이진 탐색 트리는 최악의 경우 트리의 높이가 n으로 나타나 비효율적인 면이 있는데, 이를 보완하기 위해 삽입 또는 삭제 연산 시 트리의 균형을 맞추는 트리들이 나타났다. 이를 자가 균형 트리라고 부르며, 대표적으로 AVL Tree와 Red-Black Tree가 있다. 이번에는 Red-Black Tree에 대해 알아보자. 

 

RB Tree에는 총 다섯 가지의 규칙이 있으며, 이 규칙을 통해 트리의 밸런스를 유지한다. 다섯 가지의 규칙은 아래와 같다. 

 

RB Tree의 다섯 가지 규칙

1. 모든 노드는 빨간색 혹은 검은색 노드이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드들은 검은색이다. 
4. 빨간색 노드의 자식은 검은색이다.
5. 루트 노드에서 리프 노드까지 거쳐가는 검은 노드의 개수가 모든 리프 노드에 대해서 같아야한다.

규칙을 보고 다시 위의 그림을 보면 모든 리프 노드가 검은색이라는 3번 규칙에 어긋나있는 것처럼 보인다. 하지만 실제 RB Tree를 구현할때 삽입되는 모든 노드들은 검은색을 가진 더미 노드들을 자식으로 갖게 되고, 위의 그림에서 리프 노드처럼 보이는 노드들은 이러한 더미 노드들을 자식으로 갖고 있다. 따라서 실제 리프 노드들은 모두 이 더미 노드들이 된다. 

 

RB Tree는 위의 다섯 가지 규칙을 지키며 균형을 유지한다. 

삽입과 삭제 연산을 하게되면 이 규칙이 위배되는 경우가 있는데, 이러한 경우 리밸런싱을 진행한다. 리밸런싱이 어떠한 과정으로 진행되는지 알아보자! 

 

 

Insert

 

먼저 삽입 연산이다. 삽입되는 노드가 트리의 black depth를 변경시켜서는 안되므로, 삽입되는 노드는 항상 빨간색임에 주의하자! 이진 탐색 트리와 마찬가지로 삽입되는 노드는 항상 리프 노드에 추가된다. 

 

삽입의 경우 크게 네 가지 CASE로 나눌 수 있다. 

 

 

CASE 0: 삽입되는 노드의 부모가 검은색인 경우

이 경우에는 빨간색 노드가 추가된다고 해서 위의 다섯 가지 규칙 중 어긋나는 것이 없기 때문에 별다른 리밸런싱이 진행되지 않고 연산을 종료한다. 

 

 

 

CASE 1, 2: 삽입되는 노드의 부모가 빨간색이고, 삼촌 노드의 색깔이 검은색인 경우 

이 경우 CASE 1과 CASE 2를 나눈 기준은 삽입된 노드가 부모 노드의 왼쪽 자식인지, 오른쪽 자식인지의 여부이다. 또한 CASE 1, 2는 parent node가 grand parent node의 왼쪽 자식인지, 오른쪽 자식인지에 따라 연산이 대칭적으로 발생한다. 즉, 원래 left rotate가 진행되는 상황이었으면 대칭적인 상황에서 right rotate가 발생한다. 

 

CASE 1을 그림으로 나타내면 아래와 같다. 

그림을 보면 빨간색 노드가 연속해서 나타난 것을 볼 수 있다. 이러한 상황을 Double Red라고 부르며, 4번 규칙을 위배하는 상황이다. 이를 해결해주기 위해 우선 트리를 parent node를 기준으로 오른쪽으로 회전시킨다. 

 

 

 

트리를 회전시키고 parent node와 grand parent node의 색깔을 바꿔주는데, 이렇게 되면 double red 현상이 해소된다. 또한 uncle node의 입장에서도 위쪽에 검은 노드가 하나 있는 것은 초기 상태와 동일하기 때문에 black depth는 변하지 않는다. CASE 1의 경우 이러한 방식으로 규칙을 만족시킬 수 있다. 

 

다음으로 CASE 2의 경우인데, 이는 CASE 1의 예시에서 삽입된 노드가 parent node의 오른쪽에 위치한 경우이다. 

위와 같은 상황에서 이번에는 삽입된 노드를 기준으로 왼쪽으로 회전을 시킨다. 

 

 

 

회전을 시키고 나면 위와 같은 결과를 얻을 수 있는데, 이는 CASE 1의 상황과 동일하기 때문에 CASE 1에서 한 것과 같이 진행을 하면 double red를 해결할 수 있다. 

 

 

 

 

 

CASE 3: 부모 노드와 삼촌 노드가 모두 빨간색인 경우 

이번에는 위의 상황과 달리 삼촌 노드까지 빨간색인 경우이다. 일단 그림을 살펴보자. 

그림의 상황에서 부모 노드와 삼촌 노드의 색깔을 모두 검은색으로 바꾼 뒤, 조부모의 색깔을 빨간색으로 바꾸면 트리 전체의 black depth를 유지할 수 있다. 

하지만 조부모의 위에 또다른 빨간색 노드가 존재할 수 있기 때문에, 색을 모두 바꿔준 뒤에 조부모 노드에 대해 다시 CASE 0 부터 검사를 진행한다. 이때 만약 조부모가 트리의 루트와 같다면 조부모의 색깔을 검은색으로 바꾼 뒤 종료한다. 이는 트리의 전체 black depth를 1만큼 늘리는 것과 같다. 

 

 

위와 같이 다섯 가지 규칙을 모두 만족시키면서 삽입을 진행할 수 있다. 이 과정을 통해 트리의 밸런스가 유지되고 트리의 높이가 항상 $log n$의 형태로 유지된다. 

 

 

 

 

 

Delete

이번에는 삭제에 대해 살펴보자. 삭제는 삽입보다 조금 더 복잡하다... 우선 삭제할 노드를 선정하는 것도 조금 복잡한데, 크게 두 가지로 나누어 살펴볼 수 있다. 

 

 

1. 삭제할 노드의 자식이 하나이거나 없는 경우

1번의 경우 비교적 간단하다. 삭제할 노드가 만약 자식이 있다면, 삭제할 노드의 부모와 자식을 연결해준 뒤, 삭제할 노드는 지워주면 된다. 이때 실제로 트리에서 사라지는 색깔은 삭제된 노드의 색깔과 같다.

그림으로 살펴보면 아래와 같다.

 

 

2. 삭제할 노드의 자식이 둘인 경우

2번의 경우를 그림으로 나타내면 위와 같다. 이번에는 1번처럼 밑에 있는 자식을 바로 위로 올리는것이 아니라, 우선 중위 순회를 기준으로 삭제할 노드 다음에 위치할 노드(successor)를 찾는다. 

 

그 다음 successor의 key 값을 삭제할 노드로 옮겨주고, 실제로 삭제되는 노드는 successor node가 된다. 위의 경우와 마찬가지로 만약 successor node가 자식이 있었을 경우 successor의 부모와 자식을 연결해주고 지워야한다. 이때 successor node는 자식이 둘일수 없기때문에 1번과 비슷한 상황이 만들어진다. 

이때 트리에서 실제로 지워지는 색깔은 successor node의 색깔이 된다.

 

이제 트리에서 지워진 색깔에 따라 리밸런싱이 진행된다. 삭제 연산은 총 여섯 가지가 존재한다. 

 

CASE 0: 지워진 노드의 색깔이 빨간색인 경우  

먼저 지워진 색깔이 빨간색인 경우를 생각해보자. 트리에서 빨간색이 지워진 경우에는 double red가 생길 위험도 없고, 트리 전체의 black depth가 변할 일도 없다. 따라서 그 어느 규칙에도 위배되지 않으므로 특별한 리밸런싱 없이 연산이 종료된다.

 

 

 

 

이후 CASE들은 모두 지워진 노드의 색깔이 검은색인 경우이다. 검은색 노드가 지워지면 노드가 지워진 경로의 black depth가 1씩 감소하기때문에 5번 규칙에 어긋나게 된다. 따라서 지워진 노드의 경로에 검은색 노드가 하나 더 추가되어야 하고, 이를 표시하기 위해 지워진 노드를 대체한 노드에게 extra black을 부여한다. 앞에서 노드를 삭제하는 경우를 하나 예시로 들어보면 아래와 같다.

위의 그림처럼 검은색 점을 옆에 찍어서 표시하자. 이제 이 extra black이 추가된 경우들을 나누어 살펴보자.

 

 

CASE 1: extra black이 붙은 노드가 빨간색인 경우

이 경우 빨간색인 노드만 검은색으로 바꿔주면 double red도 생기지 않고 black depth도 1이 추가되기 때문에 extra black을 해결할 수 있다. 다른 CASE에 비해 비교적 간단하게 해결이 가능하다. 

 

 

 

 

CASE 2: 형제 노드가 검은색이고 형제 노드의 바깥 자식이 빨간색인 경우

앞으로 소개할 CASE 2와 CASE 3, 그리고 CASE 5의 경우는 위의 삽입의 CASE 1, 2와 같이 대칭적인 연산이 발생한다. 설명의 편의를 위해 트리의 바깥쪽에 위치하는 노드를 바깥 자식으로, 안쪽에 위치하는 노드를 안쪽 자식으로 표현하였다. 그림에서는 바깥 자식을 out으로, 안쪽 자식을 in으로 표현하였다.

먼저 아래 그림은 CASE 2를 나타낸 것인데, 색깔을 특정할 수 없는 노드는 모두 초록색으로 표현하였다. 

먼저 그림과 같은 상황을 고려해보자. 지금 왼쪽 경로에 검은 노드가 하나 더 필요한 것을 알 수 있다. 따라서 먼저 트리를 형제 노드(S)를 기준으로 왼쪽으로 회전시키고, P와 S의 색깔을 바꿔줄 것이다. 

회전 이후 결과는 위와 같다. extra black이 있던 노드의 입장에서 살펴보면, 위에 초록 노드만 있던 상황에서 검은 노드가 추가되었기때문에 black depth가 1이 추가된 것을 알 수 있다. 따라서 extra black을 해결한 것이 된다. in node 또한 마찬가지로 위에 초록 노드 하나와 검은 노드 하나가 있는 것이 초기 상황과 같기 때문에 black depth는 초기와 같이 유지된다. 

하지만 마지막으로 out node의 경우 원래 초록 노드와 검은 노드가 하나씩 있었는데 회전 이후에는 위에 초록 노드만 있는 것을 볼 수 있다. 따라서 black depth가 1이 줄어들었고, 이를 해결해주기 위해 out node의 색깔을 검은색으로 바꿔준다. 원래 out node의 색깔이 빨간색이었기때문에 검은색으로 바꿔도 다른 규칙을 위배하지 않는다. 

 

최종적인 결과는 아래와 같다. 

그림을 보면 모든 문제가 해소된 것을 볼 수 있다. 

 

 

 

 

 

 

 

CASE 3: 형제 노드가 검은색이고 바깥 자식도 검은색, 안쪽 자식은 빨간색인 경우 

위와 같은 경우, 먼저 in node를 기준으로 오른쪽 회전을 시켜준다. 회전을 시키고나면 다음과 같다. 

 

위의 그림을 보면 S가 있는 경로는 black depth가 회전 이전과 딱히 달라지지 않지만, in node의 왼쪽 서브트리의 black depth는 원래 위에 있던 S가 없어졌으므로 1이 줄어들게 된다. 또한 원래 P가 빨간색일 가능성도 있기때문에 추가적인 조치가 필요하다. 이를 위해 in node와 S의 색깔을 바꿔준다. 

 

색깔을 바꿔주고나면 더이상 문제가 발생하지 않는다. 하지만 여전히 extra black은 해소되지 않았다. 이제 그림을 잘 보면 CASE 2와 같아진 것을 볼 수 있다. 따라서 CASE 2에서 한 것과 같이 진행하면 extra black을 해소할 수 있다. 

 

 

 

 

CASE 4: 형제 노드가 검은색이고, 형제의 자식 노드들도 모두 검은색인 경우 

이번에는 노드가 전부 다 검은색인 경우이다. 이때 (S가 검은 노드) == (S가 빨간색이고 extra black이 붙은 경우) 라고 생각할 수 있다. 따라서 아래와 같이 표현이 가능하다. 

이제 P의 자식들이 모두 extra black을 가지고 있다. 이는 P의 자식들이 모두 검은 노드를 하나 더 필요로 한다는 의미이고, 따라서 P의 경로에 검은 노드가 하나 더 추가되면 자연히 밑의 extra black들도 해소될 것이다. 따라서 extra black을 P에게로 넘긴다. 

extra black이 위로 올라갔기 때문에, P에 대해 다시 CASE 0 부터 검사를 진행한다. 만약 P가 트리의 루트라면 규칙에 따라 색을 검은색으로 바꾸고 리밸런싱을 종료한다. 

 

 

 

 

 

CASE 5: 형제 노드가 빨간색인 경우

이제 마지막 경우이다! 지금까지의 경우를 살펴보면 모두 CASE 1 또는 CASE 2의 상황과 같게 만들어 해결하려는 것을 볼 수 있다. 이번 경우도 마찬가지로 해결한다. 형제 노드가 빨간색인 경우 형제 노드를 기준으로 형제 노드가 제일 위에 오게끔 회전을 시켜준다. 이때 P의 부모도 빨간 노드일 수 있기 때문에 P와 S의 색깔을 바꿔 double red를 방지한다. 

회전을 진행하고 나면 위의 그림과 같은 결과를 얻을 수 있는데, 이제 extra black이 붙은 노드의 입장에서 in node가 형제 노드가 되었고, in node는 항상 검은 노드이기 때문에  CASE 2, 3, 4의 경우로 돌아가 해결할 수 있다. 

 

 

 

삽입이나 삭제나 한 CASE에 대한 연산을 만들어두고, 다른 CASE 들을 특정 CASE의 형태로 만들어 해결하는 모습을 볼 수 있다. 따라서 기본적으로 불균형이 해소되는 연산을 기억해두고, 다른 CASE들을 BASE CASE로 만들어주려는 생각을 하면 쉽게 떠올릴 수 있을 것이다!