레드-블랙 트리(RBT)는 이진 탐색 트리의 균형 잡힌 버전이다. 기본 연산(탐색, 이전 노드, 다음 노드, 최소값, 최대값, 삽입, 삭제)이 최악의 경우에도 로그 시간 복잡도를 보장한다.
이진 탐색 트리(BST)는 삽입 또는 삭제 연산 후에 균형이 깨질 수 있다는 단점이 있다. 최악의 경우, 노드들이 연결 리스트처럼 구성될 수 있다. 다음 예제를 보자:
a
\
b
\
c
\
d
이 문제를 방지하기 위해, 레드-블랙 트리는 삽입 또는 삭제 후에 재균형 작업을 수행한다. 또한 각 노드에 추가로 색상 속성을 저장하는데, 이는 빨간색 또는 검은색이 될 수 있다. 각 연산 후에 레드-블랙 트리는 다음 속성들을 만족한다:
속성 5는 노드 x의 블랙 높이(black-height)인 bh(x)를 정의한다. 블랙 높이는 해당 노드에서 리프 노드까지의 경로에 있는 검은색 노드의 수를 의미하며, 노드 자신은 포함하지 않는다.
[CLRS] 참조
노드:
nodeX.getPredecessor() 노드X의 중위 순회 이전 노드를 반환nodeX.getSuccessor() 노드X의 중위 순회 다음 노드를 반환nodeX.minimum() 노드X의 서브트리에서 최소 키 값을 가진 노드를 반환nodeX.maximum() 노드X의 서브트리에서 최대 키 값을 가진 노드를 반환트리:
search(input:) 주어진 키 값에 해당하는 노드를 반환minValue() 전체 트리에서 최소 키 값을 반환maxValue() 전체 트리에서 최대 키 값을 반환insert(key:) 키 값을 트리에 삽입delete(key:) 해당 키 값을 가진 노드를 트리에서 삭제verify() 주어진 트리가 레드-블랙 트리 속성을 만족하는지 검증count() 트리에 있는 노드의 총 개수를 반환isEmpty() 트리에 노드가 없는지 여부를 반환allElements() 트리의 모든 노드를 중위 순회로 배열로 반환회전, 삽입, 삭제 알고리즘은 [CLRS]에 제공된 의사 코드를 기반으로 구현됨
편의를 위해, 노드의 자식이나 부모(루트의 부모는 제외)에 대한 nil 포인터는 모두 nullLeaf로 교체된다. nullLeaf는 트리의 다른 노드와 마찬가지로 일반적인 노드 객체이지만, 색상은 검정색이고 자식, 부모, 키 값은 nil이다. 따라서 빈 트리는 루트에 정확히 하나의 nullLeaf로 구성된다.
왼쪽 회전(x 기준):
x의 오른쪽 자식인 y가 nullLeaf가 아니라고 가정한다. x에서 y로 이어지는 링크를 기준으로 회전하며, y를 서브트리의 새로운 루트로 만든다. x는 y의 왼쪽 자식이 되고, y의 왼쪽 자식은 x의 오른쪽 자식이 된다. 여기서 n은 노드, [n]은 서브트리를 나타낸다.
| |
x y
/ \ ~> / \
[A] y x [C]
/ \ / \
[B] [C] [A] [B]
오른쪽 회전(y 기준):
y의 왼쪽 자식인 x가 nullLeaf가 아니라고 가정한다. y에서 x로 이어지는 링크를 기준으로 회전하며, x를 서브트리의 새로운 루트로 만든다. y는 x의 오른쪽 자식이 되고, x의 오른쪽 자식은 y의 왼쪽 자식이 된다.
| |
x y
/ \ <~ / \
[A] y x [C]
/ \ / \
[B] [C] [A] [B]
회전은 포인터만 교환하는 로컬 연산이므로 시간 복잡도는 O(1)이다.
주어진 키를 가진 노드를 생성하고 색상을 빨간색으로 설정한다. 이후 표준 BST 삽입 작업을 수행해 트리에 추가한다. 이 과정 이후 트리는 더 이상 유효한 RBT가 아닐 수 있으므로, insertFixup 알고리즘을 호출해 레드-블랙 트리 속성을 복구한다.
레드-블랙 트리 속성을 위반하는 경우는 삽입된 노드 z와 그 부모 노드에서만 발생한다. 두 노드 모두 빨간색이거나, 부모 노드가 존재하지 않으면(루트는 반드시 검은색이어야 하므로 위반) 속성이 위반된다.
주요 케이스는 세 가지로 나뉜다:
케이스 1: z의 삼촌 노드가 빨간색이다. z.parent가 왼쪽 자식이면 z의 삼촌은 z.grandparent의 오른쪽 자식이다. 이 경우, 색상을 재조정하고 z를 z.grandparent로 이동한 후, 새로운 z에 대해 다시 확인한다. 다음 예제에서 빨간색 노드는 (x), 검은색 노드는 {x}로 표시하며, p는 부모, gp는 조부모, u는 삼촌을 나타낸다.
| |
{gp} (newZ)
/ \ ~> / \
(p) (u) {p} {u}
/ \ / \ / \ / \
(z) [C] [D] [E] (z) [C] [D] [E]
/ \ / \
[A] [B] [A] [B]
케이스 2a: z의 삼촌 노드가 검은색이고 z가 오른쪽 자식이다. 이 경우 z를 위로 이동시켜 z의 부모를 newZ로 만든 후, 이 newZ를 중심으로 회전한다. 이후 케이스 2b로 진행한다.
| |
{gp} {gp}
/ \ ~> / \
(p) {u} (z) {u}
/ \ / \ / \ / \
[A] (z) [D] [E] (newZ) [C] [D] [E]
/ \ / \
[B] [C] [A] [B]
케이스 2b: z의 삼촌 노드가 검은색이고 z가 왼쪽 자식이다. 이 경우 z.parent를 검은색으로, z.grandparent를 빨간색으로 재조정한다. 이후 z의 조부모를 중심으로 회전을 수행한다. 이 과정을 마치면 유효한 레드-블랙 트리가 완성된다.
| |
{gp} {p}
/ \ ~> / \
(p) {u} (z) (gp)
/ \ / \ / \ / \
(z) [C] [D] [E] [A] [B] [C] {u}
/ \ / \
[A] [B] [D] [E]
이 알고리즘의 실행 시간은 다음과 같다:
케이스 1은 최대 O(log n)번 수행되고, 나머지 케이스는 최대 한 번씩만 실행된다. 따라서 O(log n)번의 색상 재조정과 최대 2번의 회전이 발생한다. 전체 삽입 작업의 실행 시간은 O(log n)이다.
주어진 키를 가진 노드를 탐색한다. 노드가 존재하면 BST의 표준 삭제 작업을 수행한다. 삭제된 노드의 색이 빨간색이면 문제가 없지만, 검은색이면 레드-블랙 트리 속성이 위반될 수 있다. 이때 deleteFixup 프로시저를 호출한다.
위반 사항은 삭제된 노드 x의 부모와 자식이 모두 빨간색인 경우, 두 개의 인접한 빨간색 노드가 생길 수 있다. 또는 루트를 삭제한 경우 루트가 빨간색이 되거나, 블랙 높이 속성이 위반될 수 있다.
총 4가지 경우가 있다. 노드 x에 대해 deleteFixup을 호출한다.
케이스 1: x의 형제가 빨간색이다. 형제는 x의 부모의 다른 자식으로, x 자신이 아니다. 이 경우 x의 부모와 x의 형제를 다시 색칠한 후, x의 부모를 기준으로 좌회전을 수행한다. 아래 예제에서 s는 x의 형제, (x)는 빨간색, {x}는 검은색, |x|는 빨간색/검은색을 나타낸다.
| |
{p} {s}
/ \ ~> / \
{x} (s) (p) [D]
/ \ / \ / \
[A] [B] [C] [D] {x} [C]
/ \
[A] [B]
케이스 2: x의 형제가 검은색이고 두 개의 검은색 자식을 가진다. 이 경우 x의 형제를 빨간색으로 다시 색칠하고, x를 x의 부모로 올린 후 새로운 x에 대해 다시 확인한다.
| |
|p| |newX|
/ \ ~> / \
{x} {s} {x} (s)
/ \ / \ / \ / \
[A] [B] {l} {r} [A] [B] {l} {r}
/ \ / \ / \ / \
[C][D][E][F] [C][D][E][F]
케이스 3: x의 형제가 검은색이고 오른쪽에 하나의 검은색 자식을 가진다. 이 경우 형제를 빨간색으로, 형제의 왼쪽 자식을 검은색으로 다시 색칠한 후, 형제를 기준으로 우회전을 수행한다. 이후 케이스 4가 된다.
| |
|p| |p|
/ \ ~> / \
{x} {s} {x} {l}
/ \ / \ / \ / \
[A] [B] (l) {r} [A] [B] [C] (s)
/ \ / \ / \
[C][D][E][F] [D]{e}
/ \
[E] [F]
케이스 4: x의 형제가 검은색이고 오른쪽에 하나의 빨간색 자식을 가진다. 이 경우 형제를 x의 부모 색으로, x의 부모와 형제의 오른쪽 자식을 검은색으로 다시 색칠한 후, x의 부모를 기준으로 좌회전을 수행한다. 이 작업 후 유효한 레드-블랙 트리가 된다. ||x||는 x가 빨간색 또는 검은색 중 하나일 수 있음을 나타내며, 이는 |x| 색과 다를 수 있다. s는 p와 같은 색을 갖는다는 점이 중요하다.
| |
||p|| ||s||
/ \ ~> / \
{x} {s} {p} {r}
/ \ / \ / \ / \
[A] [B] |l| (r) {x} |l| [E] [F]
/ \ / \ / \ / \
[C][D][E][F] [A][B][C][D]
이 알고리즘의 실행 시간:
[CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein. "Introduction to Algorithms", 제3판. 2009
Swift 알고리즘 클럽을 위해 Ute Schiehlen이 작성. Jaap Wijnen과 Ashwin Raghuraman의 기여를 바탕으로 업데이트. Swift 4.2 검토는 Bruno Scheele가 수행.