10장 탐색 트리(2)

10.4 (2,4) 트리

이 장에서 논의하는 (2,4) 트리를 포함한 일부 자료 구조는 다원 탐색 트리이다.

다원 탐색 트리(multi-way search tree): 즉 자식이 둘 이상인 내부 노드를 가진 트리

따라서 (2,4) 트리를 정의하기 전에 다원 탐색 트리에 대해 논의해 보겠다.

10.4.1 다원 탐색 트리

다원 트리는 각 내부 노드가 많은 자식을 가질 수 있도록 정의되어 있음을 기억하자. 

이 절에서는 다원 트리를 탐색 트리로 사용하는 방법에 대해 설명한다. 

탐색 트리에 저장하는 항목은 (k,x) 형태의 쌍이다. 

(k: 키, x: 키와 관련된 값)

그러나 업데이트 메소드에 대한 세부 사항은 

다원 트리에 대해 유지하려는 추가 속성에 따라 달라지므로 

다원 탐색 트리에서 업데이트를 수행하는 메소드에 대해서는 지금 논의하지 않는다. 

14.3.1절에서 설명한다.

다원 탐색 트리의 정의

d-노드: 자식 노드 d를 가질 경우의 정렬된 트리의 노드

다원 탐색 트리를 다음 성질을 갖는 정렬된 트리 T로 정의하며, 

이는 그림 10.19a에 표시되어 있다:

• T의 각 내부 노드는 적어도 2개의 자식을 갖는다. 

   즉, 각 내부 노드는 d > 2가 되도록 d-노드이다.

• 자식 v1,..., vd가 있는 T의 각 내부 d-노드 v는 

   d - 1개의 키-값 항목(k1,x1),..., (k(d - 1),x(d - 1))의 정렬된 집합을 저장한다. 

   여기서 k1≤... ≤ k(d - 1)이다.

• 관례적으로 k0 = - ∞와 kd = + ∞를 정의해 보자. 

   i = 1,...,d에 루트를 둔 v의 부분 트리의 한 노드에

   저장된 각 항목 (k, x)에 대하여 k(i-1) ≤ k≤ ki가 있다.

즉, v에 저장된 키들의 집합을 

특수 가공 키 k0 =- ∞ 및 kd =+ ∞를 포함하는 것으로 생각한다면, 

자식 노드 vi에 뿌리를 둔 T의 서브트리에 저장된 키 k는 

v에 저장된 두 키 사이에 "그 사이에" 있어야 한다. 

이러한 간단한 관점은 d-노드가 (d - 1)개의 정규 키를 저장하는 규칙을 발생시키며, 

또한 다원 탐색 트리에서 탐색하는 알고리즘의 기초를 형성한다.

위의 정의에 따르면, 이진 탐색 트리에 대한 우리의 관례(섹션 10.1)와 같이, 

다원 탐색의 외부 노드는 어떠한 엔트리도 저장하지 않고 "자리 표시자" 역할만 한다. 

따라서 이진 탐색 트리는

각 내부 노드가 하나의 엔트리를 저장하고 두 개의 자식을 갖는

다원 탐색 트리의 특별한 경우로 볼 수 있다. 

또한 외부 노드가 null일 수 있지만, 

여기서는 이들이 아무것도 저장하지 않는 실제 노드라고 단순화하여 가정한다.
그림 10.19: 

(a) 다원 탐색 트리 T; 

(b) 키 12에 대한 T의 탐색 경로(성공적이지 못한 탐색); 

(c) 키 24에 대한 T의 탐색 경로(성공적인 탐색).

 

그러나 다원 트리의 내부 노드에 

두 개의 자식이 있는지 또는 여러 개가 있는지는 

엔트리 수와 외부 노드 수 사이에 흥미로운 관계가 있다.

제안 10.7: n개의 엔트리를 가진 다원 탐색 트리에는 n+1개의 외부 노드가 있다.

다원 트리에서 탐색

다원 탐색 트리 T가 주어졌을 때, 

키 k로 엔트리를 탐색하는 것은 간단하다. 

T의 경로를 루트에서 시작하여 추적하여 그러한 탐색을 수행한다. 

(그림 10.19b와 c 참조)

탐색 중에 d-노드 v에 있을 때, 키 k를 v에 저장된 키 k1,..., k(d-1)과 비교한다. 

만약 어떤 i에 대하여 k=ki이면, 탐색은 성공적으로 완료된다. 

그렇지 않으면, v의 자식 vi에서 ki - 1 ≤ ki ≤ ki가 되도록 탐색을 계속한다. 

(일반적으로 k0 = - ∞와 kd = + ∞를 정의하는 것을 기억하자. 

외부 노드에 도달하면, T에 키 k로 엔트리가 없고, 

탐색이 성공적으로 종료되지 않음을 알 수 있다.

다원 탐색 트리를 표현하기 위한 자료 구조

7.1.3절에서는 일반 트리를 표현하기 위한 연결된 자료 구조에 대해 설명한다. 

이 표현은 또한 다원 탐색 트리에도 사용될 수 있다. 

사실, 다원 탐색 트리를 구현하기 위해 

일반 트리를 사용할 때 각 노드에 저장해야 하는 추가 정보는 

해당 노드에 연결된 엔트리(키 포함) 집합뿐이다. 

즉, v에 대한 엔트리를 저장하는 일부 컬렉션에 대한 참조로 v를 저장해야 한다.

이진 탐색 트리를 사용하여 정렬된 딕셔너리 D를 나타낼 때, 

단순히 각 내부 노드에 하나의 항목에 대한 참조를 저장한다. 

D를 나타내기 위해 다원 탐색 트리 T를 사용할 때, 

T의 각 내부 노드 v에 v와 관련된 정렬된 항목 집합에 대한 참조를 저장해야 한다. 

정렬된 딕셔너리를 나타내기 위해 정렬된 딕셔너리의 표현이 필요하므로, 

이 추론은 처음에는 순환 논법처럼 보일 수 있다. 

그러나 부트스트래핑 기법을 사용하면 순환 논법을 피할 수 있다.

부트스트래핑(bootstrapping) 기법: 문제에 대한 이전(덜 고급) 해결책을 사용하여 새로운(더 고급) 해결책을 생성한다.

이 경우 부트스트래핑은 우리가 이전에 구축한 딕셔너리 자료 구조를 사용하여 

각 내부 노드와 관련된 정렬된 집합을 나타내는 것으로 구성된다.

(예를 들어, 9.3.3절에 표시된 정렬된 배열에 기반한 탐색 테이블)

특히, 정렬된 딕셔너리를 이미 구현하는 방법이 있다고 가정하면 

트리 T를 가져와 T의 각 노드에 이러한 딕셔너리를 저장함으로써 

다원 탐색 트리를 구현할 수 있다.

2차(secondary) 자료 구조: 각 노드 v에 저장하는 딕셔너리

더 큰 기본(primary) 자료 구조를 지원하기 위해 그것을 사용한다.

 

D(v): T의 노드 v에 저장된 딕셔너리

D(v)에 저장하는 항목들을 통해 탐색 연산 중에 다음으로 이동할 자식 노드를 찾을 수 있다.

 

구체적으로 하위 v1,...,vd 및 항목(k1,x1),...,(k(d-1),x(d-1))이 있는 T의 각 노드 v에 대해

딕셔너리 D(v)에 다음 항목을 저장한다
(k1, (x1, v1)), (k2, (x2, v2)), ..., (kd − 1, (x(d − 1), v(d − 1))), (+ ∞, (φ, vd)).

즉, 딕셔너리 D(v)의 엔트리(ki, (xi,vi))는 키 ki와 값(xi,vi)을 갖는다. 
참고로 마지막 항목에 특수 키 + ∞가 저장된다.

위의 다원 탐색 트리 T의 구현을 통해 

키 k로 T의 엔트리를 탐색하면서 d-노드 v를 처리하는 것은 

k보다 크거나 같은 가장 작은 키로 

D(v)의 엔트리(ki,(xi,vi))를 찾는 탐색 연산을 수행함으로써 가능하다. 

우리는 두 가지 경우를 구분한다:

• k < ki이면 자식 vi를 처리하여 탐색을 계속한다

(특수 키 kd = + ∞가 반환되면 k는 노드 v에 저장된 모든 키보다 크며 자식 vd를 계속 처리한다).

• 그렇지 않으면(k = ki) 탐색이 성공적으로 종료된다.

n개의 엔트리를 저장하는 다원 탐색 트리 T의 위와 같은 실현을 위한 공간 요구사항을 고려해 보자. 

T의 노드의 2차 구조에 대해 정렬된 딕셔너리의 공통된 실현(제9장) 중 하나를 사용하여 

제안 10.7에 의해 T에 대한 전체 공간 요구사항은 O(n)이다.

다음으로 T의 탐색에 대한 응답에 소요되는 시간을 생각해 보자. 

탐색하는 동안 T의 d-노드 v에서 소요되는 시간은 

이차 자료 구조 D(v)를 어떻게 구현하느냐에 달려 있다. 

정렬된 배열(즉, 정렬된 탐색 테이블)로 D(v)를 구현하면 v를 O(logd) 시간으로 처리할 수 있다. 

정렬되지 않은 리스트를 사용하여 대신 D(v)를 구현하면 v를 처리하는 데 O(d) 시간이 걸린다. 

dmax: T의 모든 노드의 자식들의 최대 수, h: T의 높이

다원 탐색 트리에서의 탐색 시간은 

T의 노드(D(v)에서 이차 구조의 구체적인 구현에 따라

O(h dmax) 또는 O(h log dmax) 중 하나이다. 

dmax가 상수이면 이차 구조의 구현에 관계없이

탐색을 수행하는 실행 시간은 O(h)이다.

따라서 다원 탐색 트리의 주요 효율 목표는 높이를 가능한 작게 유지하는 것이다. 

즉, h는 딕셔너리에 저장된 총 항목 수인 n의 로그 함수가 되기를 원한다. 

균형 탐색 트리(balanced search tree): 로그 높이를 가진 탐색 트리

다음으로 4에서 dmax를 상한으로 하는 균형 탐색 트리에 대해 설명한다.

(2,4) 트리의 정의

(2,4) 트리:

각 노드에 저장된 2차 자료 구조를 작게 유지하는 동시에 

기본 다원 트리의 균형을 유지하는 다원 탐색 트리

2-4 트리 또는 2-3-4 트리로 불리기도 한다. 

 

이러한 자료 구조는 다음과 같은 두 가지 단순한 속성을 유지함으로써 목표를 달성한다(그림 10.20 참조):

크기 속성(size property): 모든 내부 노드에는 최대 4개의 자식이 있다. 
깊이 속성(depth property): 모든 외부 노드의 깊이가 동일하다.

그림 10.20: A(2,4) 트리.

 

다시 말하지만, 우리는 외부 노드가 비어 있다고 가정하고, 

단순화를 위해 외부 노드가 실제 노드라고 가정하는 탐색 및 업데이트 메소드를 설명하지만, 

후자의 요구 사항은 엄격하게 필요하지 않다.

(2,4) 트리에 대한 크기 속성  

1) 다원 탐색 트리의 노드가 단순해진다. 

2) 트리의 각 내부 노드에는 2, 3 또는 4개의 자식이 있음을 의미하므로 

    "2-3-4 트리"라는 대체 이름이 생성된다. 

3) 정렬되지 않은 리스트 또는 정렬된 배열을 사용하여 

     각 내부 노드 v에 저장된 딕셔너리 D(v)를 나타낼 수 있지만 

     모든 연산에 대해 O(1) 시간 성능을 달성할 수 있다는 것이다(dmax = 4 이기 때문에). 

 

(2,4) 트리에 대한 깊이 속성  

1) (2,4) 트리의 높이에 중요한 경계를 적용한다.

제안 10.8: n개의 항목을 저장하는 (2,4) 트리의 높이는 O(log n)이다.
 
정당화 : h를 n개의 원소를 저장하는 (2,4) 트리 T의 높이라고 하자. 

다음 주장들이 사실임을 보여줌으로써 명제를 정당화한다.

1 / 2 * log(n +1) ≤ h  (10.9)
그리고
h ≤ log(n+1)  (10.10)

1) 크기 속성에 의해, 깊이 1에 최대 4개의 노드, 깊이 2에 최대 4^2개의 노드 등을 가질 수 있다. 

따라서 T에 있는 외부 노드의 수는 최대 4^h이다. 

 

2) 깊이 속성과 (2,4) 트리의 정의에 의해, 

깊이 1에 적어도 2개의 노드, 깊이 2에 적어도 2^2개의 노드 등을 가져야 한다. 

따라서 T에 있는 외부 노드의 수는 적어도 2^h이다. 

 

또한 명제 10.7에 의해 T에 있는 외부 노드의 수는 n+1이다. 

따라서, 2^h ≤ n+1 과 n+1 ≤ 4^h 를 얻는다.

위 각 항의 밑 2에 로그를 취하면

h≤log(n+1)과 log(n+1) ≤2h을 얻는다.
이것은 우리의 주장을 정당화한다(10.9 및 10.10).

명제 10.8은 크기와 깊이 속성이

다원 트리의 균형을 유지하기에 충분하다는 것을 나타낸다(섹션 10.4.1). 

또한 이 명제는 (2,4) 트리에서 탐색을 수행하는 데 O(logn) 시간이 소요되며 

최대 자식 수 dmax가 상수(4)이므로 

노드에서 2차 구조를 구체적으로 구현하는 것이 중요한 설계 선택이 아님을 의미한다. 

예를 들어, 각 2차 구조에 대해 배열 리스트 탐색 테이블과 같은

간단한 정렬된 딕셔너리 구현을 사용할 수 있다.

10.4.2 (2,4) 트리에 대한 업데이트 연산

그러나 (2,4) 트리에서 삽입 및 제거 작업을 수행한 후 

크기 및 깊이 특성을 유지하려면 약간의 노력이 필요하다. 

다음으로 이러한 연산에 대해 설명한다.

삽입

키 k인 새로운 엔트리 (k,x)를 (2,4) 트리 T에 삽입하기 위해, 

먼저 k에 대한 탐색을 수행한다. 

T에 키 k인 엔트리가 없다고 가정하면, 이 탐색은 외부 노드 z에서 성공적으로 종료된다. 

v를 z의 부모라고 하자. 

노드 v에 새로운 엔트리를 삽입하고 

z의 왼쪽에 있는 v에 새로운 자식 w (외부 노드)를 추가한다. 

즉, 딕셔너리 D(v)에 엔트리 (k, x, w)를 추가한다.

기존의 외부 노드와 동일한 레벨로 새로운 외부 노드를 추가하기 때문에 

삽입 메소드는 깊이 속성을 보존한다.

그럼에도 불구하고 크기 속성을 위반할 수 있다. 

실제로 노드 v가 이전에 4-노드였다면 

삽입 후 5-노드가 될 수 있으므로

트리 T는 더 이상 (2,4) 트리가 아니다. 

 

노드 v에서의 오버플로우(overflow) :

자식 노드가 더 추가되어 더 이상 (2, 4) 트리가 아니게 되는 유형의 크기 속성 위반

 

(2,4) 트리의 속성을 복원하려면 이를 해결해야 한다. 

v1...,v5를 v의 자식이라고 하고,

k1,...,k4를 v에 저장된 키라고 한다. 

노드 v에서의 오버플로우를 해결하기 위해 

v에 대해 다음과 같이 분할(split) 연산을 수행한다(그림 10.21 참조):
 
• v를 두 개의 노드 v' 및 v''로 대체한다. 여기서 v'는
○ v'는 키 k1 및 k2를 저장하는 하위 v1, v2, v3가 있는 3-노드이다
○ v''는 키 k4를 저장하는 하위 v4, v5가 있는 2-노드이다.

• v가 T의 루트라면 새 루트 노드 u를 생성하고, 그렇지 않으면 v의 부모가 된다.

• 키 k3를 u에 삽입하고 v'와 v''를 u의 자식으로 만들어 

   v가 u의 자식 i이면 v'와 v''는 각각 u의 자식 i와 i+1이 되도록 한다.

그림 10.22의 (2,4) 트리에 삽입된 일련의 순서를 보여준다.

그림 10.21: 노드 분할: 

(a) 5-노드 v에서의 오버플로우; 

(b) v의 부모 u에 삽입된 v의 세 번째 키; 

(c) 노드 v가 3-노드 v' 및 2-노드 v''로 대체됨.

그림 10.22: (2,4) 트리에 삽입하는 순서: 
(a) 1개의 엔트리를 갖는 초기 트리; (b) 6의 삽입; (c) 12의 삽입; (d) 15의 삽입, 오버플로우를 야기한다.;

(e) 분할, 새로운 루트 노드의 생성을 야기한다.; (f) 분할 후; 

(g) 3의 삽입; (h) 5의 삽입, 오버플로우를 야기한다.; 

(i) 분할; (j) 분할 후;

(k)10의 삽입; (l) 8의 삽입.

(2,4) 트리의 삽입 해석

분할 연산은 트리의 일정한 노드 수와 

그러한 노드에 저장된 O(1)개의 엔트리에 영향을 미치므로 

O(1) 시간 내에 실행되도록 구현할 수 있다.

노드 v에 대한 분할 연산의 결과로

v의 부모 u에서 새로운 오버플로우가 발생할 수 있다. 

이러한 오버플로우가 발생하면 노드 u에서 차례로 분할을 발생시킨다. (그림 10.23 참조) 

분할 작업은 오버플로우를 제거하거나 현재 노드의 부모로 전파한다. 

따라서 분할 작업의 수는 트리의 높이로 제한되며, 이는 명제 10.8에 의해 O(logn)이다. 

따라서 (2,4) 트리에서 삽입을 수행하는 총 시간은 O(logn)이 된다.

그림 10.23: (2,4) 트리에서 계단식 분할을 일으키는 삽입: 

(a) 삽입 전; (b) 오버플로우를 일으키는 17의 삽입; 

(c) 분할 (d) 분할 후에 새로운 오버플로우가 발생한다; 

(e) 새로운 루트 노드가 생성하는 또다른 분할; (f) 최종 트리.

제거

이제 (2,4) 트리 T에서 키 k를 가진 엔트리의 제거를 생각해 보자. 

T에서 키 k를 가진 엔트리를 탐색하는 것으로 그러한 연산을 시작한다. 

(2,4) 트리에서 그러한 엔트리를 제거하는 것은 

항상 제거할 엔트리가 자식이 외부 노드인 노드 v에 저장되는 경우로 축소될 수 있다. 

 

예를 들어, 제거하고자 하는 키 k를 가진 엔트리가 

내부 노드 자식만 있는 노드 z의 i번째 엔트리(ki,xi)에 저장된다고 가정하자.

이 경우 엔트리(ki,xi)를

다음과 같이 외부 노드 자식이 있는 노드 v에 저장된 적절한

엔트리와 교환한다(그림 10.24d 참조):

1. 우리는 z의 i번째 자식에 뿌리를 둔 부분 트리에서 가장 오른쪽 내부 노드 v를 찾으며, 

노드 v의 자식은 모두 외부 노드임에 주목한다.
2. z에 있는 항목(ki, xi)을 v의 마지막 항목으로 바꾼다.

제거할 항목이 외부 노드 자식만 있는 노드 v에 저장되어 있는지 확인한 후

(v에 이미 있거나 v로 스왑했기 때문에) 

v에서 항목을 제거하고 v의 i번째 외부 노드를 제거하기만 하면 된다.

위에서 설명한 대로 노드 v에서 항목(그리고 자식)을 제거하면 

항상 외부 노드 자식만 있는 노드 v에서 외부 노드 자식을 제거하기 때문에 

깊이 속성이 유지된다. 

그러나 이러한 외부 노드를 제거할 때 v에서 크기 속성을 위반할 수 있다. 

실제로 v가 이전에 2-노드였다면 

제거 후에 항목이 없는 1-노드가 되며(그림 10.24d 및 e), 

이는 (2,4) 트리에서는 허용되지 않다. 

 

노드 v에서의 언더플로우(underflow) :

노드 v에서 항목과 자식을 제거할 때 자식의 수가 2보다 작아지게 되어

크기 속성을 위반하는 것

 

언더플로우를 해결하기 위해 v의 직계 형제의 자식의 노드의 수를 확인해본다.

1 ) v의 직계 형제 w가 3-노드이나 4-노드인 경우 

전송(transfer) 연산을 수행한다(그림 10.24b 및 c 참조). 

전송 연산: w의 자식을 v로, w의 키를 v와 w의 부모 u로, u의 키를 v로 이동하는 연산

 

2) v에 형제가 한 명만 있거나 v의 직계 형제가 모두 2-노드인 경우 

융합(fusion) 연산을 수행하여 v를 형제와 병합하여 

새 노드 v'를 생성하고 키를 v의 상위 u에서 v'로 이동한다

(그림 10.25e 및 f 참조)

노드 v에서 융합 연산이 발생하면 v의 부모 u에서 새로운 언더플로우가 발생할 수 있으며, 

이는 다시 u에서 전송이나 융합을 유발한다. (그림 10.25 참조) 

따라서 융합 연산의 수는 트리의 높이로 제한되며, 이는 명제 10.8에 의해 O(logn)이다. 

언더플로우가 루트까지 전파되면 루트는 단순히 삭제된다. (그림 10.25c 및 d 참조) 

그림 10.24 및 10.25에서 (2,4) 트리에서 제거되는 순서를 보여준다.

그림 10.24: (2,4) 트리에서 제거 순서: 

(a) 언더플로우를 유발하는 4의 제거; (b) 전송 연산; 

(c) 전송 연산 후; (d) 12의 제거;

(e) 융합 연산 후; (f) 13의 제거; 

(g) 13의 제거; (h) 제거 후.

그림 10.25: (2,4) 트리에서 융합의 전파 순서: 

(a) 14의 제거, 언더플로우를 유발한다; (b) 융합, 또다른 언더플로우를 유발한다; 

(c) 2번째 융합 연산, 루트를 제거한다;  (d) 최종 트리.

(2,4) 트리의 성능

표 10.3은 (2,4) 트리로 구현된 딕셔너리의 주요 연산의 실행 시간을 요약한 것이다. 

시간 복잡도 분석은 다음을 기반으로 한다:
• n개의 항목을 저장하는 (2,4) 트리의 높이는 명제 10.8에 의해 O(logn)이다.

• 분할, 전송 또는 융합 연산은 O(1) 시간이 걸린다.
• 항목의 탐색, 삽입 또는 제거는 O(logn) 노드를 방문한다.

표 10.3: (2,4) 트리로 구현된 n-엔트리 딕셔너리의 성능. 

s: findAll에 의해 반환되는 컬렉션의 크기

공간 사용량: O(n)

 

연산	시간
size, isEmpty	O(1)
find, insert, remove	O(log n)
findAll	O(log n + s)

따라서 (2,4) 트리는 빠른 딕셔너리 탐색 및 업데이트 연산을 제공한다. 

(2,4) 트리는 또한 다음에 논의할 자료 구조와 흥미로운 관계를 가지고 있다.

10.5 레드-블랙 트리

AVL 트리와 (2,4) 트리는 여러 가지 좋은 특성을 가지고 있지만, 

딕셔너리의 응용으로는 적합하지 않은 것들이 있다. 

예를 들어, AVL 트리는 제거 후 많은 재구조화 연산(회전)을 수행해야 할 수 있고, 

(2,4) 트리는 삽입 또는 제거 후 많은 융합 또는 분할 연산을 수행해야 할 수 있다. 

그러나 이 섹션에서 설명하는 레드-블랙 트리(Red-Black Tree)는 이러한 단점이 없지만, 

균형을 유지하기 위해 업데이트 후 오직 O(1) 구조 변경만 수행해야 한다.

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

다음 속성을 만족시키는 방법으로 레드과 블랙으로 표시된 노드가 있는 이진 탐색 트리(섹션 10.1 참조)

루트(root) 속성: 루트가 블랙이다.
외부(external) 속성: 모든 외부 노드가 블랙이다.
내부(internal) 속성: 레드 노드의 자식이 블랙이다.
깊이(depth) 속성: 모든 외부 노드는 동일한 블랙 깊이를 가진다.

(블랙 깊이(black depth): 블랙 조상들의 수에서 1을 뺀 숫자 (노드가 자신의 조상임을 상기시킨다.))

레드-블랙 트리의 예는 그림 10.26에 나와 있다.

그림 10.26: 그림 10.20의 (2,4) 트리와 관련된 레드-블랙 트리이다. 

이 레드-블랙 트리의 각 외부 노드에는 4개의 블랙 조상(자신을 포함)이 있으므로 블랙깊이가 3이다. 

우리는 레드 대신 파란색을 사용한다. 

또한 트리의 가장자리에 자식 노드와 같은 색을 부여하는 규칙을 사용한다.

이전 유형의 탐색 트리에 대해서는 

항목이 레드-블랙 트리의 내부 노드에 저장되고 외부 노드는 빈 자리표시자라고 가정한다. 

또한 외부 노드가 실제 노드라고 가정하지만 

약간 더 복잡한 방법을 희생하더라도 외부 노드가 null일 수 있다는 점에 주목한다.

그림 10.27과 같이 레드-블랙 트리와 (2,4) 트리 사이의 흥미로운 대응에 주목함으로써 

레드-블랙 트리의 정의를 보다 직관적으로 만들 수 있다. 

즉, 레드-블랙 트리가 주어지면

모든 레드 노드 v를 부모로 병합하고 v의 항목을 부모에 저장함으로써

대응하는 (2,4) 트리를 구성할 수 있다.

 

반대로, 각 노드를 블랙으로 색칠하고 각 내부 노드 v에 대해 다음과 같은 변환을 수행함으로써 

임의의 (2,4) 트리를 해당 레드-블랙 트리로 변환할 수 있다:
• v가 2-노드인 경우 v의 (블랙) 자식을 그대로 유지한다.
• v가 3-노드인 경우 새 레드 노드 w를 만들고 

   v의 첫 번째 두 자식(검은색)을 w로 주고 

   w와 v의 세 번째 자식을 v의 두 자식으로 만든다.
• v가 4-노드인 경우 새 레드 노드 w와 z를 두 개 생성하고 

   v의 처음 두 개(블랙) 자식을 w에 주고 

   v의 마지막 두 개(블랙) 자식을 z에 주고 

   w와 z를 v의 두 개 자식으로 만든다.

그림 10.27: (2,4) 트리와 레드-블랙 트리의 대응: 

(a) 2-노드; (b) 3-노드; (c) 4-노드.

 

(2,4) 트리와 레드-블랙 트리의 대응은 

레드-블랙 트리에서 업데이트를 수행하는 방법에 대한 논의에서 사용할 중요한 직관을 제공한다. 

사실 레드-블랙 트리의 업데이트 알고리즘은 이런 직관 없이는 불가사의할 정도로 복잡하다.

명제 10.9: n개의 원소를 저장하는 레드-블랙 트리의 높이는 O(logn)이다. 

정당화:

T: n개의 원소를 저장하는 레드-블랙 트리

h: T의 높이

다음 사실을 설정함으로써 이 명제를 정당화한다.
log(n + 1) ≤ h ≤ 2 log(n + 1)

d: T의 모든 외부 노드의 공통 블랙 깊이

T': T와 관련된 (2,4) 트리

h': T'의 높이

레드-블랙 트리와 (2,4) 트리의 대응 때문에, h = d임을 알고 있다. 

따라서, 명제 10.8에 의해, d = h ≤ log(n + 1). 

내부 노드 속성에 의해, h ≤ 2d. 

따라서, h ≤ 2log(n + 1)를 얻는다. 

다른 부등식인 log(n + 1) ≤ h는 

명제 7.10과 T이 n개의 내부 노드를 갖는다는 사실로부터 이어진다.

각 노드에 딕셔너리 항목과 색상 표시기를 저장하는

이진 트리에 대한 연결 구조로 레드-블랙 트리를 구현한다고 가정한다(섹션 7.3.4). 

n개의 키를 저장하기 위한 공간 요구 사항: O(n)

레드-블랙 트리 T에서 탐색하는 알고리즘은 표준 이진 탐색 트리의 알고리즘과 동일하다(섹션 10.1). 

적흑 트리에서 탐색하는 데 걸리는 시간: O(logn)

10.5.1 업데이트 연산

레드-블랙 트리에서 업데이트 연산을 수행하는 것은 

색상 속성을 추가로 복원해야 한다는 점을 제외하고는 이진 탐색 트리와 유사하다.

삽입

이제 T와 연관된 (2,4) 트리 T' 사이의 대응과 T'에 대한 삽입 알고리즘을 염두에 두고 

키 k를 가진 엔트리를 레드-블랙 트리 T에 삽입하는 것을 고려해 보겠다. 

이 알고리즘은 처음에 이진 탐색 트리와 같이 진행된다(10.1.2절). 

즉, T의 외부 노드에 도달할 때까지 T에서 k를 찾고, 

이 노드를 내부 노드 z로 대체하여 (k,x)를 저장하고 두 개의 외부 노드 자식을 갖는다. 

z가 T의 루트라면, z를 블랙으로 색칠하고, 그렇지 않으면 z를 레드으로 색칠한다. 

또한 z의 자식을 블랙으로 색칠한다. 

이 동작은 외부 자식이 있는 (2,4) 트리 T'의 노드에 (k,x)를 삽입하는 것에 해당한다.

 

또한 이 동작은 T의 루트, 외부 및 깊이 속성을 보존하지만 내부 속성을 위반할 수도 있다. 

실제로 z가 T의 루트가 아니고 z의 부모 v가 레드이면 부모와 자식(즉, v와 z)이 둘 다 레드이다. 

루트 속성에 의해 v는 T의 근이 될 수 없으며 내부 속성에 의해 v의 부모 u는 블랙이어야 한다. 

z와 그 부모는 레드이지만 z의 조부모 u는 블랙이 된다.

 

노드 z의 이중 레드(double red) :

노드를 삽입할 때 부모 자식 노드가 모두 레드가 되어버려 내부 속성을 위반하는 것

이중 레드를 치료하기 위해 두 가지 경우를 고려한다.

사례 1: v의 형제 w는 블랙이다. (그림 10.28 참조) 

이 경우 이중 레드는 (2,4) 트리 T1의 해당 4개 노드에 대한 잘못된 대체를 생성한 사실을 나타낸다. 

잘못된 대체에는 다른 레드 노드(z)의 부모인 하나의 레드 노드(v)가 있는 반면, 

두 개의 레드 노드는 형제로 만들기를 원한다. 

이 문제를 해결하기 위해 T의 트라이노드 재구조화를 수행한다. 

트라이노드 재구조화는 다음 단계로 구성된 restructure(z)에 의해 수행된다

(그림 10.28 참조; 이 연산은 섹션 10.2에서도 설명):

• 노드 z, 해당 상위 v 및 조부모 u를 취하고, 

   a, b, c를 왼쪽에서 오른쪽 순서로 일시적으로 재라벨하여 

   a, b, c가 순서대로 트리 중위 순회에 의해 방문되도록 한다.

• 조부모 u를 b라는 이름의 노드로 대체하고, 

   노드 a와 c를 b의 자식으로 만들어 순서 관계를 변경하지 않는다.

restructure(z) 연산을 수행한 후 b를 블랙으로 하고 a와 c를 레드로 한다. 

따라서 restructure 연산을 수행하면 이중 레드 문제를 제거할 수 있다.
그림 10.28: 이중 레드를 해결하기 위해 레드-블랙 트리 재구조화: 

(a) 재구조화 전에 u, v, z에 대한 네 가지 구성; (b) 재구조화 후.

사례 2: v의 형제 w는 레드이다. (그림 10.29 참조) //여기부터

이 경우 이중 레드는 해당하는 (2,4) 트리 T의 오버플로우를 나타낸다. 

문제를 해결하기 위해 분할 연산과 동등한 작업을 수행한다. 

즉, 다시 칠하기(recoloring)를 한다.

 

다시 칠하기(recoloring):

v와 w를 블랙으로 색칠하고 그들의 부모를 레드로 색칠한다

(u가 루트가 아닌 경우 블랙으로 색칠한다). 

 

이러한 다시 칠한 후에, u가 부모 레드를 가질 수 있기 때문에 

트리 T보다 위에 있지만 이중 레드 문제가 다시 나타날 수 있다. 

만약 이중 레드 문제가 u에서 다시 나타난다면, 

우리는 u에서 두 경우를 반복하여 고려한다. 

따라서, 회상은 노드 z에서 이중 레드 문제를 제거하거나 z의 조부모 u로 전파한다. 

최종적으로 이중 레드 문제를 해결할 때까지 

(최종 회상 또는 트리노드 재구조화)

T를 수행하여 회상을 계속한다. 

따라서, 삽입으로 인한 다시 칠하기의 수는 트리 T의 높이의 절반 이하, 

즉 명제 10.9에 의한 log(n + 1) 이하이다.

 

그림 10.29: 이중 레드 문제를 해결하기 위한 다시 칠하기: 

(a) 다시 칠하기 전 및 분할 전 관련 (2,4) 트리의 해당 5-노드; 

(b) 다시 칠하기 후 (그리고 분할 후 관련 (2,4) 트리의 해당 노드).

그림 10.30과 10.31은 레드-블랙 트리에서 삽입 연산의 순서를 보여준다.

그림 10.30: 레드-블랙 트리의 삽입 순서: 

(a) 초기 트리; (b) 7의 삽입; (c) 12의 삽입, 이중 레드를 유발한다; (d) 재구조화 후

(e) 15의 삽입, 이중레드를 유발한다; (f) 다시 칠한 후 (루트는 블랙으로 남는다) (g) 3의 삽입; (h) 5의 삽입; 

(i) 14의 삽입, 이중레드를 유발한다; (j) 재구조화 후

(k) 18의 삽입, 이중레드를 유발한다; (l) 다시 칠한 후  (그림 10.31에서 계속)

그림 10.31: 레드-블랙 트리의 삽입 순서: 

(m) 16의 삽입, 이중레드를 유발한다 (n) 재구조화 후, 

(o)  17의 삽입, 이중레드를 유발한다 (p) 다시 칠한 후, 재구조화로 처리해야 할 이중 레드가 다시 있다. 

(q) 재구조화 후. (그림 10.30부터 계속)

삽입 사례는 레드-블랙 트리에 대한 흥미로운 특성을 암시한다. 

즉, Case 1 행동은 단일 트라이노드 구조화로 이중 적색 문제를 제거하고 

Case 2 행동은 재구조화 연산을 수행하지 않으므로 

레드-블랙 트리 삽입에서 최대 한 가지 재구조화가 필요하다. 

위의 분석과 재구조화 또는 다시 칠하기에 O(1) 시간이 걸린다는 사실에 의해 다음과 같은 것이 있다:

제안 10.10: n개의 엔트리를 저장하는 레드-블랙 트리에 키-값 엔트리의 삽입은 

O(logn) 시간 내에 수행될 수 있으며 

O(logn) 다시 칠하기와 하나의 트라이노드 재구조화(restructure 연산)가 필요하다.

제거

이제 레드-블랙 트리 T에서 키 k를 가진 엔트리를 제거하도록 요청받았다고 가정하자. 

이러한 엔트리를 제거하는 것은 처음에는 이진 탐색 트리와 같이 진행된다(제10.1.2절). 

먼저, 이러한 엔트리를 저장하고 있는 노드 u를 탐색한다. 

만약 노드 u가 외부 자식을 갖지 않는다면, 

T의 순서대로 u를 따르는 내부 노드 v를 찾고, 

v에서 엔트리를 u로 이동시키고, v에서 제거를 수행한다. 

따라서, 외부 자식 w를 가진 노드 v에 키 k를 저장하고 있는 엔트리의 제거만 고려할 수 있다. 

또한, 삽입에서와 같이, 레드-블랙 트리 T와 연관된 (2,4) 트리 T'

(그리고 T'에 대한 제거 알고리즘) 사이의 대응 관계를 염두에 두자.

외부 자식 w이 있는 T의 노드 v에서 키 k를 가진 엔트리를 제거하기 위해 다음과 같이 진행한다. 

(r: w의 형제,  x: v의 부모)

노드 v와 w를 제거하고 r을 x의 자식으로 만든다. 

v가 레드(따라서 블랙)이거나 r이 레드(따라서 v가 블랙)이면 r을 블랙으로 색칠하고 완료된다. 

대신에 r이 블랙이고 v가 블랙이면 

깊이 성질을 보존하기 위해 r에게 가상의 이중 블랙(double black)을 부여한다. 

우리는 이중 블랙 문제라고 불리는 색 위반을 가지고 있다.

 

T에서 이중 블랙은 대응하는 (2,4) 트리 T의 언더플로우를 나타낸다. 

x는 이중 블랙 노드 r의 부모임을 기억하자. 

r에서 이중 블랙 문제를 해결하기 위해 세 가지 경우를 고려한다.

사례 1: r의 형제 y는 블랙이고 레드 자식 z를 가지고 있다. (그림 10.32 참조) 

이 경우를 해결하는 것은 (2,4) 트리 T'의 전송 연산에 해당한다. 

연산 restructure(z)를 통해 트라이노드 재구조화를 수행한다. 

연산 restructure(z)는 노드 z와 그 부모 y, 그리고 조부모 x를 

일시적으로 오른쪽으로 a, b, c로 라벨링하고 

x를 b로 표시한 노드로 대체하여 다른 두 개의 부모를 만든다. 

(10.2절의 재구조화 설명도 참조) 

a와 c는 블랙으로, b는 x의 이전 색상으로, r은 블랙으로 표시한다. 

이 트라이노드 재구조화는 이중 블랙 문제를 제거한다. 

따라서 이 경우에는 기껏해야 하나의 재구조화가 제거 연산에서 수행된다.

그림 10.32: 이중 블랙 문제를 해결하기 위한 레드-블랙 트리의 재구조화: 

(a)와 (b) 재구조화 전의 구성, 

여기서 r은 오른쪽 자식이고 전송 전의 (2,4) 트리의 연관 노드

(r은 왼쪽 자식인 다른 두 대칭 구성이 가능함), 

(c) 재구조화 후의 구성, 그리고 전송 후의 (2,4) 트리의 연관 노드. 

(a)와 (b) 부분의 노드 x와 (c) 부분의 노드 b에 대한 회색은 

이 노드가 레드이나 블랙으로 변할 수 있다는 사실을 나타낸다.

사례 2: r의 형제 y는 블랙이고 y의 두 자식은 모두 블랙이다. (그림 10.33 및 10.34 참조)

이 경우를 해결하는 것은 해당 (2,4) 트리 T'의 융합 연산에 해당한다. 

우리는 다시 칠하기 연산을 한다; 

r을 블랙으로 색칠하고, 

y를 레드으로 색칠하고, 

x가 레드이면 블랙으로 색칠한다 (그림 10.33); 

그렇지 않으면 x를 이중 블랙으로 색칠한다 (그림 10.34 참조). 

따라서 이 다시 칠하기 후에 r의 부모 x에서 이중 블랙 문제가 다시 나타날 수 있다 (그림 10.34 참조). 

즉, 이 다시 칠하기는 이중 블랙 문제를 제거하거나 현재 노드의 부모로 전파한다. 

그런 다음 부모에서 이 세 가지 경우에 대한 고려를 반복한다. 

따라서 Case 1은 트라이노드 재구조화 연산을 수행하고 중지하므로

(그리고 나중에 보게 될 Case 3도 유사), 

제거로 인한 다시 칠하기의 수는 log(n+1) 이하이다.

그림 10.33: 이중 블랙 문제를 해결하는 레드-블랙 트리의 다시 칠하기: 

(a) 융합 전 관련 (2,4) 트리의 다시 칠하기 및 대응 노드 이전(다른 유사한 구성이 가능함);

(b) 융합 후 관련 (2,4) 트리의 다시 칠하기 및 대응 노드 이후.

 

그림 10.34: 이중 블랙 문제를 전파하는 레드-블랙 트리의 다시 칠하기: 

(a) 융합 전 관련 (2,4) 트리의 다시 칠하기 및 대응 노드 이전의 구성(다른 유사한 구성도 가능); 

(b) 융합 후 관련 (2,4) 트리의 다시 칠하기 및 대응 노드 이후의 구성.

Case 3: r의 형제 y는 레드이다. (그림 10.35 참조) 

이 경우 다음과 같이 조정(adjustment) 연산을 수행한다. 

만약 y가 x의 오른쪽 자식이면 z가 y의 오른쪽 자식이 되고, 

그렇지 않으면 z가 y의 왼쪽 자식이 된다. 

트라이노드 재구조화 연산 restructure(z)를 실행하여 y를 x의 부모로 만든다. 

색상 y는 블랙이고 x는 레드이다. 

조정은 (2,4) 트리 T'에서 3-노드의 다른 표현을 선택하는 것에 해당한다. 

조정 작업 후에 r의 형제는 블랙이고, 

x와 y의 다른 의미로 Case 1 또는 Case 2 중 하나가 적용된다. 

Case 2가 적용되면 이중 블랙 문제가 다시 발생할 수 없다. 

따라서 Case 3을 완료하기 위해 

위의 Case 1 또는 Case 2 중 하나를 한 번 더 적용하고 작업을 완료한다. 

따라서 최대 한 번의 조정은 제거 연산에서 수행된다.

그림 10.35: 이중 블랙 문제가 있는 경우 레드-블랙 트리의 조정: 

(a) 조정 전 구성 및 관련 (2,4) 트리의 해당 노드(대칭적 구성 가능); 

(b) 관련 (2,4) 트리의 동일한 해당 노드로 조정 후 구성.

위의 알고리즘 설명을 통해 제거 후 필요한 트리 업데이트는 

트리 T에서 상향 행진을 포함하는 동시에 

노드당 최대 일정한 양의 작업(재구조화, 다시 칠하기, 조정)을 수행한다는 것을 알 수 있다. 

따라서 이 상향 행진 동안 T의 노드에서 변경하는 사항은 O(1) 시간이 소요되므로 

(일정한 양의 노드를 영향을 끼치기 때문에)

다음과 같은 사항이 있다:

제안 10.11: 

n개의 엔트리가 있는 레드-블랙 트리에서 엔트리를 제거하는 알고리즘은 

O(logn) 시간이 걸리고 O(logn) 다시 칠하기를 수행하며, 

기껏해야 한 번의 조정과 한 번의 추가 트라이노드 재구조화를 수행한다. 

따라서 기껏해야 두 번의 재구조화 연산을 수행한다.

그림 10.36과 10.37에서 레드-블랙 트리에 대한 일련의 제거 연산을 보여준다. 

그림 10.36c와 d에서 사례 1의 재구조화를 보여준다. 

그림 10.36과 10.37에서 사례 2의 재구조화를 보여준다. 

마지막으로 그림 10.37i와 j에서 사례 3의 조정 예를 보여준다.

그림 10.36: 레드-블랙 트리에서 제거 순서: 

(a) 초기 트리; (b) 3의 제거; 

(c) 12의 제거, 이중 블랙 발생(재구조화로 처리); (d) 재구조화 후.

(그림 10.37에서 계속)

그림 10.37: 레드-블랙 트리에서 제거 순서(계속): 

(e) 17의 제거, (f) 18의 제거, 이중 블랙 발생(다시 칠하기로 처리), 

(g) 다시 칠하기 후, (h) 15의 제거,

(i) 16의 제거, 이중 블랙 발생(조정으로 처리), 

(j) 조정 후 이중 블랙은 다시 칠하기로 처리해야 한다,

(k) 다시 칠하기 후. (그림 10.36에서 계속)

 

레드-블랙 트리의 성능에 관한 연구

표 10.4는 레드-블랙 트리로 실현된 딕셔너리의 주요 연산의 실행 시간을 요약한 것이다. 

우리는 그림 10.38에서 이러한 경계들에 대한 정당성을 설명한다.

표 10.4: 레드-블랙 트리로 구현된 n-엔트리 딕셔너리의 성능. 

s: findAll에 의해 반환되는 컬렉션의 크기

공간 사용량: O(n)

연산	시간
size, isEmpty	O(1)
find, insert, remove	O(log n)
findAll	O(log n + s)

 

그림 10.38: 레드-블랙 트리에서 탐색 및 업데이트의 실행 시간을 보여준다. 

시간 성능: 레벨당 O(1)

하강 단계(down phase): 탐색이 포함된다.

상승 단계(up phase): 지역적 트라이노드 재구조화(회전)를 수행한다.

따라서 레드-블랙 트리는 딕셔너리에서

탐색과 업데이트 모두에 대해 로그 최악의 경우 실행 시간을 달성한다. 

레드-블랙 트리 자료 구조는 해당하는 (2,4) 트리보다 약간 더 복잡하다. 

그럼에도 불구하고 레드-블랙 트리는 업데이트 후 레드-블랙 트리에서 균형을 복원하기 위해 

일정한 수의 트라이노드 재구조화만 필요하다는 개념적 이점이 있다.

10.5.2 Java 구현

코드 조각 10.9 ~ 10.11에서는

레드-블랙 트리를 통해 구현된 딕셔너리의 Java 구현의 주요 부분을 보여준다. 

main 클래스는 코드 프래그먼트 10.9에 표시된 중첩 클래스 RBNode를 포함하며, 

이는 이진 탐색 트리의 키-값 항목을 나타내는 BTNode 클래스를 확장한다. 

추가 인스턴스 변수를 노드의 색상을 나타내는 isRed로 정의하고

이를 설정하고 반환하는 메소드를 정의한다.

코드 조각 10.9: RBTree에 대한 인스턴스 변수, 중첩 클래스 및 생성자.

/** Realization of a dictionary by means of a red-black tree. */
public class RBTree<K,V>
  extends BinarySearchTree<K,V> implements Dictionary<K,V> {
  public RBTree() { super(); }
  public RBTree(Comparator<K> C) { super(C); }
  /** Nested class for the nodes a red-black tree */
  protected static class RBTree<K,V> extends BTNode<Entry<K,V>> {
    protected boolean isRed;  // we add a color field to a BTNode
    RBNode() {/** default constructor */}
    /** Preferred constructor */
    RBNode(Entry<K,V> element, BTPosition<Entry<K,V>> parent,
         BTPosition<Entry<K,V>> left, BTPosition<Entry<K,V>> right) {
      super(element, parent, left, right);
      isRed = false;
    }
    public boolean isRed()  {return isRed;}
    public void makeRed()  {isRed = true;}
    public void makeBlack()  {isRed = false;}
    public void setColor(boolean color)  {isRed = color;}
  }

클래스 RBTree(코드 조각 10.9 ~ 10.11)는 BinarySearchTree(코드 조각 10.3 ~ 10.5)를 확장한다. 

부모 클래스는 트라이노드 재구조화(회전)를 수행하기 위한 메소드 restructure를 지원하며, 

그 구현은 연습(P-10.3)으로 남겨진다. 

클래스 RBTree는 BinarySearchTree로부터

메소드 size, isEmpty, find, findAll를 상속하지만 

메소드 insert 및 remove는 재정의된다. 

먼저 부모 클래스의 해당 메소드를 호출한 다음 

이 업데이트로 인해 발생했을 수 있는 모든 색상 위반을 복구하여 

이 두 가지 연산을 구현한다. 

클래스 RBTree의 몇 가지 보조 메소드는 표시되지 않았지만 

이름은 의미를 제안하고 구현은 간단하다.

 

코드 조각 10.10: 

class RBTree의

딕셔너리 ADT 메소드 insert 및

보조 메소드 createNode와 remedyDoubleRed

  /** Creates a new tree node. */
  protected BTPosition<Entry<K,V>> createNode(Entry<K,V> element,
      BTPosition<Entry<K,V>> parent, BTPosition<Entry<K,V>> left,
      BTPosition<Entry<K,V>> right) {
    return new RBNode<K,V>(element, parent, left, right); // a red-black node
  }
  public Entry<K,V> insert(K k, V x) throws InvalidKeyException {
    Entry<K,V> toReturn = super.insert(k, x);
    Position<Entry<K,V>> posZ = actionPos; // start at the insertion position
    setRed(posZ);
    if (isRoot(posZ))
      setRed(posZ);
    else
      remedyDoubleRed(posZ); // fix a double-red color violation
    return toReturn;
  }
  protected void remedyDoubleRed(Position<Entry<K,V>> posZ) {
    Position<Entry<K,V>> posV = parent(posZ);
    if (isRoot(posV))
      return;
    if (!isPosRed(posV))
      return;
    // we have a double red: posZ and posV
    if (!isPosRed(sibling(posV))) { // Case 1: trinode restructuring
      posV = restructure(posZ);
      setBlack(posV);
      setRed(left(posV));
      setRed(right(posV));
    }
    else { // Case 2: recoloring
      setBlack(posV);
      setBlack(sibling(posV));
      Position<Entry<K,V>> posU = parent(posV);
      if (isRoot(posU))
        return;
      setRed(posU);
      remedyDoubleRed(posU);
    }
  }

메소드 insert(코드 조각 10.10) 및 remove(코드 조각 10.11)는 

슈퍼클래스의 해당 메소드를 먼저 호출한 다음 

보조 메소드를 호출하여 

트리의 균형을 재조정하여 

업데이트 위치(슈퍼클래스에서 상속된 actionPos 변수로 지정됨)에서

루트까지의 경로를 따라 회전을 수행한다.

코드 조각 10.11:

클래스 RBTree의 메소드 remove와 보조 메소드 remedyDoubleBlack

  public Entry<K,V> remove(Entry<K,V> ent) throws InvalidKeyException {
    Entry<K,V> toReturn = super.insert(k, x);
    Position<Entry<K,V>> posR = actionPos; 
    setRed(posZ);
    if (toReturn != null) {
      if (wasParentRed(posR) || isRoot(posR) || isPosRed(posR))
        setBlack(posR);
      else
        remedyDoubleRed(posR);
    }
    return toReturn;
  }
  protected void remedyDoubleBlack(Position<Entry<K,V>> posR) {
    Position<Entry<K,V>> posX, posY, posZ;
    boolean oldColor;
    posX = parent(posR);
    posY = sibling(posR);
    if (!isPosRed(posY))
      posZ = redChild(posY);
      if (hasRedChild(posY)) { // Case 1: trinode restructuring
        oldColor = isPosRed(posX);
        posZ = restructure(posZ);
        setColor(posZ, oldColor);
        setBlack(posR);
        setBlack(left(posZ));
        setBlack(right(posZ));
        return;
      }
      setBlack(posR);
      setRed(posY);
      if (!isPosRed(posX)) { // Case 2: recoloring
        if (isRoot(posU))
          remedyDoubleRed(posU);
        return;
      }
      setBlack(posX);
      return;
    }  // Case 3: adjustment
    if (posY == right(posX)) posZ = right(posY);
    else posZ = left(posY);
    restructure(posZ);
    setBlack(posY);
    setRed(posX);
    remedyDoubleRed(posR);
  }