agenda

1. 緣由

2. rb tree properties

3. rotation

3. insertion

4. deletion

緣由

之前看到stg-stl priority queue時覺得代碼就是introduction to algorithms中大頂堆再工程化實現(xiàn)
關(guān)系型容器的一個基礎(chǔ)是rb tree, 有必要把它先弄清楚再看代碼, 這個插播系列也是給自己后面review提供一個索引

rb tree properties

properties:

A binary tree is a rb tree if it satisfies:

1. every node is either red or black
2. the root is black
3. every leaf (NIL) is black
4. if a node is red, then both it's children are black
5. for each node, all paths from the node to descendant leaves contain the same number of black nodes.

some symbol reference:

• it ref as p#[1-5], leaf and parent are all NIL which is black
• l(x) imply left child of x, r(x), p(x) in the same way
• c(x) = RED imply mark node x as RED
• NIL(T) refer sentinel of rb tree T, root(T) is the same way
• Case#1 ref code handle situation
• c#[1-15] ref code from line 1 to 15

black height

bh(x): black-height of the x is the number of black nodes on any path from a node x (but not including x) down to a leaf.
from p#5 black height is well defined, since it shares all leaf of the same count.

Lemma 13.1 a rb tree with n nodes has height at most
prove:
first we use hypothesis show subtree rooted at any node x contains at least internal nodes.
basis hypothesis: if h(x) = 0, then x is leaf(NIL), the subtree contains nodes, basis holds.
inductive hypothesis: for node x, h(x) > 0 with 2 children.
from p#4 --> (since is RED x must be BLACK, excluding x make make less 1 than )
by hypothesis we have number of internal nodes:
which prove claims
according to p#4 a red node must least bring a black node on the way to the leaf
at least half the nodes on any simple from the root to a leaf(not including the root) must be black. that is bh(x) h(x)/2
, that is we get upper bound of height with relation of lg(n)

rotations

a rotation operation preserves the binary search tree property: the keys in a precede key[x], key[y], and keys in r, as show in graph

void left_rotate(T, x){
  y = r(x); //buf y
  r(x) = l(y);//x's right -> β
  p(l(y)) = x; // β's parent -> x
  p(y) = p(x); // y's parent -> x's parent
  if (px(x) == NIL(T)): //x is root
    root(T) = y;
  else if (x == l(p(x))) // x is left child
    l(p(x)) = y;
  else
    r(p(x)) = y;
  l(y) = x;
  p(x) = y;
}
void right_rotate(T, y){
  x = l(y);// buf x
  l(y) = r(x);// y's left -> β
  p(r(x)) = y;// β's parent -> y
  p(x) = p(y);  x's parent -> y's parent
  if (p(y) == NIL(T)) // y is root
    root(T) = x;
  else if y == l(p(y)) // y is left child
    l(p(y)) = x;
  else
    r(p(y)) = x;
  r(x) = y;
  p(y) = x;
}

left_rotate <-> right_rotate are symmetric

insertion

insertion rb tree do as binary search tree then fix up fulfill rb tree properties.

code snap

void rb_insert(T, z){
  y = NIL(T);
  x = root(T);
  while (x != NIL(T)){ //find proper leaf position store in y
    y = x;
    if (k(z) < k(x))
      x = l(x);
    else
    x = r(x);
  }
  p(z) = y; // z's parent -> y
  if (y == NIL(T)) //not enter while loop, z is root
    root(T) = z;
  else if (k(z) < k(y))
    l(y) = z;
  else
    r(y) = z;
  }
  l(z) = r(z) = NIL(T);
  c(z) = RED;
  rb_insert_fixup(T, z);
}

the key point is rb_insert_fixup, we add new RED node at leaf position, codes as fellow:

void rb_insert_fixup(T, z){
 1  while(c(p(z)) == RED) {
 2    if (p(z) == l(p(p(x)))) {
 3      y = r(p(p(z))); 
 4      if (c(y) == RED){ //Case#1
 5        c(p(z)) = BLACK;
 6        c(y) = BLACK;
 7        c(p(p(z))) = RED;
 8        z = p(p(z));
 9     } else if (z == r(p(z))){ //Case#2
10      z = p(z);
11      left_rotate(T, z);
12    else { c(p(z)) = BLACK;//Case#3
13       c(p(p(z))) = RED;
14      right_rotate(T, p(p(z)));
15  else ... exchange `left` <-> `right` do line c#2-14
16  c(root(T)) = BLACK;  
}

correctness

FIRST we see by call of rb_insert, it results violates p#2,4

1. p#2 is break when z is root, c#16 fix it
2. p#4 is break when z and p(z) are both RED

for p#1,3,5 does not affect(since insert one is RED node)

SECOND we check loop invariant before rb_insert_fixup and at each case of start of iteration, c#1-15 maintains the fellowing three part loop invariant are:
a. z is RED
b. if p(z) is the root, p(z) is BLACK (imply p(z) is RED, p(p(x)) exists)
c. p#2,4 at most one violation.
loop invariant is true prior to the first iteration of the loop. each loop maintains the loop, it make legal rb tree at loop termination.

Initialization (prior call of rb_insert_fixup)
a. newly add z is RED
b. if p(z) is root, p(z) started out BLACK not change prior the call of rb_insert_fixup
c. p#1,3,5 hold when rb_insert_fixup is called
?1. if p#2 is not hold, z must be root, it's children are the sentinel, which is BLACK, not a violation of p#4
?2. if p#4 is not hold, z & p(z) are RED, the tree had no other violations prior to z, hence not violation of p#2
thus p#2 & p#4 at most one violation.

Termination (loop finish)
when loop terminates, p(z) is BLACK, no violation of p#4, p#2 is fixed by c#16, when rb_insert_fixup terminates all rb tree properties hold.

Maintains (each case)
there are 6 cases of cases, 3 of then are symmetric (depend on p(z) is left or right of p(p(z)))
from c#2 check p(z) == RED because b of loop invariant, p(z) can not be root, that's p(p(z)) is exists, otherwise (p(z) == BLACK) loop terminates

Case#1
distinguish from Case2,3 by uncle's color
In Case#1 p(z), y, z are RED, p(p(z)) is BLACK, making c(y) = c(p(z)) = BLACK, p(p(z)) = RED maintains p#5 then repeat z = p(p(z)) move up 2 levels.
as shows:

loop invariant
a. after loop, new z = is p(p(z)) is RED
b. if is root, and it not affected in this loop, remain BLACK at the next iteration
c. Case#1 maintain p#5, not introduce p#1,3
? if is root, violation of p#2 only
? if is not root, 's color is not related with p#2, we color p(z) and y to BLACK to fix z and p(z) both RED thereby maintain p#5
? if is BLACK rb tree properties hold, otherwise introduce violation of p#4 only and loop continue

Case2,3
In Case2,3, y is BLACK, then check z is left/right of p(z)'s child, if z == r(p(z)) calling left_rotate transform from Case#2 to Case#3, else enter directly into Case#3
In Case2,3, because both z and p(z) are RED, the rotation affects neither the black height of nodes nor p#5 when y is BLACK
? in Case#2, c#10 move up one level and down one level in c#11 the identity of p(p(z)) remain unchanged.
? in Case#3, color change and right rotation preserve p#5, no longer have 2 RED in one row, p(z) is BLACK loop terminates.

loop invariant
a. Case#2 while loop finish z now points previous p(z)(in graph node A) which is RED, no further change z and it's color
b. Case#3 make p(z) to BLACK, if p(z) is root, at next start of iteration, it's BLACK
c. p#1,3,5 are maintained in Case#2,3
? z is not root in Case#2,3, no way of violation p#2, only paint RED in Case#3 becomes child of BLACK node no way of violation p#4
? Case#2 -> Case#3 which only violation of p#4 without another violation

Analysis

rb_insert running time is O(lg(n))
rb_insert_fixup running time is O(lg(n))
? Case#1 is executed, z moves up 2 levels up
? Case#2 -> Case#3 -> finish
? Case#3 -> finish

deletion

code snap

 1  void rb_delete(T, z) {
 2    y = (l(z) == NIL(T) or r(z) == NIL(T)) ? z : tree_successor(z);
 3    x =  (l(y) != NIL(T)) ? l(y) : r(y);
 4    if (p(y) == NIL(T))
 5      ROOT(T) = x;
 6    else if y == l(p(y))
 7       l(p(y)) = x;
 8    else
 9      r(p(y)) = x;
10    if (y != z)
11      k(z) = k(y);
12      //cp y's data into z
13    if (c(y) == BLACK)
14      rb_delete_fixup(T, x);
15    return y;
16  }

 1  void rb_delete_fixup(T, x) {
 2    while ( x != ROOT(t) and c(x) == BLACK){
 3      if (x == l(p(x)) {
 4        w = r(p(x));
 5        if (c(w) == RED) { //Case#1
 6          c(w) = BLACK;
 7          c(p(w)) = RED;
 8          left_rotate(T, p(x));
 9          w = r(p(x));
10        }
11        if (c(l(w) == BLACK and c(r(w)) == BLKACK){ //Case#2
12          c(w) = RED;
13          x = p(x);
14        }
15        else if (c(r(w)) == BLACK) { Case#3
16          c(l(w)) = BLACK;
17          c(w) = RED;
18          right_rotate(T, w);
19          w = r(p(x));
20        }
21        else {
22          c(w) = c(p(x));
23          c(p(x)) = BLACK;
24          c(r(w)) = BLACK;
25          left_rorate(T, p(x));
26          x = ROOT(T);
27        }
28    else // "right" <-> "left" do c#3-27
29    c(x) = BLACK;
30  }

correctness

in rb_delete:

• y is target delete note
• x is child of y which may break rb tree properties because deleting it's parent y

rb_delete intents splice y by x, there 3 cases:

1. y is leaf node, delete it directly
2. y has on child, splice y with it's child x
3. y has two children, delete position of it's successor, copy key & data into y 's position.
   
   leaf
   
   
   one child
   
   
   two children

if spliced node y is RED, the rb properties still hold:

• no black-heights in the tree have changed.
• no red nodes have been made adjacent.
• y is not root, root's color remain.

if spliced node y is BLACK, he rb propeties broken as:

• y is root, x became new root, violation of p#2
• if p(y) and x are RED, splice y violates p#4
• remove BLACK y cause p#5, we set node point by x either double-black (when color is BLACK, black count is 2) or red-black (when color is RED, black count is 1), in that way p#5 still hold, p#1 is broken.

rb_delete_fixup restores p#1,2,4, maintain p#5
while loop move the extra black until:

1. x points to red-black node, set black @ c#29
2. x points to root, set black @ c#29
3. suitable rotations and recoloring can be performaced

there are 4 cases depends on x 's is root and color

1. if x is new root original is RED/BLACK, if x is not root and original RED: since y is BLACK, c#29 ensure p#1,2,4, remove y BLACK then adding new BLACK p#5 preserves
2. if x is not root and original BLACK, there are another 4 cases, c#29 ensure no violation of p#1,2, since x is BLACK, in while loop c#2-28 x start points double-black node maintain p#5

Case#1

1. after remove back node of y, count(A) = 2 makes p#5 still holds.
2. subtree α, β, r, g, ε, ξ 's black height is not change before and after transformation.
3. after transformation, w's color change to BLACK, then transfer to Case#[2-4]
4. since w is RED, l(w) & r(w) must exists and BLACK for p#5 holds before transformation

Case#2

both l(w) & r(w) are BLACK

1. w must be BLACK, otherwise Case#1 is executed first.
   2.before transformation: x points to double-black count(A) = 2, after transformation: x points either double-black or red-black node, count(A) decrease 1 then count(B) increase 1 letting bh(α) = bh(B) + 2 not changed, in the same way r, g, ε, ξ bh is not change(count(D) decrease 1 then count(B) increase 1) -> p#5 preserve.
2. if B is RED making D RED exit while loop , c#29 making B BLACK p#4 preserve, if B is BLACK loop continue p#4 holds(transform from Case#1)

Case#3

w is BLACK, r(w) is BLACK, l(w) i RED

1. bh of α, β, r, g, ε, ξ is not changed p#4 holds
2. since l(w) is RED, c(g) must be BLACK, making C(D) = RED no violation of ##p#4##
3. after ##Case#3## c(r(w)) is RED then transfer to ##Case#4##

Case#4

c(D) is BLACK, c(C) & c(E) is RED

1. since set x as root then set BLACK, count(A) from 2 to 1, then adding new BLACK B, bh is maintained
2. α, β, r, g, ε, ξ is not changed, ##p#5## is maintained
3. make x as root loop terminate, c#29 preserve ##p#1,2##

Analysis

1. rb_delete_fixup ##Case#1,3,4## operations of constant time
   2.Case#2 move up by 1 level, and continue when p(x) is RED at most execute lg(n) times.
2. tree_successor running time is O(lg(n)), overall rb_delete running time is O(lg(n))