3-x 插播rb tree

agenda

1. 缘由

2. rb tree properties

3. rotation

3. insertion

4. deletion

缘由

之前看到stg-stl priority queue时觉得代码就是introduction to algorithms中大顶堆再工程化实现
关系型容器的一个基础是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 2lg(n+1)
prove:
first we use hypothesis show subtree rooted at any node x contains at least 2^{bh(x)} - 1 internal nodes.
basis hypothesis: if h(x) = 0, then x is leaf(NIL), the subtree contains 2^{bh(x)} - 1 = 2^0 - 1 = 0 nodes, basis holds.
inductive hypothesis: for node x, h(x) > 0 with 2 children.
from p#4 --> bh(x) = \begin{cases}bh(x_{parent}), c(x_{parent}) == BLACK \\bh(x_{parent}) - 1, c(x_{parent}) == RED\end{cases} (since x_{parent} is RED x must be BLACK, excluding x make make bh(x) less 1 than bh(x_{parent}))
by hypothesis we have number of internal nodes: counts(x) \ge 2^{bh(x)} - 1
\therefore counts(x_{parent}) = counts(x_l) + count(x_r) + 1 \ge 2^{bh(x_{parent}) -1} - 1 +2^{bh(x_{parent} )- 1} - 1 + 1 = 2^{bh(x_{parent})} - 1 which prove claims
\because according to p#4 a red node must least bring a black node on the way to the leaf
\therefore 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) \ge h(x)/2
\therefore counts(x) \ge 2^{bh(x)} - 1 \ge 2^{h/2} - 1, h \le 2lg(counts(x) + 1), 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 = z' is p(p(z)) is RED
b. if p(z') 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 z' is root, violation of p#2 only
  if z' is not root, z''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 p(z') 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))
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 220,063评论 6赞 510
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,805评论 3赞 396
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 166,403评论 0赞 357
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 59,110评论 1赞 295
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 68,130评论 6赞 395
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,877评论 1赞 308
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,533评论 3赞 420
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,429评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,947评论 1赞 319
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,078评论 3赞 340
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,204评论 1赞 352
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,894评论 5赞 347
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,546评论 3赞 331
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,086评论 0赞 23
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,195评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,519评论 3赞 375
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,198评论 2赞 357

推荐阅读更多精彩内容

  • 10. 平衡搜索树
    Goal: get a search tree data structure that we can insert...
    邢昱阅读 429评论 0赞 0
  • 13. Red-Black Trees 1
    DefinitionA red-black tree (RBT) is a binary search tree ...
    何大炮阅读 262评论 5赞 0
  • rljs
    rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,338评论 0赞 10
  • 红黑树
    红黑树 红黑树是一种特殊的二叉查找树（binary search tree，以下简称BST），它用来解决BST的致...
    山里没有经阅读 223评论 0赞 1
  • python-day3
    字符串 1.什么是字符串 使用单引号或者双引号括起来的字符集就是字符串。 引号中单独的符号、数字、字母等叫字符。 ...
    mango_2e17阅读 7,511评论 1赞 7