Red Black Tree
레드 블랙 트리
* 검색 트리의 종류 (URL)
- 이진 검색 트리가 Build될 때 Balance(균형)이루지 못하게 되면 데이터의 저장과 검색에 \(\Theta(n)\)에 비례하는 시간이 소요된다.
- 이진 검색 트리의 Balance를 일정 수준으로 유지해가며 Build하도록 고안된 대표적인 자료구조가 Red Black Tree와 AVL Tree이다.
- 레드 블랙 트리는 어떤 노드를 삽입/삭제해도 레드 블랙 특성을 유지하게끔 트리를 자동으로 수선하는 자료구조이다.
Background (배경지식)
* Red Black Properties (레드 블랙 특성)
- 레드 블랙 트리는 모든 노드에 레드 혹은 블랙의 색상을 칠하는데,
아래의 "레드 블랙 특성"을 만족시켜 가면서 색상을 칠하게 된다.
특성 1. 루트노드는 블랙이다.
특성 2. 레드 블랙 트리에서의 리프노드는 NULL이며, 모든 리프노드는 블랙이다.
특성 3. 어떤 노드가 레드이면, 그 노드의 자식 노드는 반드시 블랙이다.
- 반대로, 블랙 노드는 레드 노드와 블랙 노드 둘 다 자식 노드로 가질 수 있다.
특성 4. 루트 노드에서 임의의 리프 노드(NULL)까지 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
* Leaf Node of Red Black Tree (레드 블랙 트리에서의 리프 노드)
- 레드 블랙 트리에서는, 우리가 아는 통상적인 "리프 노드"의 링크 필드가 가리키는 널 값을 리프 노드로 간주한다.
(즉, 리프 노드가 가리키는 널 값 = 레드 블랙 트리에서의 리프 노드)
- 이렇게 널 값을 리프 노드로 간주하게 되면 알고리즘에서 리프 노드가 개입될 때 특수 처리를 하지 않아도 된다.
- 모든 NULL 리프 마다 하나의 노드를 할당하기 보다는, 메모리 효율성과 경계조건을 용이하게 다루기 위해
모든 NULL 리프에 대한 포인터들이 하나의 NULL 값을 가리키게 설계하는 것이 바람직하다.
Mechanism (원리)
Search Operation (검색 연산)
- 레드 블랙 트리의 검색 연산은 이진 검색 트리에서의 검색 연산과 동일하게 수행된다.
Insertion Operation (삽입 연산)
* \(x\): 새로 삽입된 노드
* \(p\): 새로 삽입된 \(x\)의 부모 노드
* \(p^2\): \(p\)의 부모 노드 (즉, \(x\)의 조부모(?)노드)
* \(s\): \(p\)의 형제 노드
- 통상적인 이진 트리에서의 삽입 연산을 수행한다. 이 때, 이진트리의 특성상 새로 삽입된 노드는 트리의 하부에 위치하게 된다.
- 삽입한 새 노드 \(x\)의 색상을 레드로 칠한다.
- \(x\)는 항상 트리의 맨 아래쪽에 위치하게 되고, \(x\)의 아래에는 블랙 색상의 NULL 리프 두 개가 위치하게 된다.
- 즉, 새로 삽입된 \(x\)의 밑 부분은 레드 블랙 특성을 항상 만족시킨다. (\(x\)의 윗부분에 대한 검사만 수행하면 된다.)
- \(x\)의 부모 노드인 \(p\)가 블랙이면 그것으로 삽입은 완료된 것이기 때문에 \(p\)가 \(x\)와 같이 레드인 경우에 대해 처리해야 한다.
- \(p\)가 레드인 경우, \(p^2\)은 반드시 블랙이며,
\(p\)의 자식 노드 중 하나인 \(x\)의 형제 노드 또한 블랙이다.
※ 즉, \(p\)가 레드일 때, 색상이 정해지지 않은 노드는 \(p\)의 형제 노드인 \(s\)밖에 없다.
| Case 1. \(s\)가 레드인 경우 |
 |
| 1. \(p\)와 \(s\)를 블랙으로 칠한다. 2. \(p^2\)을 레드로 칠한다. 1) 이 때, \(p^2\)이 루트이면, \(p^2\)을 다시 블랙으로 바꾸고 끝낸다. 2) \(p^2\)이 루트가 아니면 \(p^2\)의 부모 색상을 확인한다. \(p^2\)의 부모 색상이 블랙이면 종료한다. \(p^2\)의 부모 색상이 레드이면 똑같은 문제가 다시 발생한 것이므로, 재귀적으로 다시 시작한다. |
| Case 2. \(s\)가 블랙인 경우 | |
| Case 2-(1). \(x\)가 \(p\)의 오른쪽 자식인 경우 | Case 2-(2). \(x\)가 \(p\)의 왼쪽 자식인 경우 |
 |
 |
| 1. \(p\)를 중심으로 왼쪽으로 회전시킨다. 2. 여전히 레드 블랙 특성을 위반하므로 Case II-(2)로 이동한다. |
1. \(p^2\)을 중심으로 오른쪽으로 회전하고 \(p\)와 \(p^2\)의 색상을 맞바꾼다. |
※ Case I이 발생되면, 한 번의 수선으로 상황이 종료될 수도 있고, 재귀적으로 반복될 수도 있다.
※ Case II가 발생되면, 반드시 Case II-(2)까지 수행되고 나서야 수선이 종료된다. (재귀적으로 반복될 염려는 없다.)
Deletion Operation (삭제 연산)
- 기본적으로, 레드 블랙 트리의 삭제 연산은 이진 검색 트리에서의 삭제 연산과 동일하게 수행된다.
(삭제 대상 노드 자리에 대체자를 복사하고, 기존의 대체자 노드는 삭제하는 방식을 의미한다.)
- 단, 삭제 대상 노드가 두 개의 자식 노드를 갖고 있는 경우,
자식 노드중에서 삭제 대상 노드를 대체할 노드를 찾고 Key값만 옮기는 방법으로 대체하게 되는데,
대체자로 인해 생긴 빈 공간이 레드 블랙 특성을 위배시키는지에 대한 여부가 삭제 연산에서의 주요 쟁점이다.
(본 블로그에서 대체자는 삭제 대상 노드의 오른쪽 자식 노드들 중 가장 최솟값인 노드를 의미한다.
즉, 대체자는 왼쪽 자식만 없거나, 자식이 아예 없는 노드이다.)
※ 따라서, 레드 블랙 트리에서의 삭제연산은 자식이 0개 혹은 1개 있는 노드의 삭제만을 커버한다.
※ 즉, 레드 블랙 트리에서 삭제 대상 노드는 실제로 삭제되지 않고 "대체"되는 것이며,
대체자가 된 노드가 원래 위치했던 자리를 삭제하는 것이다.
\(m\): 삭제 대상 노드(=대체자가 원래 있던 자리)
\(x\): \(m\)의 자식 노드 (\(m\)이 자식이 없다면, \(x\)는 NULL값을 갖는다.)
| Case 0. 비교적 처리가 간단한 경우 | |
| Case 0-(1). \(m\)이 레드인 경우 | Case 0-(1). \(m\)이 블랙이지만, \(x\)가 레드인 경우 |
 |
 |
| - \(m\)이 레드인 경우에는 삭제되어도 레드 블랙 특성을 깨지 않는다. - \(m\)이 레드이면, \(m\)의 부모는 블랙일 것이므로, 대체자가 레드이건, 블랙이건 상관 없기 때문이다. |
- \(m\)을 삭제한 후, \(x\)의 색상을 블랙으로 바꾼다. - 이 경우, \(m\)의 부모 노드의 색상은 아무래도 상관없다. |
| Case 1~2. 처리가 복잡한 경우 (\(m\)과 \(x\)가 블랙인 경우) |
|
 |
|
| - Case 1~2의 경우, \(m\)을 제거한 후 \(x\)의 주변 노드의 색상 상황에 따라 처리 방법을 제각기 달리한다. - \(x\)노드 옆의 "-1"은 루트에서 \(x\)를 지나는 경로에 블랙 노드의 수가 1개 부족함을 의미한다. * \(m\): 삭제 대상 노드(=대체자가 원래 있던 자리, 이미 삭제된 노드) * \(x\): \(m\)의 자식 노드 (\(m\)이 자식이 없다면, \(x\)는 NULL값을 갖는다.) * \(p\): \(x\)의 부모 노드 * \(s\): \(x\)의 형제 노드 * \(l\): \(s\)의 왼쪽 자식 노드 * \(r\): \(s\)의 오른쪽 자식 노드 ※ 색이 입혀지지 않은 노드는 레드/블랙 두 색상을 모두 취할 수 있음을 의미한다. |
| Case 1. <p = 레드, s = 블랙>인 경우 (레드 블랙 특성 3에 의해, \(s\)는 당연히 블랙일 수 밖에 없다.) |
|
| Case 1-(1). <p = 레드, s = 블랙, l = 블랙, r = 블랙> 인 경우 | Case 1-(2). <p = 레드, s = 블랙, l = 레드, r = 레드> 혹은 <p = 레드, s = 블랙, l = 블랙, r = 레드> 인 경우 |
 |
 |
| Case 1-(3). <p = 레드, s = 블랙, l = 레드, r = 블랙> 인 경우 | |
 |
|
| Case 2. <p = 블랙>인 경우 | |
| Case 2-(1). <p=블랙, s=블랙, l=블랙, r=블랙> 인 경우 | Case 2-(2). <p=블랙, s=블랙, l=레드, r=레드> 혹은 <p=블랙, s=블랙, l=블랙, r=레드> 인 경우 ※ Case 1-(2) 와 p를 제외하면 일치하는 경우이다. |
 |
 |
| Case 2-(3). <p=블랙, s=블랙, l=레드, r=블랙> 인 경우 ※ Case 1-(3) 와 p를 제외하면 일치하는 경우이다. |
Case 2-(4). <p=블랙, s=레드, l=블랙, r=블랙> 인 경우 |
 |
 |
| Case 2 ~ 3을 일반화한 버전 (아래 5가지 Case는 모두 레드 블랙 특성 4를 위반한 경우이다.) |
|
| Case 1-(1) | 수선 방법 |
 |
 |
| Case *-(2) | 수선 방법 |
 |
 - \(p\)와 \(s\)의 색상을 서로 맞바꾼다. - \(r\)을 레드에서 블랙으로 바꾼다. - \(s\)와 \(r\)에 달려있던 서브트리들도 그림과 같이 옮긴다. |
| Case *-(3) | 수선 방법 |
 |
 - \(l\)과 \(s\)의 색상을 맞바꾼다. - Case *-(2)로 이동하여 처리한다. |
| Case 2-(1) | 수선 방법 |
 |
 - 루트에서 \(s\)를 지나는 경로상에 블랙 노드가 하나 감소했다. - 이는 \(x\)에서 발생했던 블랙 노드의 부족 문제가 \(p\)에서 발생했음을 의미한다. - \(p\)를 문제가 발생한 노드로 두고 다시 재귀적으로 처리한다. |
| Case 2-(4) | 수선 방법 |
 |
 - \(p\)와 \(s\)의 색상을 서로 맞바꾼다. - \(l\)과 \(r\)을 경유하는 경로에는 문제가 없으나, \(x\)의 부모 노드의 색상이 블랙에서 레드로 바뀐 상황이 되었다. (Case 1에 해당) - 색상의 조합을 따져 Case 1-(1), 1-(2), 1-(3) 중 하나로 이동한다. |
Performance Evaluation (자료구조 성능 평가)
※ \(n\)개의 Key로 구성된 레드 블랙 트리가 가질 수 있는 최대 Depth(Level)는 \(O(log n)\)이다.
pf) 레드나 블랙 색상을 고려하지 않고, 가장 이상적으로 꽉 채워진 트리의 Depth는 \(\lfloor\log n\rfloor + 1\)이다.
그러므로, 레드 블랙 트리가 아무리 잘 만들어져도
루트에서 임의의 Leaf까지 이르는 경로에 존재하는 블랙 노드의 개수는 \(\lfloor\log n\rfloor + 1\)을 넘을 수 없다.
레드 블랙 특성 3에 따라, 레드 노드는 두 개가 연속해서 존재할 수 없다.
그러므로 루트에서 임의의 Leaf에 이르느 경로에서 레드 노드는 블랙 노드의 개수보다 많을 수 없다.
즉, 루트에서 임의의 Leaf에 이르는 경로의 길이는 \(2(\lfloor\log n\rfloor + 1)\)을 넘을 수 없다.
이는 점근적으로 \(O(\log n)\)에 비례한다.
※ 레드 블랙 트리에서의 검색 연산 = \(O(\log n)\)
※ 레드 블랙 트리에서의 삽입 연산 = \(O(\log n)\)
- Case 1은 다시 Case 1을 재귀적으로 호출할 가능성이 있으므로, (루트까지 올라갈 수 있다.)
최악의 경우 \(O(\log n)\)에 비례하는 시간내에 해결된다.
- Case 2의 경우, 상수 시간내에 해결된다.
※ 레드 블랙 트리에서의 삭제 연산 = \(O(\log n)\)
- Case 1-(1), Case *-(2), Case *-(3)의 경우, 상수 시간내에 해결된다.
- Case 2-(4)는 Case 1-(1), Case 1-(2), Case 1-(3) 중 하나로 이동하므로, 이 또한 상수 시간내에 해결된다.
- Case 2-(1)은 무보 노드에서 같은 상황이 다시 반복되어 재귀적으로 처리해야 할 가능성이 있으므로, (루트까지 올라갈 수 있다.)
최악의 경우 \(O(\log n)\)에 비례하는 시간내에 해결된다.
RBT Interface and Implementation (C++)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
