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

이진검색트리는 저장과 검색에 평균 Θ()시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 균형잡힌 이진검색트리이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 레드블랙트리와 AVL트리다.

레드블랙 트리는 자가균형이진탐색 트리(self-balancing binary search tree)로써, 대표적으로 연관배열(associative array) 등을 구현하는데 쓰이는 자료구조이다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다. 트리에 n개의 원소가 있을때 Θ()의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

레드블랙 트리는 이진검색트리의 모든 노드에 레드 또는 블랙의 색상을 칠한다. 단, 다음의 성질을 만족하돍 색칠을 해야 하는데, 이를 레드블랙특성이라 한다.

1. 루트는 블랙이다.
2. 모든 리프(NIL)는 블랙이다.
3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
4. 로트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

여기서 말하는 리프 노드는 일반적으로 말하는 리프 노드와 의미가 다르다. 이진검색트리의 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프 노드라 부른다. 이것은 처음에는 다소 어색해 보일 수도 있지만 알고리즘에서 리프 노드가 개입될 때 특수 처리를 하지 않아도 되는 편리함이 있다.

위 조건들을 만족하게 되면, 레드블랙 트리는 가장 중요한 특성을 나타내게 된다. 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배보다 항상 작다. 다시 말해 레드블랙 트리는 개략적으로 균형이 잡혀있다. 따라서, 삽입, 삭제, 검색 시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(깊이)에 따라 결정되기 때문에 보통의 이진검색 트리에 비해 효율적이다.

위의 그림은 이진검색트리를 레드블랙트리로 만든 한 예다. 루트 노드는 블랙으로 칠이 되어 특성 1번을 만족한다. 임의의 노드에서 자식이 없는 쪽은 모두 NIL 리프를 붙이고, 모든 NIL 노드는 블랙으로 칠하여 특성 2번을 만족한다. 임의의 노드가 레드이면 그 자식은 반드시 블랙이라는 특성 3번을 만족한다. 루트에서 모든 리프 노드에 이르는 경로상에서 만나는 블랙 노드의 수는 항상 3개로 똑같아 특성 4번을 만족한다.

여기서 잠깐 실제 구현시에 NIL 리프를 어떻게 다루는지 살표보면 모든 NIL 리프 마다 하나씩의 노드를 할당하는 방법도 있으나 불편한 점이 많다. 대신, 노드 하나를 할당하여 이를 리프로 정하고 모든 NIL 리프에 대한 포인터가 이 노드를 가리키도록 하면 된다. 공간도 절약할 수 있을뿐더러 경계 조건을 다루기도 편리해진다. 위의 그림이 이를 보인다.

레드블랙 트리에서의 높이

노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 edge의 개수이다.

노드 x의 높이 bh(x)는 x로부터 리프 노드까지의 경로상의 블랙노드의 개수이다. (노드 x자신 불포함)

높이가 h인 노드의 블랙높이는 조건4에 의해 레드 노드가 연속될 수 없으므로 bh >= h/2 이다.

노드 x를 루트로 하는 임의의 부트리는 적어도 개의 내부노드를 포함한다.

n개의 내부노드를 가지는 레드블랙 높이는 이다. (n >= >= 이므로)

레드블랙 트리에서의 검색

레드블랙 트리에서의 검색은 트리의 내용을 건드리지 않으므로 이진검색 트리에서의 검색과 동일하다. 삽입과 삭제도 기본적으로는 이진검색트리와 동일하나 삽입이나 삭제 후 레드블랙특성을 위반하는 경우가 발생할 수 있따. 이때는 적절한 작업을 통해 레드블랙 특성을 만족하다록 바로잡아 주어야 한다.

레드블랙 트리에서의 삽입에 앞서 레드블랙특성을 유지하기 위한 방법들이 여러 존재하는데 그 중에 Left and Right Rotation 에 대해 잠시 살펴보고 가도록 합시다.

이진탐색트리의 특성을 유지하면서 왼쪽 혹은 오른쪽으로 회전하는 방법이다. 레드블랙트리에서는 삽입이나 삭제 후 레드블랙특성을 유지하기 위해 사용된다. 아래의 그림은 Left Rotation 의 한 예를 나타낸다.

y = right[x] ≠ NIL , 루트노드의 부모도 NIL 이라고 가정하에 슈도코드는 다음과 같다.

레드블랙 트리에서의 삽입

레드블랙 트리에서의 노드를 삽입할 때는 먼저 이진검색트리의 삽입 알고리즘에 따라 삽입을 한 다음 새 노드의 색상을 레드로 칠한다. 이 노드를 z 라고 하자. 새 노드는 항상 맨 아래쪽에 매달리므로 삽입 직후에 z의 아래쪽은 블랙 노드인 리프 두개만이 있으므로 레드블랙특성을 위반하지 않는다. 하지만 z의 위쪽에서 z가 루트 노드이면서 레드이거나, z와 그 부모 p[z]가 둘다 red 인 경우 위반이 일어난다. 이를 해결하기 위해서는 부모노드 p[z]가 블랙이 되거나 z가 루트인 경우 z를 블랙으로 바꿔주면 해결한다. 부모노드 p[z]를 블랙으로 바꿀때의 경우를 세분화하면 다음과 같다.

(p[z]가 p[p[z]]의 오른쪽 자식인지 왼쪽 자식인지에 따라 두가지 경우로 나누어지는데 이 두 경우는 서로 정확히 대칭이므로 p[z]가 p[p[z]]의 왼쪽 자식인 경우만 살펴보겠습니다.)

[Case 1의 예]

• Case 1 : z의 삼촌이 레드

z의 부모와 z의 삼촌 노드를 레드에서 블랙으로 바꾸고, z의 조상노드를 블랙에서 레드로 바꾼다. 그러면 레드블랙특성을 모두 만족하게 된다. 하지만 z의 조상 노도의 부모노드가 레드인 경우 이 문제는 반복되게 된다. 이 경우 z의 조상노드를 문제발생 노드로 하여 재귀적으로 다시 시작한다. 이 문제는 z의 부모가 블랙을 만날때 종료되며, 혹 재귀적으로 루트까지 올라가게되면 루트노드를 블랙으로 바꾸면 이 문제는 종료된다.

[Case 2의 예]

• Case 2 : z의 삼촌이 블랙

      - Case 2-1 : z가 p[z]의 오른쪽 자식

      - Case 2-2 : z가 p[z]의 왼쪽 자식

Case 2-1에서 p[z]를 중심으로 왼쪽으로 회전(Left rotation)시킨다. 여전히 레드블랙특성 3번을 위반한다. Case 2-2로 문제를 넘긴다.

Case 2-2에서 p[p[z]]를 중심으로 오른쪽 회전(Right rotation)시키고 p[z]와 p[p[z]]의 색상을 맞바꾼다.

Case 2를 만나면 Case 2-2의 수선을 마지막으로 상황이 종료된다. Case 1을 만나면 상황이 끝날 수도 있고 똑같은 상황이 다른 노드에서 다시 시작될 수도 있다. 이런 상황이 재귀적으로 반복되어 루트까지 올라갈 수 도 있다.

레드블랙 트리에서의 삽입 슈도코드는 아래와 같다.

레드블랙 트리에서의 삭제

레드블랙 트리에서 노드를 삭제할 때는 기본적으로 이진검색 트리에서의 삭제 방법을 따라 노드를 삭제한 후 색상을 맞추어 준다. 이진검색트리에서 임의의 노드 d를 삭제할 때 d의 자식이 둘이면 d의 직후원소(Successor)를 d로 옮긴 뒤 삭제한다. 노드 d의 색상을 건드리지 않은 채 키만 바뀌는 것은 레드블랙특성에 영향을 미치지 않는다. 문제가 되는 것은 직후원소를 삭제한 후 주변의 레드블랙특성의 위반 여부이다. 직후원소는 왼쪽 자식을 갖지 않는다는 점을 상기하자. 따라서 d의 직후원소 노드는 최대 1개의 자식만을 가질 수 있으므로 2개의 자식을 가진 노드의 삭제 작업은 자식이 없거나 1개만을 가진 노드의 삭제 작업으로 귀결된다. 따라서 레드블랙 트리에서의 삭제 작업은 자식이 없거나 1개만을 가진 노드의 삭제에 국한해 설명해도 무방하다.

삭제하려고 하는 노드 m의 (최대 1개) 자식을 x라고 하자. 만약 자식이 없으면 x는 NIL 노드가 된다. 어떤 경우든 앞으로 설명할 알고리즘에서 구별할 필요는 없다. 그냥 x로 표시하는 것으로 충분하다. m은 자신의 부모 노드의 왼쪽 자식일 수도 있고, 오른쪽 자식일 수도 있으나 완전히 대칭적이므로 둘 중 하나만 살펴봐도 완결성이 떨어지지 않는다.

우선 간단하게 해결될 수 있는 경우를 살펴보면

1. m이 레드인 경우는 그냥 삭제하면된다.

2. m이 블랙이고 자식이 레드인 경우는 삭제후 x의 노드를 블랙으로 바꾸면된다.

까다로운 경우는 m과 x가 블랙인 경우이다. 이 경우는 m을 삭제하면 블랙 노드의 개수가 1개 모자라서 레드블랙특성 4번에 위반된다. x의 주변상황에 따라 처리 방법이 달라지는데 경우별로 나누어 살펴보도록한다. 아래의 그림은 한 예를 나타낸다.

• Case 1 : p가 레드 (s는 항상 블랙이므로) <l, r의 색상>에 따라

     - Case 1-1 <블랙, 블랙>

- Case 1-2 <*, 레드>

- Case 1-3 <레드, 블랙>

• Case 2 : p가 블랙 <s, l, r의 색상>에 따라

- Case 2-1 <블랙, 블랙, 블랙>

- Case 2-2 <블랙, *, 레드>

- Case 2-3 <블렉, 레드, 블랙>

- Case 2-4 <레드, 블랙, 블랙>

Case 1-2, 2-2 와 Case 1-3, 2-3은 p의 색상이 처리 방법에 영향을 미치지 않으므로 통합하여 표시한다. 그림으로 나타내면 아래와 같다.

각 Case 별로 해결방법은 다음과 같다.

• Case 1-1

단순히 p와 s의 색상을 맞바꾼다.

• Case *-2

p를 중심으로 왼쪽으로 회전시키고, p와 s의 색상을 바꾼 다음 r의 색상을 레드에서 블랙으로 바꾼다.

• Case *-3

s를 중심으로 오른쪽으로 회전시키고 l과 s의 색상을 맞바꾼다. Case *-2로 이동한다.

• Case 2-1

단순히 s의 색상을 블랙에서 레드로 바꾼다. 이제 s를 지나가는 경로에서도 블랙 노드가 하나 모자라게 되어 p를 지나가는 경로 전체에서 블랙 노드가 하나 모자라게 된다. 이것은 원래 x에 대해서 발생했던 문제와 똑같은 문제가 p에 대해서 발생했음을 뜻한다. 재귀적으로 이 문제를 해결한다.

• Case 2-4

p를 중심으로 왼쪽으로 회전시키고 p와 s의 색상을 맞바꾼다. l과 r을 경유하는 경로와 관련해서는 문제가 없다. 다만 문제가 발생한 x의 부모 노드의 색상이 블랙에서 레드로 바뀌었다. 이것은 Case 1에 해당하므로 Case 1로 이동한다.

아래의 손가락 버튼을 눌려주시면 감사하겠습니다^^