12-2강. 레드블랙트리 (3)

RB-DELETE(T, z) // T: Binary Search Tree, z : 삭제할 노드

if left[z] == nil[T] or right[z] == nil[T]	// 자식이 없거나, 자식이 하나거나
	then y <-z	// 실제 이 노드를 삭제하면 된다.
else y <- TREE-SUCCESSOR(z)	// 자식이 둘이라면 y는 z의 SUCCESSOR가 된다.

if left[y] != nil[T]	// 자식이 최대 한 명이라면,
	then x <- left[y]	// x를 왼쪽 자식이라 하고,
else x <- right[y]		// 그렇지 않으면 x를 오른쪽 자식이라 한다.

p[x] <- p[y]	// x의 부모가 y의 부모가 된다.
if p[y] == nil[T]
	then root[T] <- x
else if y == left[p[y]]	// 노드y가 자기 부모의 왼쪽 자식이면
	then left[p[y]] <- x	// x는 왼쪽 자식이 되고
else right[p[y]] <-x	// 그게 아니라면 오른쪽 자식이 된다.
// 여기까지는 삭제 ..

if y != z	// 실제로 삭제한 노드 y가 삭제하려 했던 노드 z가 아닌 경우 (z의 successor을 삭제한 경우)
	then key[z] <- key[y]
    	copy y's satellite data into z
// 여기까지는 BST에서 Delete하는 코드이다..

if color[y] == BLACK	// 삭제한 노드가 BLACK이었을 경우,	
	then RB-DELETE-FIXUP(T, x)	// X : 실제로 삭제한 노드의 자식노드

return y

 

• 레드블랙트리에서의 DELETE

- 보통의 Binary Search Tree에서처럼 DELETE한다.

- 실제로 삭제된 노드 y가 red라면 종료한다.

- y가 black이었을 경우, RB-DELETE-FIXUP을 호출한다.

 

 

RB-DELETE-FIXUP(T, x) 해야 하는 경우

1. 모든 노드는 RED or BLACK이어야 한다. => OK

2. y가 루트였고, x가 red인 경우 위반

3. 모든 NIL노드는 black이어야 한다. => OK

4. p[y] 와 x가 모두 red일 경우 위반

5. 원래 y를 포함했던 모든 경로는 이제 black노드가 하나 부족하다

   1) 노드 x에 "extra black"을 부여해서 일단 조건5를 만족한다

   2) 노드 x는 "double black" 혹은 "red & black

 

- 아이디어 : 

   - extra black을 트리의 위쪽으로 올려 보낸다

   - x가 red&black상태가 되면 그냥 black노드로 만드로 끝낸다

   - x가 루트가 되면 그냥 extra black을 제거한다

 

- Loop Invariant

   - x는 루트가 아닌 double-black노드

   - w는 x의 형제노드

   - w는 NIL노드가 될 수 없음(아니면 x의 부모에 대해 조건 5가 위반된다.)

 

 

 

Red-Black Tree에서 delete는 여덟가지 경우가 있다.

네 가지는 왼쪽, 네 가지는 오른쪽인 대칭적인 경우이다.

 

case 1

Case 1. w가 RED인 경우 (w : x의 형제노드)

- w의 자식들은 black

- w를 black으로, p[x]를 red로

- p[x]에 대해서 left-rotation 적용

- x의 새로운 형제노드는 원래 w의 자식노드, 따라서 black노드

- Case2,3, 4에 해당

 

 

case 2

Case 2. w는 black이고 w의 자식들도 black

- x의 extra-black을 빼앗고, w를 red로 바꾼다

- p[x]에게 빼앗은 extra-black을 준다

- p[x]을 새로운 x로 해서 계속한다

- 만약 Case1에서 이 경우에 도달했다면, p[x]는 red였고, 따라서 새로운 x는  red&black이 되어서 종료한다.

(gray노드는 unknown color)

 

 

case 3

Case 3. w는 black이고 w의 왼쪽 자식이 red

- w 를 red로, w의 왼쪽 자식을 black으로

- w에 대해서 right-rotation 적용

- x의 새로운 형제 w는 오른쪽 자식이 red -> case4에 해당

 

 

case 4

Case 4. w는  black이고 w의 오른쪽 자식이 red

- w의 색을 현재 p[x]의 색으로 한다(unknown color)

- p[x]를 black으로, w의 오른쪽 자식을 black으로

- p[x]에 대해서 left-rotation을 적용한다

- x의 extra-black을 제거하고 종료한다

 

 

 

Red-Black Tree Sudo Code