13 Red-black Trees

13 Red-Black Trees

13 Red-Black Trees13.1 Properties of red-black trees13.2 Rotations13.3 Insertion13.4 Deletion

$O(h)$ $O(lg \; n)$ 시간이 걸리는 것을 보장하기 위해 "balanced"된 많은 search-tree 전략중의 하나이다.

13.1 Properties of red-black trees

red-black tree는 node마다 한 개의 추가 비트의 storage를 가진 binary search tree이다: 그것은 바로 color인데, 이것은 RED 또는 BLACK 둘 중 하나일 수 있다. root에서 한 leaf로 가는 어떤 simple path에서 node colors를 제한하여, red-black trees는 어떤 path가 어떤 다른 것보다 두 배 이상 되지 않도록 보장한다. 그 tree가 approximately balanced되게 하기 위해서이다.

그 트리의 각 노드는 이제 attributes인 color, key, left, right, and p를 포함한다. 만약 한 노드의 부모 또는 자식이 존재하지 않는다면, 그 노드의 대응되는 pointer attribute는 NIL 값을 포함한다. 우리는 이러한 NILs를 binary search tree의 leaves에 (external nodes)대한 포인터로 간주할 것이고, 그 보통의, key를 가진 노드들을 그 트리의 internal nodes로 간주할 것이다.

red-black tree는 다음의 red-black properties를 만족하는 binary tree이다:

모든 노드는 red이거나 black이다.
그 root는 black이다.
모든 leaf (NIL)은 black이다.
만약 한 노드가 red라면, 그러면 그것의 두 자식 모두 black이다.
각 노드에 대해, 그 노드에서 자손 leaves로 가는 모든 simple paths는 black nodes의 같은 개수를 포함한다.

그림 13.1(a)는 red-black tree의 한 예시를 보여준다.

$T.nil$ 은 그 트리에서 평범한 노드와 같은 attributes를 가진 오브젝트이다. 그것의 color attribute는 BLACK이고, 그것의 다른 attributes들 - p, left, right, and key- 는 임의의 값을 취할 수 있다. 그림 13.1(b)가 보여주듯이, NIL에 대한 모든 포인터들은 sentinel T.nil에 대한 포인터로 대체된다.

우리는 한 node x의 NIL child를 부모가 x인 평범한 노드로서 다룰 수 있게 하기 위해 sentinel를 사용한다. 비록 우리가 대신에 tree에서 각 NIL에 대ㅐ 별개의 sentinel node를 추가할 수 있을지라도, 각 NIL의 부모가 잘 정의되게 하기 위해, 그 접근법은 공간을 낭비할 것이다. 대신에, 우리는 모든 NILs를 나타내기 위해 한 개의 sentinel T.nil를 사용할 것이다 - 모든 leaves이며 그 root의 parent이다. 그 sentinel의 attributes인 p, left, right, and key의 값들은 실체가 없는 것이다. 비록 우리가 편리함을 위해 한 절차 도중에 그것들을 설정할지라도.

우리는 일반적으로 우리의 흥미를 red-black tree의 internal nodes에 국한한다. 왜냐하면 그것들이 key values를 가지기 때문이다.이 챕터의 나머지에서, 우리는 red-black trees를 그릴 때, 그 leaves를 생략한다. 그림 13.1(c)에서 보여지듯이.

black-height $bh(x)$ 로 표기한다. property 5에 의해, black height의 개념은 잘 정의된다. 왜냐하면 그 노드의 모든 내려가는 simple paths들은 같은 수의 black nodes를 가져야 하기 때문이다. 우리는 한 red-black tree의 black-height가 그것의 root의 black-height가 되도록 정의한다.

다음의 lemma는 왜 red-black trees가 좋은 search trees를 만드는지를 보여준다.

Lemma 13.1

$2lg(n+1)$ 의 height를 가진다.

Proof $2^{bh(x)} -1$ $2^{bh(x)} - 1 = 2^0 - 1 = 0$ $bh(x)$ $bh(x) - 1$ $2^{bh(x)- 1}- 1$ $(2^{bh(x) - 1} -1) + (2^{bh(x) - 1} -1) + 1 = 2^{bh(x)} - 1$ 의 internal nodes를 포함한고, 이것은 그 주장을 증명한다.

$h/2$ 가 됨에 틀림이 없다; 따라서,

$n \geq 2^{h/2} - 1$ .

1은 좌변으로 옮기고, 양변에 로그를 취하여 다음을 만들어낸다

lg(n+1) \geq h/2 \text{, or } h \leq 2lg(n+1)

$O(lg \; n)$ $O(h)$ $O(lg\; n)$ $O(lg\; n)$ $O(lg \;n)$ time에 이러한 두 연산을 지원하는 방법을 볼 것이다.

Exercises

13.1-1

$\{1,2, \dots, 15\}$ 에 대해 height가 3인 complete binary search tree를 그려라. 최종 red-black trees의 black-heights가 2, 3, 그리고 4가 되도록 세 개의 다른 방식들로 NIL leaves와 color를 추가해라.

13.1-2

key 36으로 TREE-INSERT가 그림 13.1에 있는 트리에 호출된 후에 발생하는 red-black tree를 그려라. 만약 그 삽입된 노드가 red로 색칠된다면, 그 최종 tree를 레드블랙 트리인가? 만약 그것이 black으로 색칠된다면 어떤가?

Ans : key 35를 가진 것의 우측 자식 노드에 될 건데, red로 칠해진다면, red-black tree의 규칙성을 깬다. 하지만 black으로 칠해진다면 red-black tree의 규칙을 유지한다.

13.1-3

red-black properties의 1, 3, 4, 그리고 5를 만족하는 binary search tree를 relaxed red-black tree라고 정의하자. 즉, 그 root는 red이거나 black 둘 중 하나일지도 모른다. root가 red인 relaxed red-black tree T를 고려해라. 만약 우리가 T의 root를 black으로 색칠하지만, T에 어떠한 변화도 주지 않는다면, 그 최종 트리는 red-black tree인가?

Ans : 그렇다

13.1-4

우리가 red-black tree에 있는 모든 red node를 그것의 black parent로 흡수시킨다고 가정해보자. 이것은 red node의 자식들이 black parent의 자식이 되게 하기 위해서이다 (그 키에 무엇이 발생할지는 무시하자.) 그것의 red children이 흡수된 후에, black node의 가능한 degrees는 무엇인가? 너는 그 최종 tree의 leaves의 depths에 대해 무엇을 말할 수 있는가?

Ans : 무슨 말인지 모르겠다.

13.1-5

red-black tree에서 한 노드 x에서 자손 leaf로 가는 가장 긴 simple path가 node x에서 한 자손 leaf로 가는 가장 짧은 경로의 가장 길어봐야 두 배의 길이를 가진다는 것을 보여주어라.

Ans : 그림 13.1 (c)에서 key 41를 가진 노드에서 leaf들은 47, 28, 35, 39 key를 가진 node들인데, 각각 경로의 길이는 1, 2, 3, 3이다. 근데 위의 주장에 따라 at most twice보다 더 많다. 왜냐하면 1, 3은 3배 차이이기 때문이다. 이건 root를 봐도 마찬가지 이다. 26 key를 가진 노드에서 가장 짧은 경로를 가진 leaf는 47 key를 가진 node로 경로는 2이다. 그리고 가장 긴 경로는 3의 key를 가진 노드로서, 경로는 5의 길이이다. 따라서 2배 이상 차이난다. 따라서 아니다. 근데 해설지에서는 그렇다라고 말하는데, 해설지를 봐도 모르겠다.

13.1-6

red-black tree에서 black-height k를 가진 internal nodes의 가장 큰 숫자는 무엇인가? 가장 작은 가능한 개수는 무엇인가?

Ans : 무슨 말인지 모르겠다

13.1-7

black internal nodes에 대한 red internal nodes의 가능한 가장 큰 비율을 구체화하는 n개의 키에 대한 red-black trees를 설명해라. 이 비율은 무엇인가? 무슨 트리가 가장 작은 가능한 ratio를 가지는가? 그 비율은 무엇인가?

$2lg(n + 1)$ 의 height를 갖는다고 한다. 그 때, height만큼의 black node를 가질 수 있을 것이다. 그 때, 이미 root는 black일 것이고, leaf 내려갈 때, height - 1만큼 black node를 가질 수 있을 것이다. 대충 여기까지만 생각이 든다. 이 이후에는 수학적으로 뭘 해야할 거 같은데. 어떻게 하는지도 모르겠고 머리가 아프다...

13.2 Rotations

$O(lg\;n)$ time이 걸린다. 왜냐하면 그것들이 트리를 수정하기 때문에, 그 결과는 Section 13.1에서 열거된 red-black properties를 위반할지도 모른다. 이러한 특성을 회복하기 위해, 우리는 트리에 있는 노드들의 색깔들을 바꾸어야 햐고, 그 포인터 구조를 바꿔야 한다.

우리는 rotation을 통해서 그 pointer structure를 바꾸는데, 이것은 binary-search-tree property를 보존하는 search tree에서 local operation이다. 그림 13.2는 두 가지 종류의 회전을 보여준다 : left rotations and right rotations. 우리가 한 노드 x에 대해 left rotation을 할 때, 우리는 그것의 오른쪽 child인 y는 T.nil이 아니라고 가정한다; x는 트리에서 오른쪽 자식이 T.nil이 아닌 어떤 노드일지도 모른다. 그 left rotation은 x에서 y로 가는 link를 중심으로 한다. 그것은 y가 그 subtree의 새로운 root가 되게 하고, x를 y의 left child로 하고, y의 left child는 x의 right child가 된다.

$x.right \neq T.nil$ $T.nil$ 이라는 것을 가정한다.


LEFT-ROTATE(T, x)
1   y = x.right             // set y
2   x.right = y.left        // y의 왼쪽 subtree를 x의 right subtree로 바꿈
3   if y.left != T.nil
4       y.left.p = x
5   y.p = x.p               // link x's parent to y
6   if x.p == T.nil
7       T.root = y
8   elseif x == x.p.left
9       x.p.left = y
10  else x.p.right = y
11  y.left = x              // put x on y's left
12  x.p = y

$O(1)$ 시간에 작동한다. 회전에 의해 오직 포인터들만 바뀐다; 노드에 있는 모든 다른 attributes는 같게 유지된다.

Exercise

13.2-1

RIGHT-ROTATE를 위한 의사코드를 작성해라.


xxxxxxxxxx
RIGHT-ROTATE(T, y)
1   x = y.left          // set x
2   y.left = x.right    // turn x'right subtree into y's left subtree
3   if x.right != T.nil
4       x.right.p = y
5   x.p = y.p           // link y's parent to x
6   if y.p == T.nil
7       T.root = x
8   elseif y == y.p.left
9       y.p.left = x
10  else y.p.right = x
11  x.right = y
12  y.p = x

13.2-2

모든 n-node binary search tree에서, 정확히 n - 1개의 가능한 회전이 있다는 것을 주장해라.

Ans : 음... 왤까... 정확히 뭘 물어보는건지 모르겠다. 그냥 leaf만 아니라면, 다 left/right rotate 시킬 수 있는거 아닌가?

13.2-3

$a, b, c$ $\alpha, \beta, \gamma$ $a, b, c$ 의 depths는 어떻게 변하는가?

$\alpha$ $\beta$ $\gamma$ 는 영향을 받지 않으므로 가만히 있는다.

13.2-4

$O(n)$ rotations을 사용하여 임의의 어떤 다른 n개의 노드를 가진 binary search tree로 변환될 수 있다는 것을 보여라. (Hint: 처음에 최대로 해야 n - 1개의 right rotations이 그 트리를 right-going chain으로 바꾸는데 충분하다는 것을 보여라.)

Ans : n - 1번 right rotations하면 계속 오른쪽으로 가는 chain으로 바뀐다. 따라서 binary search tree 특성에 맞게 된다.

13.2-5

$T_1$ $T_2$ right-converted $T_1$ $T_2$ $T_1$ $T_2$ $T_1$ $T_2$ $T_1$ $T_2$ $O(n^2)$ 에 대한 호출을 사용하여 right-converted 될 수 있다는 것을 보여주어라.

ANS : 찾기 어려운듯;;

13.3 Insertion

$O(lg\;n)$ time에 n개의 노드를 가진 red-black tree에 한 노드를 넣을 수 있다. 그렇게 하기 위해, 우리는 TREE-INSERT procedure (Section 12.3)의 조금 수정된 버전을 사용한다, tree T에 node z를 넣기 위해서, 마치 그것이 평범한 binary search tree인 것 처럼, 그러고나서 우리는 z를 red로 색칠한다 (Exercise 13.3-1은 너에게 왜 우리가 z를 black이 아닌 red로 칠해야 하는지를 설명하라고 한다.) red-black properties가 보존되도록 보증하기 위해, 우리는 그러고나서 nodes를 재색칠하기 위해 RB-INSERT-FIXUP이라는 보조 procedure를 호출하고, 회전을 수행한다. 그 RB-INSERT(T,z)는 node z를 넣는데, 그 key는 red-black tree T에 이미 채워져 있다고 가정된다.


xxxxxxxxxx
RB-INSERT(T,z)
1   y = T.nil
2   x = T.root
3   while x != T.nil
4       y = x
5       if z.key < x.key
6           x = x.left
7       else x = x.right
8   z.p = y;
9   if y == T.nil
10      T.root = z
11  elseif z.key < y.ey
12      y.left = z
13  else y.right = z
14  z.left = T.nil
15  z.right = T.nil
16  z.color = RED
17  RB-INSERT-FIXUP(T,z)

$z.left$ $z.right$ 를 RB-INSERT의 lines 14-15에서 T.nil로 설정한다. 이것은 적절한 tree structure를 유지하기 위해서이다. 세 번 째로, 우리는 line 16에서 z를 red로 칠한다. 넷 째로, z를 red로 칠하는 것은 red-black properties 중 하나를 위반하게 할 수 있을지도 모르기 때문에, 우리는 red-black properties를 회복하기 위해 RB-INSERT의 line 17에서 RB-INSERT-FIXUP(T,z)를 호출한다.


xxxxxxxxxx
RB-INSERT-FIXUP(T,z)
1   while z.p.color == RED
2       if z.p == z.p.p.left
3           y = z.p.p.right
4           if y.color == RED
5               z.p.color = BLACK           // case 1
6               y.color = BLACK             // case 1
7               z.p.p.color = RED           // case 1
8               z = z.p.p                   // case 1
9           else if z == z.p.right          // @Chan : else안에서 if문이다.
10                  z = z.p                 // case 2
11                  LEFT-ROTATE(T,z)        // case 2
12              z.p.color = BLACK           // case 3
13              z.p.p.color = RED           // case 3
14              RIGHT-ROTATE(T,z.p.p)       // case 3
15      else (same as then clause
                with "right" and "left" exchanged)
16  T.root.color = BLACK

RB-INSERT-FIXUP이 작동하는 방법을 이해하기 위해, 우리는 코드에 대한 조사를 세 개의 중요한 단계들로 나눌 것이다. 처음에, 우리는 node z가 넣어지고, red로 색칠될 때 red-black properties의 무슨 violations이 RB-SERT에 도입되었는지를 결정할 것이다. 둘 쨰로, 우리는 lines 1-15에서 while loop의 전체 목적을 조사할 것이다. 마지막으로, 우리는 while loop의 body 안에서 세 가지 cases들 각각을 조사하고, 그것들이 그 목적을 어떻게 이루는지를 볼 것이다. 그림 13.4는 RB-INSERT-FIXUP이 sample red-black tree에서 작동하는 방법을 보여준다.

red-black properties의 어떤 것이 RB-INSERT-FIXUP의 호출동안 위반될지도 모르는가? Property 1은 확실히 계속해서 유지 된다. property 3도 그러한데, 그 새롭게 넣어진 red node의 두 자식들은 sentinel T.nil이기 때문이다. Property 5, black nodes의 개수가 주어진 노드에서 모든 simple path에서 갖다고 하는 것은, 또한 만족된다. 왜냐하면 node z는 그 (black) sentinel를 대체하기 떄문이고, 그 node z는 sentinel children을 가진 red이기 때문이다. 따라서, 위반될지도 모르는 유일한 properties는 propety 2이고, 이것은 root가 black이 되도록 요구하고, 그리고 property 4인데, 이것은 red node가 red child를 가질 수 없다는 것을 말한다. 두 가능한 위반은 red로 칠해지는 z 때문이다. Property 2는 만약 z가 root라면 위반되어지고, property 4는 만약 z의 parent가 red라면 위반된다. 그림 13.4 (a)는 node z가 넣어진 이후에 property 4의 위반을 보여준다.

lines 1-15에 있는 while loop는 loop의 각 iteration의 시작에서 다음의 세 부분의 invariant(불변자)를 유지하려 한다:

a. Node z는 red이다.

b. 만약 z.p가 root라면, 그러면 z.p는 black이다.

c. 만약 그 tree가 red-black properties의 어떤 것을 위반한다면, 그러면 그것은 많아봐야 최대로 그것들 중 한 개를 위반해야 하고, 그 위반은 property 2또는 property 4 둘 중 하나여야 한다. 만약 그 tree가 property 2를 위반한다면, 그것은 z가 root이고 red이기 때문이고, 만약 그 tree가 property 4를 위반한다면, 그것은 z와 z.p가 둘 다 red이기 때문이다.

Part(c), red-black properties의 violations을 다루는, 는 RB-INSERT-FIXUP이 parts(a)와 (b)보다 red-black properties를 복구하는 것을 보여주는데 더 중점적이다. 그리고 우리는 그 코드에서 상황을 이해하기 위해 그 방법을 따라 그것을 사용한다(?). 우리는 node z와 트리에서 그것에 가까이 있는 노드들에 집중할 것이기 때문에, part (a)에서 z가 red라는 것을 아는 것은 도움이 된다. 우리가 lines 2, 3, 7 , 8, 13 그리고 14에 있는 것을 참조할 때, node z.p.p가 존재하는 것을 보여주기 위해 part(b)를 사용할 것이다.

우리가 한 loop invariant가 그 loop의 first iteration 전에 true라는 것을 보여줄 필요가 있다는 것을 상기해라. 그리고 각 iteration이 그 loop invariant를 유지하고, 그 loop invariant는 윌에게 loop termination에 유용한 property를 준다는 것을 상기해라.

우리는initialization과 termination arguments로 시작한다. 그러고나서, 우리가 좀 더 상세히 loop의 body가 작동하는 방법을 조사할 때, 우리는 그 loop가 매 iteration마다 그 invariant를 유지한다고 주장할 것이다. 그 방법을 따라서, 우리는 또한 그 loop의 각 iteration이 가능한 두 가지 결과를 갖는다고 증명할 것이다 : 그 pointer z가 tree를 따라 올라가거나, 또는 우리는 rotations을 수행하고 그러고나서 그 loop를 종료시킨다.

Initialization: loop의 첫 번째 iteration전에, 우리는 violations이 없는 red-black tree로 시작했었고, 우리는 red node z를 추가했다. 우리는 invariant의 각 부분이 RB-INSERT-FIXUP이 호출되는 시간에 유효하다는 것을 보여준다:

a. RB-INSERT-FIXUP이 호출될 때, z는 추가되었던 red node이다.

b. 만약 z.p가 root라면, 그러면 z.p는 black으로 시작했었고, RB-INSERT-FIXUP 호출 전에 변경되지 않았다.

c. 우리는 RB-INSERT-FIXUP를 호출할 때, properties 1, 3, and 5가 유효하다는 것을 이미 보았다.

만약 그 tree가 property 2를 위반한다면, 그러면 그 red root는 새롭게 추가된 node z임에 틀림없고, tree에서 유일한 internal node이다. 왜냐하면 z의 부모와 자식 모두 black인 sentinel이기 때문에, 그 tree는 property 4를 위반하지 않는다. 따라서 property 2의 이 위반은 전체 트리에서 red-black properties의 유일한 위반이다.

만약 그 tree가 property 4를 위반한다면, 그러면 node z의 자식이 black sentinels이고, 그 tree가 추가된 z이전에 어떠한 다른 violations이 없었기 때문에, 그 위반은 z와 z.p가 둘 다 red이기 때문임에 틀림없다. 게다가, 그 tree는 어떠한 red-black properties도 위반하지 않는다.

Termination: 그 loop가 종료될 때, 그것은 z.p가 black이기 때문에 그렇다 (만약 z가 root라면, 그러면 z.p는 sentinel T.nil이고, 그 T.nil은 black이다.) 따라서, 그 tree는 loop termination에서 property 4를 위반하지 않는다. 그 loop invariant에 의해, 유효하는데 실패할지도 모르는 유일한 property는 property 2이다. Line 16은 이 property를 복구한다, RB-INSERT-FIXUP이 종료될 떄, 모든 red-balck properties가 유효하다.

Maintenance: 우리는 실제로 while loop에서 6개의 케이스들을 고려할 필요가 있지만, 그것들 중 세 개는 다른 세 개에 대해 대칭적이고, line 2가 z의 parent인 z.p가 z의 grandparent인 z.p.p의 left or right child인지를 결정하는 것에 따라 다르다. 우리는 z.p가 left child인 상황에 대해서만 코드를 주었다. loop invariant의 part(b)에 의해, node z.p.p는 존재하고, 만약 z.p가 root라면, 그러면 z.p는 black이다. 우리는 z.p가 red인 경우에만 loop iteration에 들어가기 때문에, 우리는 z.p가 root가 될 수 없다는 것을 안다. 그러므로, z.p.p는 존재한다.

우리는 z의 parent의 sibling, 즉 "uncle"의 색깔로 cases 2와 3을 case 1과 구분한다. Line 3은 y가 z의 uncle z.p.p.right를 가리키게 만들고, line 4는 y의 색을 테스트한다. 만약 y가 red라면, 그러면 우리는 case 1를 실행한다. 만약 그렇지 않다면, 제어는 cases 2와 3에 간다. 모든 세 개의 케이스들에서, z의 grandparent인 z.p.p는 black인데, 그것의 parent z.p가 red이기 때문이다. 그리고 property 4는 z와 z.p 사이에서만 위반된다.

Case 1 : z's uncle y is red

그림 13.5는 case 1 (lines 5-8)에 대한 상황을 보여준다. 이것은 z.p와 y 둘 다 red일 때 발생한다. 왜냐하면 z.p.p가 black이기 때문에, 우리는 z.p와 y를 둘 다 black으로 칠할 수 있고, 그것으로 z와 z.p가 둘 다 red가 되는 문제를 고치게 된다. 그리고 우리는 z.p.p를 red로 칠할 수 있고, 그것으로 인해 property 5가 유지된다. 우리느 ㄴ그러고나서 z.p.p를 새로운 node z로 while loop를 반복한다. 그 pointer z는 그 트리에서 두 단계 위로 올라간다.

$z' = z.p.p$ 를 사용하는데, 다음 iteration에서 line 1에서 테스트에서 node z라고 불려질 노드를 표기하기 위해서이다.

$z'$ 는 다음 iteration 시작시에 red이다.

$z'.p$ 가 이 iteration에서 z.p.p.p이고, 이 노드의 색이 바뀌지 않는다. 만약 이 노드가 root라면, 그것은 이 iteration전에 black이였었다. 그래서 그것은 다음 iteration 시작에 black으로 된다.

c. 우리는 case 1이 property 5를 유지한다고 이미 주장했다. 그리고 그것은 properties 1또는 3의 위반을 도입시키지 않는다.

$z'$ $z'$ $z'$ 에 의한 것이다.

$z'$ $z'$ $z'.p$ $z'.p$ $z'.p$ $z'$ $z'$ $z'.p$ 사이에 property 4의 위반을 생성했다.

Case 2: z's uncle y is black and z is a right child

Case 3: z's uncle y is black and z is a left child

cases 2와 3에서, z의 uncle y의 color는 black이다. 우리는 z가 z.p의 right or left child인지에 따라 두 케이스로 구분한다. Lines 10-11은 case 2를 구성하고, 그림 13.6에서 case 3과 함께 보여진다. case 2에서, node z는 그것의 부모의 right child이다. 우리는 즉시 그 상황을 case3로 바꾸기 위해 (lines 12-14) left rotation을 사용한다. 그 후에 node z는 left child이다. z와 z.p가 둘 다 red이기 때문에, 그 회전은 nodes의 black height에도 property 5에도 영향을 미치지 않는다. 우리가 직접적으로 case 3에 들어가거나 case 2를 통할 떄, z의 uncle y는 black이다. 만약 그렇지 않다면, 우리는 case 1를 실행할 것이기 때문이다. 추가적으로, 그 node z.p.p가 존재하는데, 우리는 이 노드가 lines 2와 3이 실행되는 시간에 존재한다고 주장하기 때문이다. 그리고 line 10에서 z를 올리고, 11에서 내린 후에, z.p.p의 identity는 바뀌지 않는다. case 3에서, 우리는 color changes와 right rotation을 실행하고, 이것은 property 5를 유지한다. 그러고나서, 우리는 더 이상 한 row에 두 개의 red nodes를 가지지 않기 때문에, 우리는 끝낸다. 그 while loop는 z.p가 이제 black이기 때문에 또 다시 iterate하지 않는다.

우리는 이제 cases 2와 3이 loop invariant라는 것을 보여준다 (우리가 주장했듯이, z.p가 line 1에서 다음 테스트 때 black일 것이고, 그 loop body는 다시 실행되지 않을 것이다.)

a. Caes 2는 z가 red인 z.p를 가리키게 한다. z에 대한 더 이상의 변화는 없고, 그것의 color는 cases 2와 3에서 발생한다.

b. Case 3은 z.p를 black으로 만든다. 만약 z.p가 다음 iteration의 시작에서 root라면, 그것은 black이다.

c. case 1에서 처럼, properties 1, 3, and 5는 cases 2와 3에서 유지된다.

node z가 cases 2와 3에서 root가 아니기 떄문에, 우리는 property 2의 어떠한 위반도 없다는 것을 안다. Cases 2와 3은 property 2의 위반을 도입하지 않는다. 왜냐하면 red로 만들어지는 유일한 노드가 case 3에서 rotation에 의해 black node의 child가 되기 떄문이다.

Cases 2와 3은 property 4의 단독 위반을 올바르게 하고, 그리고 또 다른 위반을 도입하지 않는다.

loop의 각 iteration이 invariant를 유지하는 것을 보여주어서, 우리는 RB-INSERT-FIXUP이 올바르게 그 red-black properties를 회복시키는 것을 보여주었다.

Analysis

$O(lg\;n)$ $O(lg\;n)$ time이 걸린다. RB-INSERT-FIXUP은 case 1이 발생하는 경우에만 whilewhile $O(lg\;n)$ $o(lg\;n)$ time이 걸린다. 게다가, 그것은 두 개 이상의 회전을 하지 않는다. 왜냐하면 만약 case 2 또는 case 3가 실행된다면 while loop가 종료되기 때문이다.

13.4 Deletion

$O(lg\;n)$ 이 걸린다. red-black tree에서 한 노드를 삭제하는 것은, 한 노드를 삽입하는 것보다 좀 더 복잡하다.

red-black tree에서 한 노드를 삭제하기 위한 procedure는 TREE-DELETE procedure를 기반으로 한다 (Section 12.3). 처음에, 우리는 TREE-DELETE가 호출하는 TRANSPLANT subroutine을 커스터마이즈 할 필요가 있는데, 그것이 red-black tree에 적용되기 위해서이다:


xxxxxxxxxx
RB-TRANSPLANT(T,u,v)
1   if u.p == T.nil
2       T.root = v
3   elseif u == u.p.left
4       u.p.left = v
5   else u.p.right = v
6   v.p = u.p

$v = T.nil$ 일 때, v.p에 할당하는 능력을 이용할 것이다.

그 procedure RB-DELETE는 TREE-DELETE procedure와 비슷하지만, 추가적인 라인들이 있다. 추가적인 lines들은 red-black properties의 위반을 만들지도 모르는 node y를 추적한다. 우리가 node z를 지우거나, z가 두 개가 안되는 자식을 가질 때, 그러고나서, z는 tree에서 제거되어지고, 그리고 y가 z가 되기를 원한다. z가 두 자식을 가질 떄, 그러면 y는 z의 successor이고, y는 tree에서 z의 위치로 이동한다. 우리는 또한 y가 제거되거나 트리 내에서 이동되어지기 전에, y의 color를 기억하고, 우리는 tree에서 y의 원래 위치로 움직이게 하는 node x를 추적한다. 왜냐하면 node x는 또한 red-black properties의 위반을 만들 지도 모르기 때문이다. node z를 지운 후에, RB-DELETE는 보조 procedure RB-DELTE-FIXUP를 호출하고, 이것은 red-black properties를 회복시키기 위해 colors를 바꾸고, 회전을 수행한다.


xxxxxxxxxx
RB-DELETE(T,z)
1   y = z
2   y-original-color = y.color
3   if z.left == T.nil
4       x = z.right
5       RB-TRANSPLANT(T,z,z.right)
6   elseif z.right == T.nil
7       x = z.left
8       RB-TRANSPLANT(T,z,z.left)
9   else y = TREE-MINIMUM(z.right)
10      y-original-color = y.color
11      x = y.right
12      if y.p == z
13          x.p = y
14      else RB-TRANSPLANT(T,y,y.right)
15          y.right = z.right
16          y.right.p = y
17      RB-TRANSPALNT(T,z,y)
18      y.left = z.left
19      y.left.p = y
20      y.color = z.color
21  if y-original-color == Black
22      RB-DELETE-FIXUP(T,x)

비록 RB-DELETE가 TREE-DELETE보다 두 배 더 많은 코드 라인을 포함할지라도, 그 두 procedure는 같은 기본 구조를 가진다. 너는 RB-DELETE 내에서 TREE-DELETE의 각 line을 찾을 수 있다 (NIL를 T.nil로 바꾸고, TRANSPLANT에 대한 호출을 RB-TRANSPLANT에 대한 호출로 바꾸는 변화와 함께), 그리고 같은 조건하에 실행이 된다.

여기에 그 두 procedures사이에 다른 차이들이 있다:

우리는 tree에서 제거되거나, tree내에서 이동될 node로서 node y를 유지한다. Line 1은 z가 두 개보다 더 작은 자식을 가지고, 그러므로 제거될 떄, node z를 가리키도록 설정된다. z가 두 자식을 가질 때, line 9는 TREE-DELETE에서 처럼, y가 z의 successor를 가리키도록 설정된다. 그리고 y는 tree에서 z의 위치로 이동할 것이다.
$y \neq z$ 이고, red-black tree에서 node y는 node z의 원래 위치로 이동한다; line 20은 y에게 z와 같은 컬러를 준다. 우리는 y의 original color를 저장할 필요가 있는데, RB-DELETE의 끝에 그것을 테스트하기 위해서이다; 만약 그것이 black이였었다면, 그러면 y를 제거하거나 옮기는 것은 red-black properties를 발생시킬 수 있다.
이야기 되었듯이, 우리는 node y의 original position으로 들어가는 node x를 추적한다. lines 4, 7, and 11에서의 할당은 x가 y의 자식만을 가리기커간, 만약 y가 자식이 없다면 sentinel T.nil를 가리키도록 설정한다 (Section 12.3에서 y가 어떠한 자식도 없는 것을 상기해라.)
node x가 node y의 원래 위치로 들어갔기 때문에, attribute x.p는 항상 y의 부모의 트리에서 원래 위치를 가리키도록 설정된다, 비록 x가 사실 sentinel T.nil일지라도. 만약 z가 y의 original parent가 아니라면, (z가 두 자식을 가지고 있고, 그것의 successor y가 z의 right child일 때만 발생하는), x.p에 대한 할당은 RB-TRANSPLANT의 line 6에서 발생한다. (RB-TRANSPLANT가 line 5, 8 or 14에서 호출되고, 두 번쨰 파라미터가 x와 같다는 것을 관찰해라.)
$x.p$ $x = T.nil$ 일 지라도.
마지막으로 만약 node y가 black이었다면, 우리는 red-black properties 한 개 이상의 violations을 넣을지도 모르고, 그래서 우리는 그 red-black properties를 회복하기 위해 line 22에서 RB-DELETE-FIXUP를 호출한다. 만약 y가 red였다면, red-black properties는 y가 제거되거나 이동될 때 여전히 유효하다 다음의 이유들 때문에:
1. tree에서 어떤 black-heights가 변하지 않았다.
2. 어떠한 red nodes들도 인접하게 만들어지지 않았다. y가 트리에서 z의 자리를 차지하기 떄문에, z의 color를 따라서, 우리는 tree에서 y의 새로운 위치에서 두 개의 인접한 red nodes를 가질 수 없다. 게다가, 만약 y가 z의 right child가 아니라면, 그러면 y의 원래 right child x는 tree에서 y를 대체한다. 만약 y가 red다면, 그러면 x는 black이고, 그래서 y를 x로 바꾸는 것은 두 개의 red nodes가 인접하게 할 수 없다.
3. y는 그것이 red였다면, root가 될 수 없기 때문에, root는 black으로 남아있는다.

만약 node y가 black이였었다면, RB-DELETE-FIXUP의 호출이 고칠 세 가지 문제가 발생하지도 모른다. 첫 째로, 만약 Y가 root였고, y의 red child가 새로운 root가 된다면, 우리는 property 2를 위반한다. 둘 쨰로, 만약 x와 x.p가 둘 다 red였다면, 그러면 우리는 property 4를 위반한다. 셋 째로, tree내에서 y를 움직이는 것은 y를 이전에 포함했던 어떤 simple path가 한 개 더 작은 black node를 갖게 만든다. 따라서, property 5가 이제 트리에서 y의 조상에 의해 위반된다. 우리는 이제 y의 original position을 차지하는 node x가 "extra" black를 가지도록 말하여 property 5의 위반을 고칠 수 있다. 즉, 만약 우리가 x를 포함하는 어떤 simple path에서 black nodes의 개수에 1를 추가한다면, 그러면 이 해석 하에, property 5는 유효하다. 우리가 black node y를 제거하거나 이동시킬 떄, 우리는 그것의 blackness를 node x에 "push"한다. 그 문제는 이제, node x가 red도 black도 아니고, 그것으로 인해 property 1를 위반한다. 대신에, node x는 "doubly black"이거나 "red-and-black" 둘 중 하나이다. 그리고 이것은 x를 포함하는 simple paths에서 black nodes의 개수에 각각 2 또는 1를 기여한다. x의 color attribute는 여전히 RED (만약 x가 red-and-black이라면) 또는 BLACK (만약 x가 doubly black이라면) 둘 중 하나일 것이다. 다시 말해서, 한 노드의 extra black은 color attribute에서 보다 오히려 x가 가리키는 노드에 반영된다.

우리는 이제 RB-DELETE-FIXUP procedure를 볼 수 있고, 그것이 search tree에 red-black properties를 어떻게 회복시키는지를 조사할 수 있다.


xxxxxxxxxx
RB-DELETE-FIXUP(T,x)
1   while x != T.root and x.color == BLACK
2       if x == x.p.left
3           w = x.p.right
4           if w.color == RED
5               w.color = BLACK                                     // case 1
6               x.p.color = RED                                     // case 1
7               LEFT-ROTATE(T,x.p)                                  // case 1
8               w = x.p.right                                       // case 1
9           if w.left.color == BLACK and w.right.color == BLACK
10              w.color = RED                                       // case 2
11              x = x.p                                             // case 2
12          else if w.right.color == BLACK
13                  w.left.color = BLACK                            // case 3
14                  w.color = RED                                   // case 3
15                  RIGHT-ROTATE(T,w)                               // case 3
16                  w = x.p.right                                   // case 3
17              w.color  = x.p.color                                // case 4
18              x.p.color = BLACK                                   // case 4
19              w.right.color = BLACK                               // case 4
20              LEFT-ROTATE(T,x.p)                                  // case 4
21              x = T.root                                          // case 4
22      else (same as then clause with "right" and "left" exchanged)
23  x.color = BLACK

그 procedure RB-DELETE-FIXUP은 properties 1, 2, and 4를 회복시킨다. Exercises 13.4-1과 13.4-2는 그 procedure가 properties 2와 4를 복구 시키는 것을 보여달라고 요청하고, 그래서 이 섹션의 나머지에서 우리는 property 1에 집중할 것이다. lines 1-22에 있는 while loop의 목적은 extra black를 tree위로 이동 시킬 것인데, 다음일 때 까지 한다

x가 red-and-black node를 가리키는데, 이 경우에, 우리는 x (단독으로) black으로 만든다 line 23에서;
x가 root를 가리키는데, 이 겨웅에, 우리는 간단히 그 extra black을 "remove" 한다; 또는
적절한 회전과 재색칠을 수행하고, 우리는 그 loop를 끝낸다.

while $x.p$ 의 left or right child인지를 결정한다 (우리는 x가 left child인 상황의 코드를 주었다; x가 right child인 상황은 - line 22 - 대칭적이다.) 우리는 x의 sibling인 w에 대한 포인터를 유지한다. node x는 doubly black이기 때문에, node w는 T.nil일 수 없다. 왜냐하면, 그렇지 않다면, x.p에서 leaf w (singly back)으로 가는 simple path에서의 blacks의 개수는 x.p에서 x로 가는 simple path에 있는 blacks의 개수보다 더 작기 때문이다.

$\alpha, \beta, \dots$ $\alpha$ $\beta$ $\gamma, \delta, \epsilon, \text{ and } \xi$ color $c$ $count(RED) = 0$ $count(BLACK) = 1$ $\alpha$ $2 + count(c)$ 이다. transformation 전후로. 이 경우에, 그 transformation 후에, 그 새로운 노드 x는 color attribute c를 가지지만, 이 노드는 실제로 red-and-black이거나 (만약 c = RED이라면) 또는 doubly black이다 (만약 c = BLACK이라면). 너는 다른 케이스들을 유사하게 입증할 수 있다. (Exercise 13.4-5 참조)

Case 1: x's sibling w is red

Case 1 (RB-DELETE-FIKXUP의 lines 5-8 그리고 그림 13.7(a))는 node w, node x의 형제인, 가 red일 때 발생한다. w는 black children을 가져야하기 때문에, 우리는 w와 x.p의 색을 바꿀 수 있고, 그러고나서 red-black properties의 어떠한 위반도 없이 x.p에 대해 left rotation을 수행할 수 있다. x의 새로운 sibling은, 회전 전에 w의 children중에 하나인, 이제 black이고, 따라서, 우리는 case 1을 case 2, 3, or 4로 바꾸었다.

Case 2, 3, 그리고 4는 node w가 black일 때 발생한다; 그것들은 w의 자식들의 colors들로 구분이된다.

Case 2: x의 sibling w는 black이고, w의 children 둘 다 black이다

case 2 (RB-DELETE-FIXUP의 lines 10-11 그리고 그림 13.7(b))에서, w의 자식들 모두 black이다. w가 또한 black이기 때문에, 우리는 x와 w 둘 다에게 black를 없애고, x가 오직 하나의 블랙을 가지게 하고, w는 red로 남겨둔다. x와 w로부터 한 black을 제거하는 것에 대해 보상하기 위해, 우리는 x.p에 extra black을 추가하고 싶다. 그리고 이것은 원래 red 또는 black 둘 중 하나이다. 우리는 x.p를 새로운 노드 x로서 while loop를 반복하여 그렇게 한다. 만약 우리가 case 1를 통해 case 2에 들어간다면, 그 새로운 node x는 red-and-black이라는 것을 관찰해라. 왜냐하며 ㄴ그 original x.p는 red이기 때문이다. 그러므로, 새로운 노드의 color attribute인 value c는 RED이고, 그 loop는 그 루프 조건을 테스트할 때 종료된다. 우리는 그러고나서 line 23에서 새로운 노드 x를 black으로 칠한다.

Case 3 : x'sibling w는 black이고, w의 left child는 red이고, w의 right child는 black이다

Case 3 (lines 13-16 그리고 그림 13.7(c))는 w가 black이고, 그것의 left childs느 red, 그리고 그것의 right child는 black일 때 발생한다. 우리는 w 그리고 그것의 왼쪽 자식 w.left의 색깔을 바꿀 수 있고, 그러고나서 red-black properties의 어떤 것도 위반하지 않고 w에 대해 right rotation을 수행한다. x의 새로운 sibling w는 이제 red right child를 가진 black node이고, 따라서 우리는 case 3를 case 4로 변환한다.

Case 4: x's sibling w는 black이고, w의 right child가 red이다

Case 4 (lines 17-21 and Figure 13.7(d))는 node x의 sibling w가 black이고, w의 right child가 red일 때 발생한다. 어떤 색을 바꾸고, x.p에 대해 left rotation을 수행하여, 우리는 x에서 extra black을 제거할 수 있고, 그것을 다시 singly black을 만들고, 어떠한 red-black properties를 위반하지 않는다. x를 root로 설정하는 것은 그것이 loop condition을 테스트할 때, 그 while loop를 종료시키게 한다.

Analysis

$O(lg\;n)$ $O(lg\;n)$ while $O(lg\;n)$ $o(lg\;n)$ $O(lg\;n)$ 이다.

chan blog

Post Lists

2020년 9월 16일 수요일