笔试算法题(51):简介 - 红黑树(RedBlack Tree)

红黑树(Red-Black Tree)

 

  • 红黑树是一种BST,但是每个节点上增加一个存储位表示该节点的颜色(R或者B);通过对任何一条从root到leaf的路径上节点着色方式的显示,红黑树确保所有路径的差值不会超过一倍,最终使得BST接近平衡;
  • 红黑树内每个节点包含五个属性:color, key, left, right和p,p表示指向父亲节点的指针;一棵BST需要同时满足下述五个性质才能称作红黑树:

    每个节点只能是红色或者黑色节点中的一种;

    根节点必须是黑色;

    每个叶节点(NULL)必须是黑色;

    如果一个节点是红色,则它的两个子节点必须是黑色;

    对于树中任何一个节点,该节点到其叶节点的所有路径上的黑色节点数相同

  • 红黑树的空间复杂度为O(N);支持三种操作:search, insert, delete,并且所有操作的时间复杂度都为O(logN),最好情况跟最坏情况的复杂度相同。对于search操作而言,其依赖BST的性质,所以不需 要依赖节点的着色信息;着色信息仅为了保证BST的平衡性,insert和delete操作则可能破坏BST的平衡性,所以这两种操作需要对红黑树中节点 的着色信息进行调整。
     
 1 //左旋操作中,oldroot的右子节点成为新的root,root的左子节点成为oldroot的右子节点,
 2 //oldroot成为新root的左子节点
 3    template <class KeyType>
 4    void Node<KeyType>::RotateLeft(Node<KeyType> * & root) {
 5       Node<KeyType> * oldRoot = root;
 6       root = root->mySubtree[RIGHT];
 7       oldRoot->mySubtree[RIGHT] = root->mySubtree[LEFT];
 8       root->mySubtree[LEFT] = oldRoot;
 9    }
10 
11 //右旋操作中,oldroot的左子节点成为新的root,root的右子节点成为oldroot的左子节点,
12 //oldroot成为新root的右子节点
13    template <class KeyType>
14    void Node<KeyType>::RotateRight(Node<KeyType> * & root) {
15       Node<KeyType> * oldRoot = root;
16       root = root->mySubtree[LEFT];
17       oldRoot->mySubtree[LEFT] = root->mySubtree[RIGHT];
18       root->mySubtree[RIGHT] = oldRoot;
19    }
20 
21 //向T索引的红黑树中插入新节点z,使用BST的性质查找z的插入位置,并且将新节点z标
22 //注为红色;
23 RB-INSERT(T, z)
24    y ← nil[T]
25    x ← root[T]
26    while x ≠ nil[T]
27       do y ← x
28       if key[z] < key[x]
29          then x ← left[x]
30          else x ← right[x]
31    p[z] ← y
32    if y = nil[T]
33       then root[T] ← z
34       else if key[z] < key[y]
35          then left[y] ← z
36          else right[y] ← z
37    left[z] ← nil[T]
38    right[z] ← nil[T]
39    color[z] ← RED
40    RB-INSERT-FIXUP(T, z)

 

插入一个节点并标注为红色的操作可能破坏红黑树的性质2和性质4;当插入节点为根节点的时候破坏性质2,此时直接将其变成黑色就可以恢复;当破坏性质4的时候则需要一系列的恢复操作;
case1:原树为空,新节点为根节点;恢复策略为将其改成黑色;
case2:新节点的父节点是黑色;满足所有红黑树规则;
case3:新节点的父节点是红色,父节点的兄弟节点是红色;恢复策略为将新节点的父节点和父节点的兄弟节点改成黑色,其祖父节点改成红色,针对祖父节点重新调用该方法;
case4:新节点的父节点是红色,父节点的兄弟节点是黑色,新节点为父节点的右子;恢复策略为以新节点的父节点为支点左旋;
case5:新节点的父节点是红色,父节点的兄弟节点是黑色,新节点为父节点的左子;恢复策略为将新节点的父节点改成黑色,祖父节点改成红色,并以祖父节点为支点右旋;

 1 RB-INSERT-FIXUP(T, z)
 2    while color[p[z] = RED
 3       do if p[z] = left[p[p[z]]
 4          then y ← right[p[p[z]]
 5             if color[y] = RED
 6                then color[p[z] ← BLACK                        ? Case 3
 7                   color[y] ← BLACK                                ? Case 3
 8                   color[p[p[z]] ← RED                           ? Case 3
 9                   z ← p[p[z]                                        ? Case 3
10                else if z = right[p[z]
11                   then z ← p[z]                                      ? Case 4
12                      LEFT-ROTATE(T, z)                            ? Case 4
13                   color[p[z] ← BLACK                             ? Case 5
14                   color[p[p[z]] ← RED                             ? Case 5
15                   RIGHT-ROTATE(T, p[p[z])                     ? Case 5
16          else (same as then clause with "right" and "left" exchanged)
17    color[root[T] ← BLACK
18 
19 //
20 RB-DELETE(T, z)
21    if left[z] = nil[T] or right[z] = nil[T]
22       then y ← z
23       else y ← TREE-SUCCESSOR(z)
24    if left[y] ≠ nil[T]
25       then x ← left[y]
26       else x ← right[y]
27    p[x] ← p[y]
28    if p[y] = nil[T]
29       then root[T] ← x
30       else if y = left[p[y]
31          then left[p[y] ← x
32          else right[p[y] ← x
33    if y 3≠ z
34       then key[z] ← key[y]
35          copy ys satellite data into z
36    if color[y] = BLACK
37       then RB-DELETE-FIXUP(T, x)
38    return y 

 

case1:x的兄弟w是红色
case2:x的兄弟w是黑色,并且w的两个孩子是黑色
case3:x的兄弟w是黑色,并且w的左孩子是红色,w的右孩子是黑色
case4:x的兄弟w是黑色,并且w的右孩子是红色

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

 

笔试算法题(51):简介 - 红黑树(RedBlack Tree),古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。