레드블랙 트리(red-black tree)

0. 출처

1) [알고리즘] 제12-1강 red black tree1

2) [알고리즘] 제12-2강 red black tree2

3) [알고리즘] 제12-3강 red black tree3

4) Introduction to Algorithms

1. 개요

1. 1 레드블랙 트리란

이진 탐색 트리에서 탐색, 삽입, 삭제의 시간 복잡도는 O(h)이다. 즉, 트리의 높이에 비례한 만큼의 시간이 걸린다. 원소들이 트리에 잘 분산되어 있다면 별 문제가 없으나, 한 쪽으로 치우친 트리(skewd tree)의 경우에는 높이가 n이 되고, 시간 복잡도도 O(n)이 된다.

 

랜덤하게 만들어진 이진 탐색 트리는 높이가 lgn임이 보장되나, 현실에서의 데이터는 랜덤하지 않다는 점이 문제가 된다. 예를 들어, 키가 정렬된 상태(1...10)로 트리에 삽입된다고 하자. 그렇다면 1이 루트가 되고, 2는 1보다 크므로 1의 오른쪽에 가고, 3은 2보다 크므로 2의 오른쪽에 간다. 이런 식으로 skewd tree가 만들어진다.

 

레드블랙 트리는 삽입이나 삭제를 할 때 트리가 한쪽으로 너무 치우치지 않도록 추가적인 작업을 해줌으로써 어느 정도 균형을 맞춰주는 것이다.

 

 

레드블랙 트리의 기본 구조는 이진 탐색 트리의 구조와 같은데, 거기에 추가로 가상의 노드를 만들어야 한다. 자식 노드가 존재하지 않을 때 'NIL'이라는 특수한 노드를 가지게 한다. 그렇기 때문에 모든 리프 노도는 NIL 노드가 된다. 또한 루트 노드의 부모 노드도 NIL 노드로 둔다. 즉, 레드블랙 트리에서 사용되는 노드들은 NIL 노드와 NIL 노드가 아닌 내부 노드로 구분할 수 있다. (여기에서 나온 NIL 노드는 프로그램을 만들 때 실제로 추가하는 것은 아니다. 설명의 간편성을 위해 가상의 노드를 고안해낸 것이다)

 

1. 2 레드블랙 트리의 조건

이진 탐색 트리 중 다음과 같은 조건들을 만족하는 것만이 레드블랙 트리다. 외워두는 것이 좋다.

1. 각 노드는 빨간색(red) 혹은 검은색(black)이다. (위 그림에서 회색이 빨간색이다)

2. 루트 노드는 블랙이다.

3. 모든 리프 노드는 블랙이다. 즉, NIL 노드는 모두 블랙이다.

4. 레드 노드의 자식은 모두 블랙이어야 한다.

5. 모든 노드에 대해 그 노드로부터 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 블랙 노드가 존재한다.

 

1. 3 h와 bh

h와 bh를 배우는 이유는 탐색, 삽입, 삭제와 같은 연산을 O(lgn) 안에 할 수 있다는 것을 증명하기 위함이다.

 

 

노드 x의 높이 h는 자신으로부터 리프 노드까지의 가장 긴 경로에 포함된 에지의 개수다. 예를 들어, 노드 15의 높이는 15-6-7-13으로 이어지는 것이 가장 길기 때문에 4다.

 

노드 x의 블랙-높이 bh는 자신으로부터 리프 노드까지의 경로 상에 있는 블랙 노드의 개수다.(노드 x 자신은 포함시키지 않는다.) 예를 들어, 노드 7의 bh는 7-13-NIL로 이어지므로 자신을 제외한 블랙 노드는 NIL 하나다. 또한 노드 x로부터 왼쪽으로 가든 오른쪽으로 가든 bh는 일정하다.(조건 5에 의해). 예를 들어, 15에서 왼쪽으로 가도 bh는 2고, 오른쪽으로 가도 bh는 2다.

 

1.4 레드블랙 트리의 높이

우선 루트가 x인 노드의 서브트리는 적어도 $2^{bh(x)}-1$개의 내부 노드를 가짐을 증명해보자. h(x)에 대한 수학적 귀납법으로 증명할 수 있다. h(x)가 0이면 x는 NIL 노드이므로 이 노드를 루트로 하는 서브 트리는 적어도 $2^{bh(x)}-1 = 2^0-1 = 0$개의 내부 노드를 가진다. 귀납적 단계로써, 노드 x가 양의 높이를 가지고 두 자식을 가지는 내부 노드라 하자. 각 자식은 자신의 색깔이 레드이냐 또는 블랙이냐에 따라 bh(x) 또는 bh(x) - 1의 높이를 가진다. 적어도 몇 개의 내부 노드를 가지는가를 알아보는 문제이기 때문에 둘 다 bh(x) - 1의 높이를 가진다고 봐도 문제 없다. 따라서 x를 루트로 하는 서브 트리는 적어도 $(2^{bh(x)-1}-1)+(2^{bh(x)-1}-1)+1=2^{bh(x)}-1$개의 내부 노드를 가지므로 앞의 명제가 증명되었다.

 

또한 조건 4에 의해 루트에서 리프로 가는 단순 경로(루트 제외)의 노드 중 절반 이상이 블랙이다. 즉, 루트의 bh(x)는 적어도 h / 2다.

($n≥2^{h/2}-1$)

 

내부 노드의 수를 구할수 있게 되었으니, 내부 노드의 개수에 따라 높이가 어떻게 결정되는지 보자. 내부 노드가 n일 때

$n≥2^{bh(x)}-1≥2^{h/2}-1$이므로 $n+1≥2^{h/2}$로 바꾸고, 양변에 로그를 씌우면 log(n + 1) ≥ h / 2, 즉 h ≤ 2log(n + 1)이 된다.

 

h ≤ 2log(n + 1)이라는 사실에 의해 탐색, 삽입, 삭제와 같은 연산은 레드블랙 트리를 이용하면 O(lgn) 시간에 수행할 수 있음을 알 수 있다.

 

2. 회전

삽입과 삭제를 배우기 전에 회전을 배워야 한다. 회전은 한 노드를 중심으로 부분적으로 노드의 모양을 수정하는 것이다. 회전을 하더라도 이진 탐색 트리의 특성을 유지한다는 점이 중요하다.(레드블랙 트리는 회전하면 레드블랙 트리의 특성을 잃을 수 있다.)

 

 

Left-Rotate는 y를 x의 자리로 옮기고, x를 y의 왼쪽 노드로 옮긴다. Right-Rotate는 x를 y의 자리로 옮기고, y를 x의 오른쪽 노드로 옮긴다. 그림에 있는 알파, 베타, 감마는 서브트리다. 알바, 베타, 감마의 변화가 조금 헷갈렸는데 이렇게 이해하면 된다. 알파는 x, y보다 작고, 감마는 x, y보다 크다. 그리고 베타는 x보다는 크고, y보다는 작다. 일단 x와 y의 위치를 정하고 나서 크기에 따라 알파, 베타, 감마의 위치를 정하면 된다.

 

Left-Rotate

 

 

복잡해 보이지만 x의 부모, y의 부모, x의 오른쪽 자식, y의 왼쪽 자식, x 노드의 부모 노드의 입장에서 왼쪽 혹은 오른쪽 노드를 바꿔야 한다는 것만 숙지하고 보면 된다.

 

3. 탐색, 삽입, 삭제

3.1 Search

탐색 알고리즘은 이진 탐색 트리의 탐색 알고리즘과 동일하다. 여기서 따로 다루지는 않는다.

 

3. 2 Insert

 

 

레드블랙트리에서의 삽입은 이진탐색트리의 삽입과 거의 같다.

 

line 1-15) 이진탐색트리에 삽입할 때의 과정과 같다.

 

line 16) 새로 삽입되는 노드는 빨간색이다.

 

line 17) 삽입 후에 레드 노드가 연속해서 등장한 경우에는 red-red violation(레드-레드 위반)이 발생하므로 이것을 고쳐주기 위해 RB-INSERT-FIXUP으로 조정한다.(사실 z가 루트 노드에 삽입될 경우에도 조건 2인 '루트 노드는 블랙이어야 한다'가 위반된다. 하지만 이 경우에는 삽입 후 루트 노드를 블랙으로 바꿔주면 되므로 큰 문제가 없다.)

 

RB-INSERT-FIXUP

RB-INSERT-FIXUP 함수는 6가지 Case로 나뉜다.

 

Case 1, 2, 3은 삽입되는 z의 부모 노드가 할아버지 노드의 왼쪽에 있다.

 

Case 4, 5, 6은 반대로 오른쪽에 있는 경우다.

 

1, 2, 3과 4, 5, 6은 서로 대칭되기 때문에 1, 2, 3만 배우면 된다.

 

Case 1

 

 

(부모 노드가 레드인데, 레드 노드는 루트 노드가 될 수 없으므로 블랙인 할아버지 노드가 반드시 존재한다.)

 

Case 1은 z와 z의 부모 노드가 레드이고, 삼촌 노드도 red인 경우를 말한다. (삼촌 노드란 부모 노드의 형제 노드) (삽입되는 노드가 부모 노드의 왼쪽에 있든, 오른쪽에 있든 상과없다)

 

이 경우에는 부모와 삼촌을 블랙으로 바꾸고, 할아버지 노드를 레드 노드로 바꾼다.

 

이렇게 하면 트리의 구조 자체를 바꾼 것은 아니므로 이진탐색 트리의 조건을 무너뜨리진 않는다.

 

조건 4를 만족하는가?

A, B, D 노드가 그들의 서브트리와 맺는 관계는 아무 문제가 없다.삽입되는 노드와 부모 노드, 삼촌 노드는 레드이므로 조건 4에 의해 그 자식 노드는 반드시 블랙 노드이기 때문이다.

 

하지만 할아버지 노드는 블랙이었다가 레드로 바뀌었으므로 할아버지의 아버지 노드와의 관계에서 red-red violation이 발생할 수 있다. 이 경우에는 할아버지 노드를 z로 설정해 다시 Case 1을 반복한다. 이 때 red-red violation이 두 레벨 올라간다. 즉, 무한히 반복되는 일은 없으며, 반복되는 횟수는 트리의 높이보다 많을 수 없다.

 

조건 5를 만족하는가?

Case 1의 경우에는 RB-INSERT-FIXUP을 실행하더라도 경로 상 블랙 노드의 수가 변함없다.

 

Case 2, 3

 

Case 2, 3은 z의 삼촌이 블랙인 경우다.

 

Case 2는 삽입되는 z 노드가 부모 노드의 오른쪽에 있는 것이고, Case 3는 왼쪽에 있는 것이다. Case 2는 z의 부모 노드에 대해 left-rotation을 해서 Case 3로 만든다. 이 과정에서 z 노드는 A 노드로 변한다.

 

Case 3에서는 아버지 노드를 블랙 노드로, 할아버지 노드를 레드로 만든 후, 할아버지 노드를 중심으로 right-rotation을 하면 된다.

 

즉, 삽입을 했을 때, Case 2라면 left-rotation을 하여 Case 3으로 바꿔 right-rotation을 하면 된다. 즉, 두 번의 연산으로 끝난다. 처음부터 Case 3였다면 right-rotaion 한 번으로 끝난다. 마지막으로 Case 1은 실행 결과에 따라 Case 1이 반복적으로 실행될 수도 있고, Case 2, 3, 4, 5, 6이 될 수도 있다.

 

조건 4를 위반하는가?

알파, 베타 감마의 경우에는 right-rotation 전이나 후나 부모가 레드 노드이기 때문에 블랙 노드다. 또한 델타의 경우 Case 3의 조건이 z의 삼촌이 블랙 노드인 경우이므로 블랙이다. 또한 새롭게 루트가 된 B 노드도 블랙 노드이기 때문에 부모 노드와 red-red violation을 발생시키지 않는다.

 

조건 5를 위반하는가?

블랙 노드는 z의 부모 노드 뿐이므로 조건을 만족한다.

 

수도 코드

 

 

레드블랙 트리 T에 z 노드를 삽입하는 수도 코드다.

 

line 1) z의 부모 노드가 레드인 경우에, 즉, red-red violation인 동안 while문을 반복한다. line 1에는 한 가지 조건이 빠져 있는데 z의 부모가 NIL 노드가 아니어야 한다는 것이다. NIL이라면 반복문을 돌지 않고 바로 빠져나오도록 해야 한다.

 

line 2) z의 부모의 부모, 즉 할아버지 노드의 왼쪽에 z의 부모 노드가 있다는 것으로 위에서 본 Case 1, 2, 3이 여기에 해당된다. 

 

line 15) z의 부모의 부모, 즉 할아버지 노드의 오른쪽에 z의 부모 노드가 있다는 것. 즉, Case 4, 5, 6

 

line 8) 할아버지 노드를 z 노드로 삼아 Case 1을 반복한다.

 

line 16) 여기까지 작업을 마치고 빠져 나오는 경우는 Case 3 혹은 Case 6을 마친 상태다. 이 때 루트 노드가 레드일 수 있으므로 블랙으로 바꿔준다.

 

시간 복잡도

Case 2, 3, 5, 6의 경우는 O(1)이 걸리고, Case 1, 4의 경우 O(lgn)이 걸리므로, 삽입 알고리즘의 시간 복잡도는 O(lgn)

 

예시

 

 

3. 3 Delete

 

 

이진탐색 트리의 삭제와 거의 유사하다.

 

line 1-15) 이진탐색 트리의 코드를 그대로 옮겨온 것.

 

삭제 이후 다음과 같은 문제가 생길 수 있다.

 

조건 2 위반) 지운 노드가 루트 노드인데 x가 레드 노드일 때

 

조건 4 위반) y 노드의 부모가 레드 노드이고 x 노드도 레드일 경우에 red-red violation이 발생

 

조건 5 위반) 가장 심각하고 해결하기 어려움. 여러 경로 중 한 경로의 블랙 노드만 하나 삭제되므로 조건 5가 위반될 수 있다.  이것을 해결하는 것이 DELTE의 핵심.

 

조건 2와 4의 경우에는 x 노드를 블랙 노드로 바꾸면 해결된다.

 

조건 5를 해결하기 위해서 RB-DELETE-FIXUP을 하는 것이고, 본격적으로 들어가기 전에 다음과 같은 사전 작업을 해준다.

노드 x에 "extra black"을 부여해 일단 조건 5를 만족하게 한다. 이 경우 노드 x는 (블랙, 블랙)이 된다. 이 경우 bh(x)는 적어도 2이기 때문에 x의 형제 노드는 NIL일 수 없다.

 

RB-DELETE-FIXUP은 8가지 Case로 나눌 수 있다. Case 1, 2, 3, 4는 x 노드가 부모 노드의 왼쪽에 있을 때이며, Case 5, 6, 7, 8은 오른쪽에 있을 때다. 이 둘은 서로 대칭이기 때문에 1, 2, 3, 4만 하면 5, 6, 7, 8도 알 수 있다.

 

Case 1

 

 

노드 x의 형제 노드인 w가 레드 노드인 경우다. 이 때 w의 자식인 C와 E는 NIL일 수 없다. NIL이라면 bh(B)가 왼쪽 경로로 가면 2가 나오고, 오른쪽으로 나오면 0이기 때문이다.

 

w를 블랙 노드로, x의 부모 노드를 레드 노드로 바꾼 후 x의 부모 노드를 기준으로 left-rotation한다.(x 노드가 한 레벨 내려간다) 결과인 오른쪽 그림을 보면 C 노드가 x의 새로운 형제가 된 것을 확인할 수 있다. 이렇게 됐다면 Case 2, 3, 4에 해당된다.

 

Case 2

 

 

Case 1이 w 노드가 레드인 경우였다면, Case 2, 3, 4는 블랙인 경우다. 그 중에서도 Case 2는 w의 두 자식이 모두 블랙 노드인 경우다. (Case 1에서는 w가 레드였으므로 부모 노드는 블랙이어야 했지만, Case 2의 경우에는 그런 제약이 없으므로 블랙일 수도 있고, 레드일 수도 있다)

 

이 경우에는 x로부터 extra-black을 빼앗고, w를 레드로 바꾼다. 그리고 부모 노드인 B에게 extra-black을 주는데, B가 원래 레드 노드였다면 그냥 블랙 노드로 바꾸고 끝내면 되는 일이지만, 원래 블랙 노드였다면 B 노드도 double-black 노드가 되므로 B 노드를 x로 삼아 다시 Case 2를 반복한다.

 

Case 3

 

 

Case 3의 결과로 w의 오른쪽 자식이 레드 노드가 된다. 여기부터는 Case 4이므로 Case 3은 여기서 마친다.

 

Case 4

 

 

Case 1, 2, 3, 4가 어떻게 진행되는지는 아래 그림을 살펴보면 한번에 알 수 있다.

 

 

Case 1, 3, 4의 경우에는 두 스텝 이내로 조정을 마칠수 있는 반면, Case 2는 경우에 따라 2가 반복될 수도 있고, 6이 될 수도 있고, 5, 7, 8이 되기도 한다. 처음부터 Case 2에 도착한 경우에는 이렇게 복잡한 반면, Case 1을 거쳐 2로 가는 경우는 한번에 마친다. (Case 1에서 2로 가는 경우에는 x의 부모가 레드 노드이기 때문이다)

 

수도 코드

 

 

RB-DELETE-FIXUP 함수의 파라미터인 x는 삭제한 노드의 자식 노드이다.

 

line 1) x가 루트 노드이거나 x가 레드 노드라면 line 23처럼 x를 블랙 노드로 만들고 끝내면 된다.

 

line 2-21) Case 1, 2, 3, 4. 즉, x가 부모의 왼쪽 노드

 

line 22) Case 5, 6, 7, 8. 자세히 설명하지 않음

 

line 3) x의 부모의 오른쪽 자식 노드(형제 노드)를 w로 둔다.

 

line 4) w가 레드인 경우. 즉, Case 1

 

line 9) w의 왼쪽, 오른쪽 자식이 모두 블랙인 경우. 즉, Case 2

 

line 12) w의 왼쪽 자식이 레드이며, 오른쪽 자식은 블랙인 경우. 즉, Case 3

 

line 11, 21) line 11에 걸려서 x를 x의 부모 노드로 만든다면 while문을 계속 돌고, line 21에 걸려서 x를 루트 노드로 하면 while문에서 빠져나간다.

 

DELETE의 시간 복잡도

BST에서 z 노드를 삭제하는 데 O(lgn)이 걸리고, RB-DELETE-FIXUP을 수행하는 데도 O(lgn)이 걸리므로 DELETE의 시간 복잡도는 O(lgn)이라고 할 수 있다.