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

문제 상황 : 현실세계에서는 완벽하게 정렬된 Binary Search Tree는 찾기 힘들다. 오른쪽으로 극단적으로 치우친 경우가 존재할 수 있다.

 

보완 방법 : 레드블랙트리(Red-Black Tree)는 이를 보완하기 위해 등장했다.

완벽하게 트리의 균형을 맞출 수는 없으나, 어느정도 보완을 가능하게 한다.

INSERT, DELETE 알고리즘을 적절하게 수정했다.

 

 

• 레드블랙트리

레드블랙트리

- 이진탐색트리의 일종

- 균형 잡힌 트리 : 높이가 O(log2n)

- SEARCH, INSERT, DELETE 연산을 최악의 경우에도 O(log2n) 시간에 지원한다.

 

- 각 노드는 하나의 키(key), 왼쪽자식(left), 오른쪽 자식(right), 그리고 부모노드(p)의 주소를 저장한다.

- 자식노드가 존재하지 않을 경우, NIL 노드라고 부르는 특수한 노드가 있다고 가정한다.

- 따라서 모든 리프노드는 NIL노드이다.

- 루트의 부모도 NIL노드라고 가정한다.

- 노드들은 내부노드와 NIL노드로 분류한다.

(NIL노드는 가상적인 노드임. 실제로 구현하지는 않는다.)

 

 

레드블랙트리 (검정색 노드 : black, 하얀색 노드 : red)

레드블랙트리

- 다음의 조건을 만족하는 이진탐색트리

   1. 각 노드는 red 혹은 black이고,

   2. 루트노드는 black이고,

   3. 모든 리프노드(즉, NIL노드)는 black이고,

   4. red노드의 자식노드들은 전부 black이고(즉, red노드는 연속되어 등장하지 않고),

   5. 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 갯수의 black노드가 존재한다.

 

 

- 높이가 h인 블랙-높이는 bh >= h/2 이다.

   - 조건4에 의해 레드노드는 연속될 수 없으므로 당연하다.

- 노드 x를 루트로 하는 임이의 부트리는 적어도 2^(bh(x)) -1개의 내부노드를 포함한다.(수학적귀납법)

- n개의 내부노드를 가지는 레드블랙트리의 높이는 2log2(n+1) 이하이다.

   - n >= 2^(bh) -1 >= 2^(h/2) -1 이므로, 여기에서 bh와 h는 각각 루트노드의 블랙-높이와 높이

 

 

• 레드블랙트리의 SEARCH, INSERT, DELETE

SEARCH 알고리즘은 Binary Search Tree와 완벽히 동일하다.

INSERT와 DELETE를 배워 볼 건데, Left and Right Rotation이라는 사전지식이 필요하다.

 

• Left and Right Rotation

  - 시간복잡도 O(1)

  - 이진탐색트리의 특성을 유지

 

LEFT-ROTATE(T, x)	// T : Tree, x : node
{
	y <- right[x]	// Set y
    right[x] <- left[y]	// Turn y's left subtree into x's right subtree
    p[left[y]] <- x
    p[y] <- p[x]	// Link x's parent to y. x의 부모가 y의 부모
    if p[x] == nil[T] // 현재 x의 부모가 nil이라면,
    	then root[T] <- y	// y가 새로운 트리의 루트가 된다
        else if x == left[p[x]]	// x의 부모노드가 실제로 존재한다면,
        	then left[p[x]] <- y	// y가 x의 왼쪽자식이다
           	else right[p[x]] <- y	// y가 x의 새로운 오른쪽 자식이라면,
    left[y] <- x	// Put x on y's left. x가 y의 왼쪽자식이다
    p[x] <- y	// x의 부모가 y가 된다
}

y = right[x] != NIL이라고 가정한다.

루트노드의 부모도 NIL이라고 가정한다.