Red-Black Tree

레드-블랙 트리(1) 레드-블랙 트리(red-black tree) 노드 색깔이 레드나 블랙으로 된 이진 탐색 트리 노드의 성질 N1. 루트나 외부 노드는 모두 블랙 N2. 루트에서 외부 노드까지 경로상에 2개 연속된 레드 노드 없음 N3. 루트에서 외부 노드까지 경로에 있는 블랙 노드 수 같음 포인터의 성질 P1. 외부 노드를 연결하는 포인터는 블랙 P2. 루트에서 외부 노드까지 경로에 2개 연속된 레드 포인터 없음 P3. 루트에서 외부 노드까지 경로에 있는 블랙 포인터 수 같음 포인터 색깔을 알면 그 노드 색깔을 알 수 있고, 노드 색깔을 알면 그 포인터 색깔을 알 수 있음

레드-블랙 트리(3) ⇒ ⇒ 2-3-4트리를 레드-블랙 트리로 변환하는 방법 1) 2-노드는 그대로 레드-블랙 트리의 한 노드로 표현 2) 3-노드는 2개의 노드와 하나의 레드 포인터로 표현 3) 4-노드는 3개의 노드와 2개의 레드 포인터로 표현 5 3 T 1 2 ⇒ 또는 3-노드를 2개의 레드-블랙 노드로 변환 7 5 3 T 1 2 ⇒ 4 4-노드를 3개의 레드-블랙 노드로 변환

레드-블랙 트리(2) 10 20 4 2 6 15 30 1 3 5 21 32 31 33 레드-블랙 트리 예

레드-블랙 트리에서의 삽입(1) 레드-블랙 트리에서의 탐색 레드-블랙 트리에서의 삽입 일반 이진 탐색 트리의 탐색 연산으로 수행 탐색 시간 복잡도 : O(logn) 레드-블랙 트리에서의 삽입 일반 이진 트리에서 사용하는 연산과 비슷 새로운 노드 삽입 시, 노드에 색깔을 지정하는 작업 추가 트리가 공백 : 새로 삽입되는 노드는 루트가 되어 자연히 블랙 트리가 공백이 아닌 경우, 블랙 노드가 추가되면 P3 위반 트리가 공백이 아닌 경우, 레드 노드가 추가되면 P2 위반

레드-블랙 트리에서의 삽입(2) 불균형(imbalance) 불균형의 처리 새로운 노드(u)가 레드이기 때문에 성질 P2를 위반한 경우 노드 u, u의 부모 노드 p, u의 조부모 노드 g에 의한 유형 RRb, RRr, RLb, RLr도 위와 마찬가지 불균형의 처리 XYr(X,Y는 L 또는 R) 타입 : 색깔만 변환시켜 처리 XYb 타입 : 색깔만 변환시키면 P2가 위반되므로, 회전을 시켜 처리 LLb : p는 g의 왼쪽 자식, u는 p의 왼쪽 자식, g의 오른쪽 자식이 블랙인 경우 LLr : p는 g의 왼쪽 자식, u는 p의 왼쪽 자식, g의 오른쪽 자식이 레드인 경우 LRb : p는 g의 왼쪽 자식, u는 p의 오른쪽 자식, g의 오른쪽 자식이 블랙인 경우 LRr : p는 g의 왼쪽 자식, u는 p의 오른쪽 자식, g의 오른쪽 자식이 레드인 경우

레드-블랙 트리에서의 삽입(3) ⇒ ⇒ LLr과 LRr의 색깔 변환 g g p p u u T T g p T T 1 2 p 3 g 4 ⇒ u T 1 2 p 3 g 4 (a) LLr 불균형 처리 ⇒ p T 1 g 4 2 3 T 1 4 2 3 (b) LRr 불균형 처리 LLr과 LRr의 색깔 변환

레드-블랙 트리의 삽입에 대한 LLb와 LRb 회전 레드-블랙 트리에서의 삽입(4) p g T 4 u 2 3 1 ⇒ LLb 회전 (a) LLb 불균형 u T 1 2 g 3 4 p (b) LLb 회전 후 p T 1 g 4 u 2 3 ⇒ LRb 회전 (c) LRb 불균형 p T 1 2 g 3 4 u (d) LRb 회전 후 레드-블랙 트리의 삽입에 대한 LLb와 LRb 회전

레드-블랙 트리에서의 삽입(5) 레드-블랙 트리에 삽입(6, 3, 5, 4) 예 삽입에 따른 색깔 변환과 회전의 수행 1 8 7 2 (a) 초기 레드-블랙 트리 1 8 7 2 6 (b) 키 6 삽입 p 1 8 7 2 6 3 g p u (c) 키 3 삽입 1 8 7 6 3 u (d) LLr 색깔 변환

레드-블랙 트리에서의 삽입(6) 1 8 7 2 6 3 g p 5 u (e) 키 5 삽입 1 8 7 2 5 3 6 (f) LRb 회전 1 8 7 2 5 3 6 4 p g u (g) 키 4 삽입

레드-블랙 트리에서의 삽입(7) 1 8 7 2 5 3 6 4 p g u 5 2 7 1 3 6 8 4 (h) LRr 색깔 변환 (i) RLb 회전

레드-블랙 트리에서의 삭제(1) 레드-블랙 트리에서의 삭제 불균형 일반 이진 탐색 트리에서와 같은 삭제 연산 색깔 변환이나 단순 회전 수행 추가 노드 색깔에 따른 삭제 처리 레드 노드 삭제 : 경로의 블랙 노드 수에 영향을 주지 않음 블랙 노드 삭제 : 경로의 블랙 노드 수를 감소시켜 P3 위반 불균형 삭제된 노드(y)가 블랙이기 때문에 성질 P3를 위반한 경우 노드 y, y의 형제 v, y의 부모 p에 의한 유형 v가 블랙 노드 : Lb 또는 Rb 타입 v가 레드 노드 : Lr 또는 Rr 타입

레드-블랙 트리에서의 삭제(2) 불균형의 처리 Rb, Lb 불균형: 서로 유사한 방법으로 처리. Rb 불균형 : 삭제된 노드의 형제 노드 v의 레드 자식 수(0, 1, 2)에 따라 Rb0, Rb1, Rb2로 나누어 처리 Rb0 : 색깔 변환. p가 블랙인 경우에는 새로운 y로 하는 불균형 타입에 적절한 조치. p가 레드인 경우에는 색깔 변환만으로 종료 Rb1, Rb2 : 회전 시킴. Rr, Lr 불균형 : 서로 유사한 방법으로 처리. Rr 불균형 : 형제 노드 v의 오른쪽 자식이 가지고 있는 레드 자식의 수(0, 1, 2)에 따라 Rr0, Rr1, Rr2로 나누어 처리 Rr1 : 어느 쪽 자식이 레드냐에 따라 2가지로 나뉨. 모든 경우, 단순 회전으로 처리 p

레드-블랙 트리에서의 삭제(3) 레드-블랙 삭제에 대한 Rb0 색깔 변환 레드-블랙 삭제에 대한 Rb1과 Rb2 회전 v T p y 2 또는 (a) Rb0 불균형 v T 1 p y 2 (b) Rb0 색깔 변환 레드-블랙 삭제에 대한 Rb0 색깔 변환 p p p w v v v y v p y T 1 w T T 2 T 1 2 y T 1 T T T y 1 2 3 T T 2 3 (a) Rb1(i) 불균형 (b) Rb1(i) 회전 (c) Rb1(ii) 불균형 (d) Rb1(ii) 회전 레드-블랙 삭제에 대한 Rb1과 Rb2 회전

레드-블랙 트리에서의 삭제(4) 레드-블랙 삭제에 대한 Rb2 회전 v T p y w v T y w v T p y v p T 1 p y w 2 3 (e) Rb2 불균형 v T 1 2 y 3 4 w (f) Rb2 회전 레드-블랙 삭제에 대한 Rb2 회전 v T 1 p y 2 (a) Rr0 불균형 v p T 2 y 1 (b) Rr0 회전 v T 1 p y w 2 3 (c) Rr1불균형 v T 1 2 p 3 y w (d) Rb1(i) 회전

레드-블랙 트리에서의 삭제(5) 레드-블랙 삭제에 대한 Rr0, Rr1, Rr2 회전 v T p y w x v T p y x 3 4 (e) Rb2 불균형 v T 1 p 4 y x w 2 3 (f) Rr1(ii) 회전 v T 1 p y w 2 x 3 4 (g) Rr2 불균형 v T 1 p 4 y x w 2 3 (h) Rr2 회전 레드-블랙 삭제에 대한 Rr0, Rr1, Rr2 회전

레드-블랙 트리에서의 삭제(6) 1 3 4 2 7 5 6 8 (a) 레드-블랙 트리 1 3 4 2 6 7 5 (b) 키 8 삭제 1 3 4 2 6 7 5 (c) Rb0 색깔 변환 1 3 4 2 6 5 (d) 키 7 삭제

레드-블랙 트리에서의 삭제(7) 레드-블랙 트리에서의 삭제 예 1 3 4 2 5 1 3 2 5 4 (e) 키 6 삭제 (f) Rr1(ii) 회전 레드-블랙 트리에서의 삭제 예