[컴퓨터알고리즘] 11. 레드블랙트리

Red-black tree

- 트리의 균형을 보장 -> 최악의 경우에도 O(lgn) 시간에 수행.

- color 속성: red 또는 black. // BST에서 상속되는 속성 key, left, right, p

- 리프노드(빈 트리)들은 흑색인 경계노드 T.nil. 널포인터 역할임 // T.nil.color=black.

- 루트노드의 부모노드도 T.nil

 

- key가 있으면(nil아니면) 다 내부노드, 모든 내부 노드는 자식 2개 가짐. (nil 리프는 보여지지 않을 뿐)

- 맨밑 경계노드 T.nil 만이 리프노드=외부노드. 항상 흑색. RBT는 (BST에서의) NULL 대신 T.nil 가리켜 사용

 

레드블랙트리의 특성

1. 모든 노드는 red거나 black이다.

2. 루트 노드는 black이다.

3. 모든 리프 노드(nil)는 black이다.

4. 노드가 red이면 두 자식은 black이다. (연속으로 두개의 red 불가. 흑색은 가능) # 이로 인해 빨간색이 절반이하가 됨

5. 각 노드에 대해, 하위 리프까지의 모든 경로에서 같은 수의 black 노드를 갖는다. # 치우치지x, 균형잡힌트리.

- 특성 깨지면 fixup 해야함.

 

레드블랙트리의 height, black-height

- 노드의 height "h(x)" : 리프에서부터 가장 긴 경로의 간선 수

- 노드 x의 black-height "bh(x)" : x의 자식노드에서 leaf까지의 black 노드의 갯수 (T.nil 포함, x 미포함)

- RBT의 black-height는 root의 black-height이다.

- 특성 5에 의해 black height가 잘 정의된다. (all path에서 같은 수의 black 노드)

  bh(x) ≤ h(x) ≤ 2bh(x)

 

 

n개의 키를 갖는 레드블랙트리의 높이가 h ≤ 2log(n+1)임을 증명.

루트가 x인 서브트리는 적어도 2^bh(x) - 1개의 내부노드를 갖는다.
# why? 보통 트리에서 키가 h면 최대 2^h - 1개 내부노드 갖는데
# RBT는 내부노드가 모두 자식 2개라서 직관적으로 합쳤을때의 자식층의 black노드 2개 이상 됨

특성4에 의해 leaf까지의 경로에서 절반이상이 흑색.
leaf까지의 경로상에서 적색노드수<=h/2고 흑색노드수>=h/2. "h/2<=bh(x)<=h"
  
* Basis: x의 높이가 0일 때  2^bh(x) - 1 = 1 - 1 = 0
         -> 0개의 내부노드를 가짐.
* Inductive step:
         x 노드의 높이 h이고 bh(x) = b라고 하자
         x의 자식노드 높이 h-1
         x의 자식노드의 bh: 자식노드 흑색이면 b-1, 적색이면 b. -> 적어도 b-1, 최대 b
         -> x의 자식노드는 적어도 "2^bh(x)-1 - 1"개의 내부노드를 갖는다.
 이를 이용해 총 내부노드수를 구하면 2^bh(x)-1 - 1 + 2^bh(x)-1 - 1 + 1 => 2^bh(x) - 1.
 n >= 2^bh(x) - 1. n+1 >= 2^bh(x). h/2 <= lg(n+1). h<=2lg(n+1).
 * 결론: h <= 2lg(n+1). # h = O(lgn).

 

 

레드블랙트리의 모든 연산은 O(lgn)에 수행된다. 검색, 최대최소 같은 것은 BST 랑 같은데 Insertion과 Deletion은 색깔을 조정해야 해서 코드가 다르다.

 

Rotations: 트리를 재구성하는 연산. 균형 맞추기 위해.

- 포인터(선)을 바꾸어 지역적인 구조를 바꾼다. BST 특성을 위반하지 않음.

 

Left-Rotate(T,x) 수도코드

Left-Rotate(T,x)
  y <- right[x] # y는 x의 오른쪽 자식 노드
  right[x] <- left[y]	# x의 오른쪽 서브트리를 y의 왼쪽 서브트리로 변경
  if left[y] != nil[T]	# left[y]가 nil[T]이면 left[y]의 부모를 x로 변경
     p[left[y]] <- x
  p[y] <- p[x] 		# y의 부모를 p[x]로 변경
  if p[x] = nil[T]  	# p[x]가 nil[T]이면 T의 루트노드를 y로 설정
     root[T] <- y
  else if x = left[p[x]] # x가 x의 부모노드의 왼쪽자식이면 y도 왼쪽자식, 
     left[p[x]] <- y
  else 			# 그렇지 않으면 오른쪽자식
     right[p[x]] <- y
  left[y] <- x 			# y의 왼쪽자식을 x로 변경
  p[x] <- y			# x의 부모를 y로 변경

순서

(1) y의 왼쪽 서브트리를 x의 오른쪽 서브트리로 옮김

(2) y의 부모노드를 p[x]로 하고 이때 y가 루트노드인지 확인

(3) x가 p[x]의 왼자식이었는지 오른자식이었는지 확인하여 y가 p[x]의 왼/오른자식으로 설정

(4) y의 왼쪽자식을 x로 변경, x의 부모노드를 y로 설정

 

- Left-Rotate 수도코드는 right[x] != nil[T], root의 부모가 nil[T]임을 가정함.

- 왼쪽 회전의 결과: x의 오른자식이 y였는데 y의 왼자식이 x로 바뀌고,  y의 왼쪽 서브트리가 x의 오른쪽 서브트리가 됨

- left, right rotation 코드는 서로 left, right 만 바꾼 반대.

- 시간복잡도 O(1)

 

레드블랙트리 삽입

1) BST의 Tree-Insert 처럼 진행한 후 (차이 있음)

2) 삽입한 노드 z를 적색으로 칠함. // RBT특성 4번 위반될 수 있음

3) re-coloring과 rotations를 통해 수정된 트리를 Fix해야 한다. "RB-Insert-Fixup"

4) 루트노드를 흑색으로 칠함.

 

Insertion

- BST와의 차이가 중요. 삽입한 노드 z를 빨간색으로 칠한 후 RB-Insert-Fixup를 호출.

RB-Insert(T,z)
  y <- nil[T]  # y에 x의 부모 노드를 담음
  x <- root[T]
  while x != nil[T]  # x가 리프 노드가 될 때까지 탐색
    do y <- x
      if key[z] < key[x]
         then x <- left[x]
         else x <- right[x]
  p[z] <- y      # z를 y에 연결할것임. z의 부모 노드를 y로 설정
  if y = nil[T]  # y가 nil이라면 z가 루트노드이며 연결할 부모노드 없음
    then root[T] <- z
    else if key[z] < key[y] # y가 nil이 아니면 y의 왼/오자식을 z로 설정
       then left[y] <- z
       else right[y] <- z
  left[z] <- nil[T] # z의 자식노드들 nil로 설정
  right[z] <- nil[T]
  color[z] <- RED # z의 색깔 RED로 설정
  RB-Insert-Fixup(T,z) # Fixup 진행

 

RB-Insert-Fixup

while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right
        if y.color == RED 	# case 1
            z.p.color = BLACK
            y.color = BLACK
            z.p.p.color = RED
            z = z.p.p
        else
            if z == z.p.right	# case 2
                z = z.p
                left-rotate(z)
            z.p.color = BLACK	#case 3
            z.p.p.color = RED
            right-rotate(z.p.p)
    else # if z.p == z.p.p.right
        y = z.p.p.left
        if y.color == RED
            z.p.color = BLACK
            y.color = BLACK
            z.p.p.color = RED
            z = z.p.p
        else
            if z == z.p.left
                z = z.p
                right-rotate(z)
            z.p.color = BLACK
            z.p.p.color = RED
            left-rotate(z.p.p)
T.root.color = BLACK # 루트 노드를 black으로 색칠

그림으로 절차 그리기...

 

#  p[p[z]]의 왼자식이 p[z], 오른자식이 y로 가정

 

Case 1: 삼촌노드 y가 red인 경우

- z, p[z], y가 red인 상황이다

- p[z], y를 black으로 하고 p[p[z]]를 red로 한뒤 새로운 z로 삼는다.

 

Case 2: y가 black, z가 right child인 경우

- y가 black인경우 y는 고려하지 않아도 된다

- z <- p[z] 후 z가 오른자식이라면 left-rotate(z)

- 그후 Case 3을 수행한다

 

Case 3: y가 black, z가 left child인 경우 (z, p[z] 둘 다 부모의 오른자식)

- p[z]를 black으로, p[p[z]]를 red로 칠한다

- right-rotate(p[p[z]])

 

RBT 특성

1. 모든 트리 red 또는 black

2. 루트 노드 색깔 black

3. 리프 노드 색깔 black

4. red 노드는 red 자식노드 가질 수 없다

5. 모든 경로 상에서 black 노드 수 동일 (bh)
* 노드 삽입/삭제 의해 깨지는 RBT 특성: 2번, 4번

- 2번 특성 깨질 때: 빈 트리에서 1개 삽입되어 빨간 노드가 유일한 노드 또는 검-빨에서 검은노드 삭제됨

- 4번 특성 깨질 때: 빨 노드 아래 빨 노드

 

 

Insertion-Fixup

수도코드, c언어 코드 작성한 것 보기

삼촌 노드가 적색이면 case 1

< 꺾여있으면 case 2

/ 펴져있으면 case 3

 

RBT 삽입의 루프 불변성

- while(z.p==RED)이 유지되는 동안 불변하는 조건

3가지

1. z는 red.

2. z.p가 root면 z.p는 흑색.

3. RBT 특성이 위배되는 경우 (2번 or 4번) 이 중 한 가지만 위배된다.

- 2번 위배: z 적색, z.p가 경계노드이고 흑색 // 초기조건에서 2번 위반된다면 z가 유일노드

- 4번 위배: z와 z.p 모두 적색 //  z가 유일노드가 아닐 때만 가능

* 초기조건: 첫 반복 시작 전에 RBT + z의 구성
1, 2 만족함.
3번
- 노드 z가 유일한경우 특성 2 위배될 수 있음.
- z가 유일노드이며 적색일 때 -> z.p가 경계노드, 흑색이므로 4번과 동시 위배 x.
- z가 유일노드가 아니면 2번 위배 x, 4번만 위배될 수 있음.

* 유지조건
- 루프가 돌아간다는 것은 z.p.color==RED 즉 z가 유일 노드가 아님을 뜻함.
1. 만족함
2. 내부 코드에서 모든경우에 최종 z.p가 BLACK이 되므로 만족
3. 루프가 돌아간다는 것은 z.p.color==RED 즉 z가 유일 노드가 아님을 뜻함. 따라서 특성4만이 위배되는 것 옳음.

* 종료조건
1. 만족함
2. z.p == BLACK일때 루프 빠져나오므로 만족
3. 특성 2, 특성 4 둘 다 종료시 위배x. 종료될 때 while문 종료됨과 동시에 tree의 root색을 빨간색으로 바꿈

 

알고리즘 분석

- RBT 삽입 및 fixup 시간복잡도: O(lgn)

- 회전연산 시간복잡도: O(1)

 

RBT 삽입 예시

- x를 트리에 삽입한다. 적색으로 칠한다.

- RBT 특성 중 4번만이 깨질 수 있다. 위반사항을 트리의 위쪽으로 올린다. (재색칠과 회전)

 

새로운 노드 들어왔을 때 RBT 다시 그릴 줄 알아야 함!

노드 몇이 들어왔을때, 최종 RBT를 그려라

 

Deletion

- RBT 특성 모두 만족시켜야. 2, 4번 특성 위반될 수 있음. 특성 위반되는 경우: 삭제된 노드가 검정색

1) BST 삭제 진행하고

2) 위반된 특성들 고치기.

RB-Delete(T,z)
  y = z
  y-original-color = y.color
  if z.left == T.nil
     x = z.right
     RB-TRANSPLANT(T,z,z.right)
  else if z.right == T>nil
     x = z.left
     RB-TRANSPLANT(T,z,z.left)
  else y = TREE-MINIMUM(z.right)
     y-original-color = y.color
     x = y.right
     if y.p == z
        z.p = y
     else RB-TRANSPLANT(T,y,y.right)
     	y.right = z.right
        y.right.p = y
     RB-TRANSPLANT(T.z, y)
     y.left=z.left
     y.left.p = y
     y.color = z.color
  if y-original-color == BLACK
     RB-DELETE-FIXUP(T,x)

RB-TRANSPLANT(T,u,v)
  if u.p == T.nil
    T.root = v
  else if u == u.p.left
    u.p.left = v
  else
    u.p.right = v
  v.p = u.p

FIXUP은 나중에 추가

 

RB-Delete에서는 삭제하려는 노드 x가 black일 때만 문제가 된다.
내 자신을 x, 같은 부모의 다른 자식(자매노드)을 w라고 하자.

케이스 나눌 때는 w와 w의 자식노드들 색깔을 확인한다.

 

이 글 읽기

https://velog.io/@hbtopkr/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%ACrbtree-%EB%85%B8%EB%93%9C-%EC%82%AD%EC%A0%9C-%EC%97%B0%EC%82%B0

레드-블랙 트리(rbtree) 노드 삭제 연산에 대한 이해와 구현

 

Case 1: w가 적색

- w의 두 자식 모두 흑색노드. x.p도 흑색.

- w를 흑색으로, x.p를 적색으로 바꾸고 x.p에서 left rotate.

- x의 새 자매노드는 이전 w의 자식노드이므로 흑색노드. 애를 새 w로 삼는다.

 

Case 2: w가 흑색, w의 두 자식 모두 흑색 (x.p의 색깔은 모름)

- x의 이중흑색 제거하고 w를 적색으로 함

- x.p를 새로운 x로 다음 루프 진행

Case 3: w가 흑색, w의 왼쪽 자식이 적색이고 오른쪽 자식이 흑색 (x.p의 색깔은 모름)

- w를 적색, w의 왼쪽 자식을 흑색으로 하고 w에서 right rotate

- w의 왼쪽자식이 x의 새 자매노드가 되며 적색 오른쪽 자식을 갖게됨

 

Case4: w가 흑색, w의 왼쪽 자식이 흑색이고 오른쪽 자식이 적색 (x.p의 색깔은 모름)

- w를 w의 부모 색깔로 칠함 (색깔을 모르지만 문제없음)

- x.p를 흑색으로 칠하고 w의 오른쪽 자식을 적색으로 칠한 후 left rotate.

- x의 이중흑색 제거하고 

- new x = T.root

 

레드블랙트리의 삭제 연산에 언급되는 "remove the extra black on x, x is now singly black"
* 이중 흑색 상태: 어떤 노드가 두 개의 흑색을 가지는 상태.

이중 흑색 제거 (Fixup)
1. 형제 노드가 적색인 경우:
형제 노드를 흑색으로 바꾸고 부모 노드를 적색으로 변경
이후 좌회전 또는 우회전 연산을 수행

2. 형제 노드가 흑색이며 형제의 자식들이 모두 흑색인 경우:
형제 노드를 적색으로 바꾸고 부모 노드의 흑색을 형제 노드와 자신에게 나눠줌
이중 흑색을 부모 노드로 이동시킴

3. 형제 노드가 흑색이며 형제의 먼 쪽 자식이 흑색이고 형제의 가까운 쪽 자식이 적색인 경우:
형제의 가까운 쪽 자식을 흑색으로, 형제 노드를 적색으로 바꿈
형제 노드를 기준으로 회전 연산을 수행함

4. 형제 노드가 흑색이며 형제의 먼 쪽 자식이 적색인 경우:
부모 노드의 색상을 형제 노드로 이동시키고, 부모 노드를 흑색으로 바꿈
형제의 먼 쪽 자식을 흑색으로 바꿈
부모 노드를 기준으로 회전 연산을 수행함

이 과정을 통해 이중 흑색 상태를 제거하면 x는 "singly black" 상태가 됨.