精华内容
下载资源
问答
  • 红黑树插入,删除时各种状态的平衡操作
  • 红黑树删除操作

    千次阅读 2014-04-17 21:35:19
     算法导论书上给出的红黑树的性质如下,跟STL源码剖析书上面的4条性质大同小异。  1、每个结点或是红色的,或是黑色的  2、根节点是黑色的  3、每个叶结点(NIL)是黑色的  4、如果一个节点是红
    转载请标明出处,原文地址:http://blog.csdn.net/hackbuteer1/article/details/7760584
          算法导论书上给出的红黑树的性质如下,跟STL源码剖析书上面的4条性质大同小异。
          1、每个结点或是红色的,或是黑色的
          2、根节点是黑色的
          3、每个叶结点(NIL)是黑色的
          4、如果一个节点是红色的,则它的两个儿子都是黑色的。
          5、对于每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑色结点。

          从红黑树上删除一个节点,可以先用普通二叉搜索树的方法,将节点从红黑树上删除掉,然后再将被破坏的红黑性质进行恢复。
          我们回忆一下普通二叉树的节点删除方法:Z指向需要删除的节点,Y指向实质结构上被删除的结点,如果Z节点只有一个子节点或没有子节点,那么Y就是指向Z指向的节点。如果Z节点有两个子节点,那么Y指向Z节点的后继节点(其实前趋也是一样的),而Z的后继节点绝对不可能有左子树。因此,
    仅从结构来看,二叉树上实质被删除的节点最多只可能有一个子树
    现在我们来看红黑性质的恢复过程:
          如果Y指向的节点是个红色节点,那么直接删除掉Y以后,红黑性质不会被破坏。操作结束。
          如果Y指向的节点是个黑色节点,那么就有几条红黑性质可能受到破坏了。首先是包含Y节点的所有路径,黑高度都减少了一(第5条被破坏)。其次,如果Y的有红色子节点,Y又有红色的父节点,那么Y被删除后,就出现了两个相邻的红色节点(第4条被破坏)。最后,如果Y指向的是根节点,而Y的子节点又是红色的,那么Y被删除后,根节点就变成红色的了(第2条被破坏)。
          其中,第5条被破坏是让我们比较难受的。因为这影响到了全局。这样动作就太大太复杂了。而且在这个条件下,进行其它红黑性质的恢复也很困难。所以我们首先解决这个问题:如果不改变含Y路径的黑高度,那么树的其它部分的黑高度就必须做出相应的变化来适应它。所以,我们想办法恢复原来含Y节点的路径的黑高度。做法就是:无条件的把Y节点的黑色,推到它的子节点X上去。(X可能是NIL节点)。这样,X就可能具有双重黑色,或同时具有红黑两色,也就是第1条性质被破坏了。
          但第1条性质是比较容易恢复的:一、如果X是同时具有红黑两色,那么好办,直接把X涂成黑色,就行了。而且这样把所有问题都解决了。因为将X变为黑色,2、4两条如果有问题的话也会得到恢复,算法结束。二、如果X是双黑色,那么我们希望把这种情况向上推一直推到根节点(调整树结构和颜色,X的指向新的双黑色节点,X不断向上移动),让根节点具双黑色,这时,直接把X的一层黑色去掉就行了(因为根节点被包含在所有的路径上,所以这样做所有路径同时黑高减少一,不会破坏红黑特征)。
          下面就具体地分析如何恢复1、2、4三个可能被破坏的红黑特性:我们知道,如果X指向的节点是有红黑两色,或是X是根节点时,只需要简单的对X进行一些改变就行了。要对除X节点外的其它节点进行操作时,必定是这样的情况:X节点是双层黑色,且X有父节点P。由知可知,X必然有兄弟节点W,而且这个W节点必定有两个子节点。(因为这是原树满足红黑条件要求而自然具备的。X为双黑色,那么P的另一个子节点以下一定要有至少两层的节点,否则黑色高度不可能和X路径一致)。所以我们就分析这些节点之间如何变形,把问题限制在比较小的范围内解决。另一个前提是:X在一开始,肯定是树底的叶节点或是NIL节点,所以在递归向上的过程中,每一步都保证下一步进行时,至少 X的子树是满足红黑特性的。因此子树的情况就可以认为是已经正确的了,这样,分析就只限制在X节点,X的父节点P和X的兄弟节点W,以及W的两个子节点中。
          下面仅仅考虑X原本是黑色的情况即可。
          在这种情况下,X此时应该具有双重黑色,算法的过程就是将这多出的一重黑色向上移动,直到遇到红节点或者根节点。
          接着往下分析, 会遇到4种情况,实际上是8种, 因为其中4种是相互对称的,这可以通过判断X是其父节点的右孩子还是左孩子来区分。下面我们以X是其父节点的左孩子的情况来分析这4种情况,实际上接下来的调整过程,就是要想方设法将经过X的所有路径上的黑色节点个数增加1。
          具体分为以下四种情况:(下面针对x是左儿子的情况讨论,右儿子对称)
          Case1:X的兄弟W是红色(想办法将其变为黑色)
           由于W是红色的,因此其儿子节点和父节点必为黑色,只要将W和其父节点的颜色对换,在对
    父节点进行一次左旋转,便将W的左子节点放到了X的兄弟节点上,X的兄弟节点变成了黑色,且红黑性质不变。但还不算完,只是暂时将情况1转变成了下面的情况2或3或4。

        Case2:X的兄弟节点W是黑色的,而且W的两个子节点都是黑色的。此时可以将X的一重黑色和W的黑色同时去掉,而转加给他们的父节点上,这是X就指向它的父节点了,因此此时父节点具有双重颜色了。这一重黑色节点上移。

          如果父节点原来是红色的,现在又加一层黑色,那么X现在指向的这个节点就是红黑两色的,直接把X(也就是父节点)着为黑色。问题就已经完整解决了。
         如果父节点现在是双层黑色,那就以父节点为新的X进行向上的下一次的递归。

        Case3:X的兄弟节点W是黑色的,而且W的左子节点是红色的,右子节点是黑色的。此时通过交换W和其左子节点的颜色并进行一次向右旋转就可转换成下面的第四种情况。注意,原来L是红色的,所以L的子节点一定是黑色的,所以旋转中L节点的一个子树挂到之后着为红色的W节点上不会破坏红黑性质。变形后黑色高度不变。

        Case4: X的兄弟节点W是黑色的,而且W的右子节点是红色的。这种情况下,做一次左旋,W就处于根的位置,将W保持为原来的根的位置的颜色,同时将W的两个新的儿子节点的颜色变为黑色,去掉X的一重黑色。这样 整个问题也就得到了解决。递归结束。(在代码上,为了标识递归结束,我们把X指向根节点)

          因此,只要按上面四种情况一直递归处理下去,X最终总会指向根结点或一个红色结点,这时我们就可以结束递归并把问题解决了。
          以上就是红黑树的节点删除全过程。
          总结:
          如果我们通过上面的情况画出所有的分支图,我们可以得出如下结论
          插入操作:解决的是 红-红 问题
          删除操作:解决的是 黑-黑 问题

          即你可以从分支图中看出,需要往上遍历的情况为红红(插入),或者为黑黑黑(删除)的情况,如果你认真分析并总结所有的情况后,并坚持下来,红黑树也就没有想象中的那么恐怖了,并且很美妙;
          详细的红黑树删除节点的代码如下:
    [cpp]  view plain copy
    1. #include<iostream>  
    2. using namespace std;  
    3.   
    4. // 定义节点颜色    
    5. enum COLOR  
    6. {    
    7.     BLACK = 0,    
    8.     RED    
    9. };    
    10.     
    11. // 红黑树节点    
    12. typedef struct RB_Tree_Node  
    13. {    
    14.     int key;    
    15.     struct RB_Tree_Node *left;    
    16.     struct RB_Tree_Node *right;    
    17.     struct RB_Tree_Node *parent;    
    18.     unsigned char RB_COLOR;    
    19. }RB_Node;  
    20.   
    21. // 红黑树,包含一个指向根节点的指针    
    22. typedef struct RBTree  
    23. {    
    24.     RB_Node* root;  
    25. }*RB_Tree;  
    26.   
    27. // 红黑树的NIL节点    
    28. static RB_Tree_Node NIL = {0, 0, 0, 0, BLACK};   
    29.   
    30. #define PNIL (&NIL)   // NIL节点地址   
    31.   
    32. void Init_RBTree(RB_Tree pTree) // 初始化一棵红黑树    
    33. {    
    34.     pTree->root = PNIL;    
    35. }     
    36.   
    37. // 查找最小键值节点    
    38. RB_Node* RBTREE_MIN(RB_Node* pRoot)    
    39. {    
    40.     while (PNIL != pRoot->left)  
    41.     {  
    42.         pRoot = pRoot->left;  
    43.     }    
    44.     return pRoot;  
    45. }  
    46.   
    47.   
    48. /* 
    49.                           15 
    50.                         /    \ 
    51.                        /      \ 
    52.                       /        \ 
    53.                      6          18 
    54.                     /  \       /  \ 
    55.                    /    \     /    \ 
    56.                   3      7   17    20 
    57.                  /  \     \ 
    58.                 /    \     \ 
    59.                2      4     13 
    60.                             / 
    61.                            / 
    62.                           9 
    63. */  
    64. // 查找指定节点的后继节点    
    65. RB_Node* RBTREE_SUCCESSOR(RB_Node*  pRoot)    
    66. {    
    67.     if (PNIL != pRoot->right)    // 查找图中6的后继节点时就调用RBTREE_MIN函数  
    68.     {    
    69.         return RBTREE_MIN(pRoot->right);    
    70.     }  
    71.     // 节点没有右子树的时候,进入下面的while循环(如查找图中13的后继节点时,它的后继节点是15)  
    72.     RB_Node* pParent = pRoot->parent;    
    73.     while((PNIL != pParent) && (pRoot == pParent->right))  
    74.     {    
    75.         pRoot = pParent;  
    76.         pParent = pRoot->parent;        
    77.     }  
    78.     return pParent;  
    79. }  
    80.   
    81. // 红黑树的节点删除  
    82. RB_Node* Delete(RB_Tree pTree , RB_Node* pDel)    
    83. {    
    84.     RB_Node* rel_delete_point;  
    85.     if(pDel->left == PNIL || pDel->right == PNIL)  
    86.         rel_delete_point = pDel;  
    87.     else  
    88.         rel_delete_point = RBTREE_SUCCESSOR(pDel);     // 查找后继节点  
    89.   
    90.     RB_Node* delete_point_child;    
    91.     if(rel_delete_point->right != PNIL)    
    92.     {    
    93.         delete_point_child = rel_delete_point->right;    
    94.     }    
    95.     else if(rel_delete_point->left != PNIL)    
    96.     {    
    97.         delete_point_child = rel_delete_point->left;    
    98.     }    
    99.     else    
    100.     {    
    101.         delete_point_child = PNIL;    
    102.     }    
    103.     delete_point_child->parent = rel_delete_point->parent;    
    104.     if(rel_delete_point->parent == PNIL)    // 删除的节点是根节点  
    105.     {    
    106.         pTree->root = delete_point_child;  
    107.     }    
    108.     else if(rel_delete_point == rel_delete_point->parent->right)  
    109.     {    
    110.         rel_delete_point->parent->right = delete_point_child;    
    111.     }    
    112.     else    
    113.     {    
    114.         rel_delete_point->parent->left = delete_point_child;    
    115.     }  
    116.     if(pDel != rel_delete_point)  
    117.     {  
    118.         pDel->key = rel_delete_point->key;  
    119.     }  
    120.     if(rel_delete_point->RB_COLOR == BLACK)    
    121.     {    
    122.         DeleteFixUp(pTree , delete_point_child);    
    123.     }  
    124.     return rel_delete_point;    
    125. }    
    126.                
    127.   
    128. /* 
    129. 算法导论上的描述如下: 
    130. RB-DELETE-FIXUP(T, x)  
    131. 1 while x ≠ root[T] and color[x] = BLACK  
    132. 2     do if x = left[p[x]]  
    133. 3           then w ← right[p[x]]  
    134. 4                if color[w] = RED  
    135. 5                   then color[w] ← BLACK                           Case 1  
    136. 6                        color[p[x]] ← RED                          Case 1  
    137. 7                        LEFT-ROTATE(T, p[x])                       Case 1  
    138. 8                        w ← right[p[x]]                            Case 1  
    139. 9                if color[left[w]] = BLACK and color[right[w]] = BLACK  
    140. 10                   then color[w] ← RED                            Case 2  
    141. 11                        x p[x]                                    Case 2  
    142. 12                   else if color[right[w]] = BLACK  
    143. 13                           then color[left[w]] ← BLACK            Case 3  
    144. 14                                color[w] ← RED                    Case 3  
    145. 15                                RIGHT-ROTATE(T, w)                Case 3  
    146. 16                                w ← right[p[x]]                   Case 3  
    147. 17                         color[w] ← color[p[x]]                   Case 4  
    148. 18                         color[p[x]] ← BLACK                      Case 4  
    149. 19                         color[right[w]] ← BLACK                  Case 4  
    150. 20                         LEFT-ROTATE(T, p[x])                     Case 4  
    151. 21                         x ← root[T]                              Case 4  
    152. 22        else (same as then clause with "right" and "left" exchanged)  
    153. 23 color[x] ← BLACK   
    154. */    
    155. //接下来的工作,很简单,即把上述伪代码改写成c++代码即可    
    156. void DeleteFixUp(RB_Tree pTree , RB_Node* node)    
    157. {    
    158.     while(node != pTree->root && node->RB_COLOR == BLACK)    
    159.     {    
    160.         if(node == node->parent->left)    
    161.         {    
    162.             RB_Node* brother = node->parent->right;    
    163.             if(brother->RB_COLOR==RED)   //情况1:x的兄弟w是红色的。    
    164.             {    
    165.                 brother->RB_COLOR = BLACK;    
    166.                 node->parent->RB_COLOR = RED;    
    167.                 RotateLeft(node->parent);    
    168.             }    
    169.             else     //情况2:x的兄弟w是黑色的,    
    170.             {    
    171.                 if(brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK)  //w的两个孩子都是黑色的    
    172.                 {    
    173.                     brother->RB_COLOR = RED;    
    174.                     node = node->parent;    
    175.                 }    
    176.                 else  
    177.                 {  
    178.                     if(brother->right->RB_COLOR == BLACK)   //情况3:x的兄弟w是黑色的,w的右孩子是黑色(w的左孩子是红色)。    
    179.                     {  
    180.                         brother->RB_COLOR = RED;  
    181.                         brother->left->RB_COLOR = BLACK;  
    182.                         RotateRight(brother);  
    183.                         brother = node->parent->right;      //情况3转换为情况4  
    184.                     }  
    185.                     //情况4:x的兄弟w是黑色的,且w的右孩子时红色的  
    186.                     brother->RB_COLOR = node->parent->RB_COLOR;    
    187.                     node->parent->RB_COLOR = BLACK;    
    188.                     brother->right->RB_COLOR = BLACK;    
    189.                     RotateLeft(node->parent);    
    190.                     node = pTree->root;  
    191.                 }//else  
    192.             }//else  
    193.         }    
    194.         else   //同上,原理一致,只是遇到左旋改为右旋,遇到右旋改为左旋即可。其它代码不变。    
    195.         {    
    196.             RB_Node* brother = node->parent->left;    
    197.             if(brother->RB_COLOR == RED)    
    198.             {    
    199.                 brother->RB_COLOR = BLACK;    
    200.                 node->parent->RB_COLOR = RED;    
    201.                 RotateRight(node->parent);    
    202.             }    
    203.             else    
    204.             {    
    205.                 if(brother->left->RB_COLOR==BLACK && brother->right->RB_COLOR == BLACK)    
    206.                 {    
    207.                     brother->RB_COLOR = RED;    
    208.                     node = node->parent;    
    209.                 }    
    210.                 else  
    211.                 {  
    212.                     if(brother->left->RB_COLOR==BLACK)    
    213.                     {    
    214.                         brother->RB_COLOR = RED;    
    215.                         brother->right->RB_COLOR = BLACK;    
    216.                         RotateLeft(brother);  
    217.                         brother = node->parent->left;      //情况3转换为情况4  
    218.                     }  
    219.                     brother->RB_COLOR = node->parent->RB_COLOR;    
    220.                     node->parent->RB_COLOR = BLACK;    
    221.                     brother->left->RB_COLOR = BLACK;    
    222.                     RotateRight(node->parent);    
    223.                     node = pTree->root;    
    224.                 }    
    225.             }    
    226.         }    
    227.     }//while   
    228.     node->RB_COLOR = BLACK;    //如果X节点原来为红色,那么直接改为黑色    
    229. }  
    展开全文
  • 红黑树删除操作

    千次阅读 2019-06-16 11:52:39
    删除红黑树中一个结点,删除的结点是其子结点状态和颜色的组合。子结点的状态有三种:无子结点、只有一个子结点、有两个子结点。颜色有红色和黑色两种。所以共会有6种组合。 组合1:被删结点无子结点,且被删结点为...

    原文:https://segmentfault.com/a/1190000012115424

     

    可能出现的情形讨论

    删除红黑树中一个结点,删除的结点是其子结点状态和颜色的组合。子结点的状态有三种:无子结点、只有一个子结点、有两个子结点。颜色有红色和黑色两种。所以共会有6种组合。

    组合1:被删结点无子结点,且被删结点为红色

    此时直接将结点删除即可,不破坏任何红黑树的性质。

    组合2:被删结点无子结点,且被删结点为黑色

    处理方法略微复杂,稍后再议。

    组合3:被删结点有一个子结点,且被删结点为红色

    这种组合是不存在的,如图假如被删结点node只有一个有值的子结点value,而以value为根结点的子树中,必然还存在null结点,如此不符合红黑树的性质5,对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。

    组合4:被删结点有一个子结点,且被删结点为黑色

    这种组合下,被删结点node的另一个子结点value必然为红色,此时直接将node删掉,用value代替node的位置,并将value着黑即可。

    组合5&6:被删结点有两个子结点,且被删结点为黑色或红色

    当被删结点node有两个子结点时,先要找到这个被删结点的后继结点successor,然后用successor代替node的位置,同时着成node的颜色,此时相当于successor被删。

    因为node有两个子结点,所以successor必然在node的右子树中,必然是下图两种形态中的一种。

    若是(a)的情形,用successor代替node后,相当于successor被删,若successor为红色,则变成了组合1;若successor为黑色,则变成了组合2。

    若是(b)的情形,用successor代替node后,相当于successor被删,若successor为红色,则变成了组合1;若successor为黑色,则变成了组合2或4。

    综上

    若被删结点是组合1或组合4的状态,很容易处理;被删结点不可能是组合3的状态;被删结点是组合5&6的状态,将变成组合1或组合2或组合4。

    再议组合2:被删结点无子结点,且被删结点为黑色

    因为删除黑色结点会破坏红黑树的性质5,所以为了不破坏性质5,在替代结点上额外增加一个黑色,这样不违背性质5而只违背性质1,每个结点或是黑色或是红色。此时将额外的黑色移除,则完成删除操作。

    然后再结合node原来的父结点father和其兄弟结点brother来分析。

    情形一

    brother为黑色,且brother有一个与其方向一致的红色子结点son,所谓方向一致,是指brother为father的左子结点,son也为brother的左子结点;或者brother为father的右子结点,son也为brother的右子结点。

    图(c)中,白色代表随便是黑或是红,方形结点除了存储自身黑色外,还额外存储一个黑色。将brother和father旋转,并重新上色后,变成了图(d),方形结点额外存储的黑色转移到了father,且不违背任何红黑树的性质,删除操作完成。

    图(c)中的情形颠倒过来,也是一样的操作。

    情形二

    brother为黑色,且brother有一个与其方向不一致的红色子结点son

    图(e)中,将son和brother旋转,重新上色后,变成了图(f),情形一。

    图(e)中的情形颠倒过来,也是一样的操作。

    情形三

    brother为黑色,且brother无红色子结点

    此时若father为红,则重新着色即可,删除操作完成。如图下图(g)和(h)。

    此时若father为黑,则重新着色,将额外的黑色存到father,将father作为新的结点进行情形判断(不删除),遇到情形一、情形二,则进行相应的调整,完成删除操作;如果没有,则结点一直上移,直到根结点存储额外的黑色,此时将该额外的黑色移除,即完成了删除操作。

    情形四

    brother为红色,则father必为黑色。

    图(i)中,将brother和father旋转,重新上色后,变成了图(j),新的brother变成了黑色,这样就成了情形一、二、三中的一种。如果将son和brother旋转,无论怎么重新上色,都会破坏红黑树的性质4或5,例如图(k)。
    图(i)中的情形颠倒过来,也是一样的操作。

     

    展开全文
  • 红黑树 删除

    2014-07-30 10:46:11
    红黑树是一种特殊的二叉查找树,其删除结点首先要按二叉查找树删除结点的算法进行 一、普通二叉查找树删除一个结点: (1)待删除结点没有子结点,即它是一个叶子结点,此时直接删除 (2)待删除结点只有一个子...

    红黑树是一种特殊的二叉查找树,其删除结点首先要按二叉查找树删除结点的算法进行

    一、普通二叉查找树删除一个结点:

    (1)待删除结点没有子结点,即它是一个叶子结点,此时直接删除

    (2)待删除结点只有一个子结点,则可以直接删除;如果待删除结点是根结点,则它的子结点变为根结点;如果待删除结点不是根结点,则用它的子结点替代它的位置。

    (3)待删除结点有两个子结点,首先找出该结点的后继结点(即右子树中数值最小的那个结点),然后将两个结点进行值交换(即:只交换两个结点的数值,不改变结点的颜色),此时待删除节点变为后继结点,删除后继结点结。由于后继结点不可能有左子结点,对调后的待删除结点也不会有左子结点,因此要把它删除的操作会落入情况(1)或情况(2)中。

    二、.红黑树的删除结点算法

      1.  待删除结点有一个外部结点,操作为: 
        该节点是黑色,其非空子节点为红色 ;则将其子节点提升到该结点位置,颜色变黑

      2.待删除结点有两个外部结点,操作如下:

        (1)若该结点是红色,则可直接删除,不影响红黑树的性质,算法结束

        (2)若该结点是黑色,则删除后红黑树不平衡。此时要进行“双黑”操作

                记该结点为V,则删除了V后,从根结点到V的所有子孙叶结点的路径将会比树中其他的从根结点到叶结点的路径拥有更少的黑色结点, 破坏了红黑树性质4。此时,用“双黑”结点来表示从根结点到这个“双黑”结点的所有子孙叶结点的路径上都增加一个黑色结点。  
    双黑含义:该结点需要代表两个黑色结点,才能维持树的平衡

    红黑树删除操作 - 枫叶 - 枫叶

    图1

       如图1,要删除结点90,则删除后从根结点到结点90的所有子树结点的路径上的黑色结点比从根点到叶结点的路径上的黑结点少。因而,删除结点90后,用子结点NULL代替90结点,并置为“双黑”结点。


    3.“双黑”结点的处理

    分三种情况:

                           (1)双黑结点的兄弟结点是红色结点

                           (2)双黑结点的兄弟结点是黑色,且有两个黑色结点

                           (3)双黑色结点的兄弟结点是黑色,且子结点有红色结点

    (1)双黑结点的兄弟结点是红色结点

    处理方法:把父节点染成红色,兄弟节点染成黑色,然后对当前节点的父节点进行左旋,重新进入算法。

    (2)双黑结点的兄弟结点是黑色,且有两个黑色结点        

    处理方法:从当前节点和兄弟节点中抽取一重黑色追加到父节点,把父节点当成新的当前节点,重新进入算法。

    (3)双黑色结点的兄弟结点是黑色,且子结点有红色结点    
    A情况:双黑结点近侄子结点(双黑结点若为左孩子,则双黑结点的兄弟结点的左孩子为近侄子结点;同理,处理双黑结点为右孩子))为红色。
    处理方法:把兄弟节点染红,近侄子节点染黑,然后以兄弟节点为支点进行右旋,重新进入算法。

    B情况:双黑结点远侄子结点(双黑结点若为左孩子,则双黑结点的兄弟结点的右孩子为远侄子结点;同理,处理双黑结点为右孩子)为红色。
    处理方法:把兄弟节点染成当前父节点的颜色,把当前节点的父节点染成黑色,远侄子节点染成黑色,然后以当前节点的父节点为支点进行左旋,并把当前节点x指向旋转后树的根节点,算法结束,所有性质调整正确。


    插入过程

    插入顺序为:12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17

    插入节点12:为根节点 

     

    插入节点1:父节点为黑色,结束

    插入节点9:父节点为红色,叔父节点为黑色,LR,case2+case3

    插入节点2:父节点为红色,叔节点为红色,case1

    插入节点0:父节点为黑色,结束

    插入节点11:父节点为黑色,结束

    插入节点7:父节点为红色,叔节点为红色,case1

    插入节点19:父节点为黑色,结束

    插入节点4:父节点为红色,叔父节点为黑色,RL,case2+case3

    插入节点15:父节点为红,叔父节点为红,case1

    插入节点18:父节点为红,叔父节点为黑,LR,case2+case3

    插入节点5:父节点为红,叔父节点为红,case1

    父节点为红,叔父节点为红,case1

    插入节点14:父节点为红,叔父节点为红,case1

    插入节点13:父节点为红,叔父节点为黑,LL,case3

    插入节点10:父节点为黑,结束

    插入节点16:父节点为红,叔父节点为红,case1

    父节点为红,叔父节点为黑,RL,case2+case3

    插入节点6:父节点为红,叔父节点为黑,LR,case2+case3

    插入节点3:父节点为黑色,结束

    插入节点8:父节点为红,叔父节点为红,case1

    父节点为红,叔父节点为黑,RR,case3

    插入节点17:父节点为红,叔父节点为黑,RR,case3

    删除过程

    原始红黑树

    删除12:用13覆盖12,转换为删除13

    自己为黑,兄弟为黑,兄弟左子为黑,右子为红,case4

    删除1:用2覆盖1,转换为删除2

    自己为黑,当前节点3为红,变黑

    删除9:用10覆盖9,转化为删除10

    自己为黑,兄弟为黑,兄弟的双子为黑,case2

    自己为红,结束

    删除2:用3覆盖2,转换为删除3

    自己为黑,兄弟为黑,兄弟的双子为黑,case2

    自己为红,变黑,结束

    删除0:自己为红,结束

    删除11:当前节点为红,变黑,结束

    删除7:自己为黑,当前节点为红,变黑

    删除19:当前节点为黑,兄弟为黑,兄弟的左子为红,case4

    删除4,用5覆盖4,转换为删除5

    自己为黑,兄弟为黑,兄弟双子为黑,case2

    自己为红,变黑,结束

    删除15:自己为黑,兄弟为黑,兄弟的右子为黑,左子为红,case3+case4

    删除18:自己为黑,兄弟为黑,兄弟的双子为黑,case2

    自己为红,变黑,结束

    删除5:用8覆盖5,转换为删除8

    自己为红,结束

    删除14:用16覆盖14,转换为删除16

    自己为红,结束

    删除13:自己为黑,兄弟为黑,兄弟的双子为黑,case2

    自己为黑,兄弟为黑,兄弟的双子为黑,case2

    删除10:用16覆盖10,转换为删除10

    自己为黑,当前节点为红,变黑

    删除16:用17覆盖16,转换为删除17

    自己为黑,兄弟为红,case1

    自己为黑,兄弟为黑,兄弟的双子为黑,case2

    删除6:用8覆盖6,转化为删除8

    自己为红,结束

    删除3:自己为黑,兄弟为黑,兄弟的双子为黑,case2

    删除8:当前节点为红,变黑,结束

    删除17:结束





    另外一篇关于红黑树 添加、删除的链接: http://hi.baidu.com/coolinc/item/c2073dc375dfe8bd0c0a7bf6
    展开全文
  • 红黑树插入删除操作

    千次阅读 2016-09-26 15:42:51
     R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。 红黑树的特性: (1)每个节点或者是黑色,或者是红色...

     

    R-B Tree简介

        R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

    红黑树的特性:
    (1)每个节点或者是黑色,或者是红色。
    (2)根节点是黑色。
    (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
    (4)如果一个节点是红色的,则它的子节点必须是黑色的。
    (5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

    注意
    (01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
    (02) 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

    红黑树示意图如下:

     

    红黑树的应用

    红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。
    例如,Java集合中的TreeSetTreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。

     

    红黑树的时间复杂度和相关证明

    红黑树的时间复杂度为: O(lgn)
    下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

    定理:一棵含有n个节点的红黑树的高度至多为2log(n+1).

    证明:
        "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题是 "高度为h的红黑树,它的包含的内节点个数至少为 2h/2-1个"。
        我们只需要证明逆否命题,即可证明原命题为真;即只需证明 "高度为h的红黑树,它的包含的内节点个数至少为 2h/2-1个"

        从某个节点x出发(不包括该节点)到达一个叶节点的任意一条路径上,黑色节点的个数称为该节点的黑高度(x's black height),记为bh(x)。关于bh(x)有两点需要说明: 
        第1点:根据红黑树的"特性(5) ,即从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点"可知,从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着,bh(x)的值是唯一的
        第2点:根据红黑色的"特性(4),即如果一个节点是红色的,则它的子节点必须是黑色的"可知,从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点,则可以得出结论"bh(x) >= h/2"。
    进而,我们只需证明 "高度为h的红黑树,它的包含的黑节点个数至少为 2bh(x)-1个"即可。

        到这里,我们将需要证明的定理已经由
    "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 
        转变成只需要证明
    "高度为h的红黑树,它的包含的内节点个数至少为 2bh(x)-1个"。


    下面通过"数学归纳法"开始论证高度为h的红黑树,它的包含的内节点个数至少为 2bh(x)-1个"。

    (01) 当树的高度h=0时,
        内节点个数是0,bh(x) 为0,2bh(x)-1 也为 0。显然,原命题成立。

    (02) 当h>0,且树的高度为 h-1 时,它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的!

        下面,由树的高度为 h-1 的已知条件推出“树的高度为 h 时,它所包含的节点树为 2bh(x)-1”。

        当树的高度为 h 时,
        对于节点x(x为根节点),其黑高度为bh(x)。
        对于节点x的左右子树,它们黑高度为 bh(x) 或者 bh(x)-1。
        根据(02)的已知条件,我们已知 "x的左右子树,即高度为 h-1 的节点,它包含的节点至少为 2bh(x)-1-1 个";

        所以,节点x所包含的节点至少为 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。
        因此,原命题成立。

        由(01)、(02)得出,"高度为h的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"。
        因此,“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

     

    红黑树的基本操作(一) 左旋和右旋

    红黑树的基本操作是添加删除。在对红黑树进行添加或删除之后,都会用到旋转方法。为什么呢?道理很简单,添加或删除红黑树中的节点之后,红黑树就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转,可以使这颗树重新成为红黑树。简单点说,旋转的目的是让树保持红黑树的特性。
    旋转包括两种:左旋 和 右旋。下面分别对它们进行介绍。

     

    1. 左旋

    对x进行左旋,意味着"将x变成一个左节点"。


    左旋的伪代码《算法导论》:参考上面的示意图和下面的伪代码,理解“红黑树T的节点x进行左旋”是如何进行的。

    复制代码
    LEFT-ROTATE(T, x)  
    01  y ← right[x]            // 前提:这里假设x的右孩子为y。下面开始正式操作
    02  right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”,即 将β设为x的右孩子
    03  p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”,即 将β的父亲设为x
    04  p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
    05  if p[x] = nil[T]       
    06  then root[T] ← y                 // 情况1:如果 “x的父亲” 是空节点,则将y设为根节点
    07  else if x = left[p[x]]  
    08            then left[p[x]] ← y    // 情况2:如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
    09            else right[p[x]] ← y   // 情况3:(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
    10  left[y] ← x             // 将 “x” 设为 “y的左孩子”
    11  p[x] ← y                // 将 “x的父节点” 设为 “y”
    复制代码

    理解左旋之后,看看下面一个更鲜明的例子。你可以先不看右边的结果,自己尝试一下。

     

    2. 右旋

    对x进行左旋,意味着"将x变成一个左节点"。


    右旋的伪代码《算法导论》:参考上面的示意图和下面的伪代码,理解“红黑树T的节点y进行右旋”是如何进行的。 

    复制代码
    RIGHT-ROTATE(T, y)  
    01  x ← left[y]             // 前提:这里假设y的左孩子为x。下面开始正式操作
    02  left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”,即 将β设为y的左孩子
    03  p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”,即 将β的父亲设为y
    04  p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
    05  if p[y] = nil[T]       
    06  then root[T] ← x                 // 情况1:如果 “y的父亲” 是空节点,则将x设为根节点
    07  else if y = right[p[y]]  
    08            then right[p[y]] ← x   // 情况2:如果 y是它父节点的右孩子,则将x设为“y的父节点的左孩子”
    09            else left[p[y]] ← x    // 情况3:(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
    10  right[x] ← y            // 将 “y” 设为 “x的右孩子”
    11  p[y] ← x                // 将 “y的父节点” 设为 “x”
    复制代码

    理解右旋之后,看看下面一个更鲜明的例子。你可以先不看右边的结果,自己尝试一下。


    旋转总结

    (01) 左旋 和 右旋 是相对的两个概念,原理类似。理解一个也就理解了另一个。

    (02) 下面谈谈如何区分 左旋 和 右旋。
    在实际应用中,若没有彻底理解 左旋 和 右旋,可能会将它们混淆。下面谈谈我对如何区分 左旋 和 右旋 的理解。

     

    3. 区分 左旋 和 右旋

    仔细观察上面"左旋"和"右旋"的示意图。我们能清晰的发现,它们是对称的。无论是左旋还是右旋,被旋转的树,在旋转前是二叉查找树,并且旋转之后仍然是一颗二叉查找树。

     

     

    左旋示例图(以x为节点进行左旋):

                                   z
       x                          /                  
      / \      --(左旋)-->       x
     y   z                      /
                               y

    对x进行左旋,意味着,将“x的右孩子”设为“x的父亲节点”;即,将 x变成了一个左节点(x成了为z的左孩子)!。 因此,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”


    右旋示例图(以x为节点进行右旋):

                                   y
       x                            \                 
      / \      --(右旋)-->           x
     y   z                            \
                                       z

    对x进行右旋,意味着,将“x的左孩子”设为“x的父亲节点”;即,将 x变成了一个右节点(x成了为y的右孩子)! 因此,右旋中的“右”,意味着“被旋转的节点将变成一个右节点”

     

    红黑树的基本操作(二) 添加

    将一个节点插入到红黑树中,需要执行哪些步骤呢?首先,将红黑树当作一颗二叉查找树,将节点插入;然后,将节点着色为红色;最后,通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。详细描述如下:

    第一步: 将红黑树当作一颗二叉查找树,将节点插入。
           红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。
           好吧?那接下来,我们就来想方设法的旋转以及重新着色,使这颗树重新成为红黑树!

    第二步:将插入的节点着色为"红色"。
           为什么着色成红色,而不是黑色呢?为什么呢?在回答之前,我们需要重新温习一下红黑树的特性:
    (1) 每个节点或者是黑色,或者是红色。
    (2) 根节点是黑色。
    (3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
    (4) 如果一个节点是红色的,则它的子节点必须是黑色的。
    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
           将插入的节点着色为红色,不会违背"特性(5)"!少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。o(∩∩)o...哈哈

    第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。
           第二步中,将插入节点着色为"红色"之后,不会违背"特性(5)"。那它到底会违背哪些特性呢?
           对于"特性(1)",显然不会违背了。因为我们已经将它涂成红色了。
           对于"特性(2)",显然也不会违背。在第一步中,我们是将红黑树当作二叉查找树,然后执行的插入操作。而根据二叉查找数的特点,插入操作不会改变根节点。所以,根节点仍然是黑色。
           对于"特性(3)",显然不会违背了。这里的叶子节点是指的空叶子节点,插入非空节点并不会对它们造成影响。
           对于"特性(4)",是有可能违背的!
           那接下来,想办法使之"满足特性(4)",就可以将树重新构造成红黑树了。

    下面看看代码到底是怎样实现这三步的。

     

    添加操作的伪代码《算法导论》

    复制代码
    RB-INSERT(T, z)  
    01  y ← nil[T]                        // 新建节点“y”,将y设为空节点。
    02  x ← root[T]                       // 设“红黑树T”的根节点为“x”
    03  while x ≠ nil[T]                  // 找出要插入的节点“z”在二叉树T中的位置“y”
    04      do y ← x                      
    05         if key[z] < key[x]  
    06            then x ← left[x]  
    07            else x ← right[x]  
    08  p[z] ← y                          // 设置 “z的父亲” 为 “y”
    09  if y = nil[T]                     
    10     then root[T] ← z               // 情况1:若y是空节点,则将z设为根
    11     else if key[z] < key[y]        
    12             then left[y] ← z       // 情况2:若“z所包含的值” < “y所包含的值”,则将z设为“y的左孩子”
    13             else right[y] ← z      // 情况3:(“z所包含的值” >= “y所包含的值”)将z设为“y的右孩子” 
    14  left[z] ← nil[T]                  // z的左孩子设为空
    15  right[z] ← nil[T]                 // z的右孩子设为空。至此,已经完成将“节点z插入到二叉树”中了。
    16  color[z] ← RED                    // 将z着色为“红色”
    17  RB-INSERT-FIXUP(T, z)             // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转,让树T仍然是一颗红黑树
    复制代码

    结合伪代码以及为代码上面的说明,先理解RB-INSERT。理解了RB-INSERT之后,我们接着对 RB-INSERT-FIXUP的伪代码进行说明。

    添加修正操作的伪代码《算法导论》

    复制代码
    RB-INSERT-FIXUP(T, z)
    01 while color[p[z]] = RED                                                  // 若“当前节点(z)的父节点是红色”,则进行以下处理。
    02     do if p[z] = left[p[p[z]]]                                           // 若“z的父节点”是“z的祖父节点的左孩子”,则进行以下处理。
    03           then y ← right[p[p[z]]]                                        // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)”
    04                if color[y] = RED                                         // Case 1条件:叔叔是红色
    05                   then color[p[z]] ← BLACK                    ▹ Case 1   //  (01) 将“父节点”设为黑色。
    06                        color[y] ← BLACK                       ▹ Case 1   //  (02) 将“叔叔节点”设为黑色。
    07                        color[p[p[z]]] ← RED                   ▹ Case 1   //  (03) 将“祖父节点”设为“红色”。
    08                        z ← p[p[z]]                            ▹ Case 1   //  (04) 将“祖父节点”设为“当前节点”(红色节点)
    09                   else if z = right[p[z]]                                // Case 2条件:叔叔是黑色,且当前节点是右孩子
    10                           then z ← p[z]                       ▹ Case 2   //  (01) 将“父节点”作为“新的当前节点”。
    11                                LEFT-ROTATE(T, z)              ▹ Case 2   //  (02) 以“新的当前节点”为支点进行左旋。
    12                           color[p[z]] ← BLACK                 ▹ Case 3   // Case 3条件:叔叔是黑色,且当前节点是左孩子。(01) 将“父节点”设为“黑色”。
    13                           color[p[p[z]]] ← RED                ▹ Case 3   //  (02) 将“祖父节点”设为“红色”。
    14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3   //  (03) 以“祖父节点”为支点进行右旋。
    15        else (same as then clause with "right" and "left" exchanged)      // 若“z的父节点”是“z的祖父节点的右孩子”,将上面的操作中“right”和“left”交换位置,然后依次执行。
    16 color[root[T]] ← BLACK 
    复制代码

    根据被插入节点的父节点的情况,可以将"当节点z被着色为红色节点,并插入二叉树"划分为三种情况来处理。
    ① 情况说明:被插入的节点是根节点。
        处理方法:直接把此节点涂为黑色。
    ② 情况说明:被插入的节点的父节点是黑色。
        处理方法:什么也不需要做。节点被插入后,仍然是红黑树。
    ③ 情况说明:被插入的节点的父节点是红色。
        处理方法:那么,该情况与红黑树的“特性(5)”相冲突。这种情况下,被插入节点是一定存在非空祖父节点的;进一步的讲,被插入节点也一定存在叔叔节点(即使叔叔节点为空,我们也视之为存在,空节点本身就是黑色节点)。理解这点之后,我们依据"叔叔节点的情况",将这种情况进一步划分为3种情况(Case)。

     现象说明处理策略
    Case 1当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。

    (01) 将“父节点”设为黑色。
    (02) 将“叔叔节点”设为黑色。
    (03) 将“祖父节点”设为“红色”。
    (04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

    Case 2当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子

    (01) 将“父节点”作为“新的当前节点”。
    (02) 以“新的当前节点”为支点进行左旋。

    Case 3当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子

    (01) 将“父节点”设为“黑色”。
    (02) 将“祖父节点”设为“红色”。
    (03) 以“祖父节点”为支点进行右旋。

    上面三种情况(Case)处理问题的核心思路都是:将红色的节点移到根节点;然后,将根节点设为黑色。下面对它们详细进行介绍。

     

    1. (Case 1)叔叔是红色

    1.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。

    1.2 处理策略
    (01) 将“父节点”设为黑色。
    (02) 将“叔叔节点”设为黑色。
    (03) 将“祖父节点”设为“红色”。
    (04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

        下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
        “当前节点”和“父节点”都是红色,违背“特性(4)”。所以,将“父节点”设置“黑色”以解决这个问题。
        但是,将“父节点”由“红色”变成“黑色”之后,违背了“特性(5)”:因为,包含“父节点”的分支的黑色节点的总数增加了1。  解决这个问题的办法是:将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”。关于这里,说明几点:第一,为什么“祖父节点”之前是黑色?这个应该很容易想明白,因为在变换操作之前,该树是红黑树,“父节点”是红色,那么“祖父节点”一定是黑色。 第二,为什么将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”;能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”,既然这样,我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题; 但是,这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”,现在我们已知“叔叔节点”是“红色”,将“叔叔节点”设为“黑色”就能解决这个问题。 所以,将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”;就解决了该问题。
        按照上面的步骤处理之后:当前节点、父节点、叔叔节点之间都不会违背红黑树特性,但祖父节点却不一定。若此时,祖父节点是根节点,直接将祖父节点设为“黑色”,那就完全解决这个问题了;若祖父节点不是根节点,那我们需要将“祖父节点”设为“新的当前节点”,接着对“新的当前节点”进行分析。

    1.3 示意图

     

    2. (Case 2)叔叔是黑色,且当前节点是右孩子

    2.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子

    2.2 处理策略
    (01) 将“父节点”作为“新的当前节点”。
    (02) 以“新的当前节点”为支点进行左旋。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          首先,将“父节点”作为“新的当前节点”;接着,以“新的当前节点”为支点进行左旋。 为了便于理解,我们先说明第(02)步,再说明第(01)步;为了便于说明,我们设置“父节点”的代号为F(Father),“当前节点”的代号为S(Son)。
    为什么要“以F为支点进行左旋”呢?根据已知条件可知:S是F的右孩子。而之前我们说过,我们处理红黑树的核心思想:将红色的节点移到根节点;然后,将根节点设为黑色。既然是“将红色的节点移到根节点”,那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)。 而S又是一个右孩子,因此,我们可以通过“左旋”来将S上移! 
          按照上面的步骤(以F为支点进行左旋)处理之后:若S变成了根节点,那么直接将其设为“黑色”,就完全解决问题了;若S不是根节点,那我们需要执行步骤(01),即“将F设为‘新的当前节点’”。那为什么不继续以S为新的当前节点继续处理,而需要以F为新的当前节点来进行处理呢?这是因为“左旋”之后,F变成了S的“子节点”,即S变成了F的父节点;而我们处理问题的时候,需要从下至上(由叶到根)方向进行处理;也就是说,必须先解决“孩子”的问题,再解决“父亲”的问题;所以,我们执行步骤(01):将“父节点”作为“新的当前节点”。

    2.2 示意图

     

    3. (Case 3)叔叔是黑色,且当前节点是左孩子

    3.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子

    3.2 处理策略
    (01) 将“父节点”设为“黑色”。
    (02) 将“祖父节点”设为“红色”。
    (03) 以“祖父节点”为支点进行右旋。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          为了便于说明,我们设置“当前节点”为S(Original Son),“兄弟节点”为B(Brother),“叔叔节点”为U(Uncle),“父节点”为F(Father),祖父节点为G(Grand-Father)。
          S和F都是红色,违背了红黑树的“特性(4)”,我们可以将F由“红色”变为“黑色”,就解决了“违背‘特性(4)’”的问题;但却引起了其它问题:违背特性(5),因为将F由红色改为黑色之后,所有经过F的分支的黑色节点的个数增加了1。那我们如何解决“所有经过F的分支的黑色节点的个数增加了1”的问题呢? 我们可以通过“将G由黑色变成红色”,同时“以G为支点进行右旋”来解决。

    2.3 示意图

    提示:上面的进行Case 3处理之后,再将节点"120"当作当前节点,就变成了Case 2的情况。

     

    红黑树的基本操作(三) 删除

    将红黑树内的某一个节点删除。需要执行的操作依次是:首先,将红黑树当作一颗二叉查找树,将该节点从二叉查找树中删除;然后,通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。详细描述如下:

    第一步:将红黑树当作一颗二叉查找树,将节点删除。
           这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况:
           ① 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。
           ② 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。
           ③ 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。在这里,后继节点相当于替身,在将后继节点的内容复制给"被删除节点"之后,再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了,下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空,就意味着"该节点的后继节点"要么没有儿子,要么只有一个儿子。若没有儿子,则按"情况① "进行处理;若只有一个儿子,则按"情况② "进行处理。

    第二步:通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。
           因为"第一步"中删除节点之后,可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树,使之重新成为一棵红黑树。

     

    删除操作的伪代码《算法导论》

    复制代码
    RB-DELETE(T, z)
    01 if left[z] = nil[T] or right[z] = nil[T]         
    02    then y ← z                                  // 若“z的左孩子” 或 “z的右孩子”为空,则将“z”赋值给 “y”;
    03    else y ← TREE-SUCCESSOR(z)                  // 否则,将“z的后继节点”赋值给 “y”。
    04 if left[y] ≠ nil[T]
    05    then x ← left[y]                            // 若“y的左孩子” 不为空,则将“y的左孩子” 赋值给 “x”;
    06    else x ← right[y]                           // 否则,“y的右孩子” 赋值给 “x”。
    07 p[x] ← p[y]                                    // 将“y的父节点” 设置为 “x的父节点”
    08 if p[y] = nil[T]                               
    09    then root[T] ← x                            // 情况1:若“y的父节点” 为空,则设置“x” 为 “根节点”。
    10    else if y = left[p[y]]                    
    11            then left[p[y]] ← x                 // 情况2:若“y是它父节点的左孩子”,则设置“x” 为 “y的父节点的左孩子”
    12            else right[p[y]] ← x                // 情况3:若“y是它父节点的右孩子”,则设置“x” 为 “y的父节点的右孩子”
    13 if y ≠ z                                    
    14    then key[z] ← key[y]                        // 若“y的值” 赋值给 “z”。注意:这里只拷贝z的值给y,而没有拷贝z的颜色!!!
    15         copy y's satellite data into z         
    16 if color[y] = BLACK                            
    17    then RB-DELETE-FIXUP(T, x)                  // 若“y为黑节点”,则调用
    18 return y 
    复制代码

    结合伪代码以及为代码上面的说明,先理解RB-DELETE。理解了RB-DELETE之后,接着对 RB-DELETE-FIXUP的伪代码进行说明

    复制代码
    RB-DELETE-FIXUP(T, x)
    01 while x ≠ root[T] and color[x] = BLACK  
    02     do if x = left[p[x]]      
    03           then w ← right[p[x]]                                             // 若 “x”是“它父节点的左孩子”,则设置 “w”为“x的叔叔”(即x为它父节点的右孩子)                                          
    04                if color[w] = RED                                           // Case 1: x是“黑+黑”节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
    05                   then color[w] ← BLACK                        ▹  Case 1   //   (01) 将x的兄弟节点设为“黑色”。
    06                        color[p[x]] ← RED                       ▹  Case 1   //   (02) 将x的父节点设为“红色”。
    07                        LEFT-ROTATE(T, p[x])                    ▹  Case 1   //   (03) 对x的父节点进行左旋。
    08                        w ← right[p[x]]                         ▹  Case 1   //   (04) 左旋后,重新设置x的兄弟节点。
    09                if color[left[w]] = BLACK and color[right[w]] = BLACK       // Case 2: x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。
    10                   then color[w] ← RED                          ▹  Case 2   //   (01) 将x的兄弟节点设为“红色”。
    11                        x ←  p[x]                               ▹  Case 2   //   (02) 设置“x的父节点”为“新的x节点”。
    12                   else if color[right[w]] = BLACK                          // Case 3: x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。
    13                           then color[left[w]] ← BLACK          ▹  Case 3   //   (01) 将x兄弟节点的左孩子设为“黑色”。
    14                                color[w] ← RED                  ▹  Case 3   //   (02) 将x兄弟节点设为“红色”。
    15                                RIGHT-ROTATE(T, w)              ▹  Case 3   //   (03) 对x的兄弟节点进行右旋。
    16                                w ← right[p[x]]                 ▹  Case 3   //   (04) 右旋后,重新设置x的兄弟节点。
    17                         color[w] ← color[p[x]]                 ▹  Case 4   // Case 4: x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的。(01) 将x父节点颜色 赋值给 x的兄弟节点。
    18                         color[p[x]] ← BLACK                    ▹  Case 4   //   (02) 将x父节点设为“黑色”。
    19                         color[right[w]] ← BLACK                ▹  Case 4   //   (03) 将x兄弟节点的右子节设为“黑色”。
    20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4   //   (04) 对x的父节点进行左旋。
    21                         x ← root[T]                            ▹  Case 4   //   (05) 设置“x”为“根节点”。
    22        else (same as then clause with "right" and "left" exchanged)        // 若 “x”是“它父节点的右孩子”,将上面的操作中“right”和“left”交换位置,然后依次执行。
    23 color[x] ← BLACK   
    复制代码

    下面对删除函数进行分析。在分析之前,我们再次温习一下红黑树的几个特性:
    (1) 每个节点或者是黑色,或者是红色。
    (2) 根节点是黑色。
    (3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
    (4) 如果一个节点是红色的,则它的子节点必须是黑色的。
    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。


          前面我们将"删除红黑树中的节点"大致分为两步,在第一步中"将红黑树当作一颗二叉查找树,将节点删除"后,可能违反"特性(2)、(4)、(5)"三个特性。第二步需要解决上面的三个问题,进而保持红黑树的全部特性。
          为了便于分析,我们假设"x包含一个额外的黑色"(x原本的颜色还存在),这样就不会违反"特性(5)"。为什么呢?
          通过RB-DELETE算法,我们知道:删除节点y之后,x占据了原来节点y的位置。 既然删除y(y是黑色),意味着减少一个黑色节点;那么,再在该位置上增加一个黑色即可。这样,当我们假设"x包含一个额外的黑色",就正好弥补了"删除y所丢失的黑色节点",也就不会违反"特性(5)"。 因此,假设"x包含一个额外的黑色"(x原本的颜色还存在),这样就不会违反"特性(5)"。
          现在,x不仅包含它原本的颜色属性,x还包含一个额外的黑色。即x的颜色属性是"红+黑"或"黑+黑",它违反了"特性(1)"。

          现在,我们面临的问题,由解决"违反了特性(2)、(4)、(5)三个特性"转换成了"解决违反特性(1)、(2)、(4)三个特性"。RB-DELETE-FIXUP需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是:将x所包含的额外的黑色不断沿树上移(向根方向移动),直到出现下面的姿态:
    a) x指向一个"红+黑"节点。此时,将x设为一个"黑"节点即可。
    b) x指向根。此时,将x设为一个"黑"节点即可。
    c) 非前面两种姿态。

    将上面的姿态,可以概括为3种情况。
    ① 情况说明:x是“红+黑”节点。
        处理方法:直接把x设为黑色,结束。此时红黑树性质全部恢复。
    ② 情况说明:x是“黑+黑”节点,且x是根。
        处理方法:什么都不做,结束。此时红黑树性质全部恢复。
    ③ 情况说明:x是“黑+黑”节点,且x不是根。
        处理方法:这种情况又可以划分为4种子情况。这4种子情况如下表所示:

     现象说明处理策略
    Case 1x是"黑+黑"节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。

    (01) 将x的兄弟节点设为“黑色”。
    (02) 将x的父节点设为“红色”。
    (03) 对x的父节点进行左旋。
    (04) 左旋后,重新设置x的兄弟节点。

    Case 2x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。

    (01) 将x的兄弟节点设为“红色”。
    (02) 设置“x的父节点”为“新的x节点”。

    Case 3x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。

    (01) 将x兄弟节点的左孩子设为“黑色”。
    (02) 将x兄弟节点设为“红色”。
    (03) 对x的兄弟节点进行右旋。
    (04) 右旋后,重新设置x的兄弟节点。

    Case 4x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色。

    (01) 将x父节点颜色 赋值给 x的兄弟节点。
    (02) 将x父节点设为“黑色”。
    (03) 将x兄弟节点的右子节设为“黑色”。
    (04) 对x的父节点进行左旋。
    (05) 设置“x”为“根节点”。

     

    1. (Case 1)x是"黑+黑"节点,x的兄弟节点是红色

    1.1 现象说明
    x是"黑+黑"节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。

    1.2 处理策略
    (01) 将x的兄弟节点设为“黑色”。
    (02) 将x的父节点设为“红色”。
    (03) 对x的父节点进行左旋。
    (04) 左旋后,重新设置x的兄弟节点。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”,从而进行进一步的处理。对x的父节点进行左旋;左旋后,为了保持红黑树特性,就需要在左旋前“将x的兄弟节点设为黑色”,同时“将x的父节点设为红色”;左旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。

    1.3 示意图

     

    2. (Case 2) x是"黑+黑"节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色

    2.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。

    2.2 处理策略
    (01) 将x的兄弟节点设为“红色”。
    (02) 设置“x的父节点”为“新的x节点”。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          这个情况的处理思想:是将“x中多余的一个黑色属性上移(往根方向移动)”。 x是“黑+黑”节点,我们将x由“黑+黑”节点 变成 “黑”节点,多余的一个“黑”属性移到x的父节点中,即x的父节点多出了一个黑属性(若x的父节点原先是“黑”,则此时变成了“黑+黑”;若x的父节点原先时“红”,则此时变成了“红+黑”)。 此时,需要注意的是:所有经过x的分支中黑节点个数没变化;但是,所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)!为了解决这个问题,我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可,那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
          经过上面的步骤(将x的兄弟节点设为红色),多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”,直接将“新的x节点”设为黑色,即可完全解决该问题;若“新的x节点”是“黑+黑”,则需要对“新的x节点”进行进一步处理。

    2.3 示意图

     

    3. (Case 3)x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的

    3.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。

    3.2 处理策略
    (01) 将x兄弟节点的左孩子设为“黑色”。
    (02) 将x兄弟节点设为“红色”。
    (03) 对x的兄弟节点进行右旋。
    (04) 右旋后,重新设置x的兄弟节点。

           下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
           我们处理“Case 3”的目的是为了将“Case 3”进行转换,转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋;为了保证右旋后,它仍然是红黑树,就需要在右旋前“将x的兄弟节点的左孩子设为黑色”,同时“将x的兄弟节点设为红色”;右旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。

    3.3 示意图

     

    4. (Case 4)x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色

    4.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色。

    4.2 处理策略
    (01) 将x父节点颜色 赋值给 x的兄弟节点。
    (02) 将x父节点设为“黑色”。
    (03) 将x兄弟节点的右子节设为“黑色”。
    (04) 对x的父节点进行左旋。
    (05) 设置“x”为“根节点”。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          我们处理“Case 4”的目的是:去掉x中额外的黑色,将x变成单独的黑色。处理的方式是“:进行颜色修改,然后对x的父节点进行左旋。下面,我们来分析是如何实现的。
          为了便于说明,我们设置“当前节点”为S(Original Son),“兄弟节点”为B(Brother),“兄弟节点的左孩子”为BLS(Brother's Left Son),“兄弟节点的右孩子”为BRS(Brother's Right Son),“父节点”为F(Father)。
          我们要对F进行左旋。但在左旋前,我们需要调换F和B的颜色,并设置BRS为黑色。为什么需要这里处理呢?因为左旋后,F和BLS是父子关系,而我们已知BL是红色,如果F是红色,则违背了“特性(4)”;为了解决这一问题,我们将“F设置为黑色”。 但是,F设置为黑色之后,为了保证满足“特性(5)”,即为了保证左旋之后:
          第一,“同时经过根节点和S的分支的黑色节点个数不变”。
                 若满足“第一”,只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”,而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1;现在,只需将S由“黑+黑”变成单独的“黑”节点,即可满足“第一”。
          第二,“同时经过根节点和BLS的分支的黑色节点数不变”。
                 若满足“第二”,只需要将“F的原始颜色”赋值给B即可。之前,我们已经将“F设置为黑色”(即,将B的颜色"黑色",赋值给了F)。至此,我们算是调换了F和B的颜色。
          第三,“同时经过根节点和BRS的分支的黑色节点数不变”。
                 在“第二”已经满足的情况下,若要满足“第三”,只需要将BRS设置为“黑色”即可。
    经过,上面的处理之后。红黑树的特性全部得到的满足!接着,我们将x设为根节点,就可以跳出while循环(参考伪代码);即完成了全部处理。

    至此,我们就完成了Case 4的处理。理解Case 4的核心,是了解如何“去掉当前节点额外的黑色”。

    4.3 示意图

       

    OK!至此,红黑树的理论知识差不多讲完了。后续再更新红黑树的实现代码

    展开全文
  • 红黑树删除操作

    千次阅读 2013-07-18 13:03:04
    上一篇文章主要讲到了红黑树的基本性质以及插入节点的操作,有了上面的基础后,今天就把红黑树剩余的一个难点也就是删除节点的操作详细的讲一下。 红黑树节点的删除方法一开始的操作和二叉搜索树差不多,都是首先...
  • 红黑树 一张导图解决红黑树全部插入和删除问题 包含详细操作原理 情况对比
  • 相对于红黑树插入操作,删除操作复杂的多。 第一:先看最简单情况,即删除红色节点。删除红色节点,不影响红黑树平衡性质,如图:   只需要删除红色节点,不需要进行调整,因为不影响红黑树的性质。 ...
  • 红黑树及其插入、删除操作

    千次阅读 2018-10-19 13:57:05
    在二叉搜索中,基本操作如结点的插入、删除、查找的性能上界都得不到保证,原因在于二叉搜索的构造依赖于其结点值的插入顺序,最坏情况下二叉搜索会退化为单链表(如下图所示)。因此我们需要对二叉搜索做出...
  • 红黑树的添加删除操作

    万次阅读 热门讨论 2010-07-09 10:57:00
    <br />来自: http://hi.baidu.com/coolinc/blog/item/3aa07f3e162502eb54e723b1.html<br />介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树...
  • 红黑树基本操作算法

    2014-10-12 14:48:49
    红黑树插入删除算法,检查了几次都没有错误,算法导论
  • 红黑树(3) - 删除操作

    千次阅读 2015-07-11 22:30:29
    红黑树(3) - 删除操作
  • 本文的思维导图解决了红黑树全部插入和删除问题,包含详细操作原理,各种情况的对比和原因 思维导图源文件已经发布在我的资源当中,有需要的可以去 我的主页 了解更多计算机学科的精品思维导图整理 本文可以转载,但...
  • 红黑树删除例子

    万次阅读 2020-01-16 12:01:14
    这里不将原理了,只放几个例子供大家观看,如有错误请留言 删除3 红色节点直接删即可 删除2 右子节点替代2,1变黑即可 删除5 比较麻烦 删除66
  • 本文的思维导图解决了红黑树全部插入和删除问题,包含详细操作原理,各种情况的对比和原因,资源的具体内容可查看我的相对应博文
  • 二、红黑树删除后的调整 删除节点后的调整要根据N的不同情形来分情况处理。假设删除节点后的树中,N的父节点为P,兄弟节点为S,兄弟节点的左孩子为SL,兄弟节点的右孩子为SR。需要注意的是空节点是有颜色的,它是...
  • stl源码剖析一书中关于红黑树删除的操作只字未提,删除操作比较复杂,没有相关说明比较晦涩。 本人再看这个函数时也是冒了一身冷汗,这方面的资料很匮乏,好容易找到了,与大家分享一下。。。
  • 红黑树、插入删除操作

    千次阅读 2016-04-01 13:41:24
    二叉排序树 一棵自平衡的二叉排序树(二叉搜索树) 生成二叉排序树的过程是非常容易失衡的,最坏的情况就是...红黑树红黑树需要满足5条性质: - 节点非红即黑 - 根节点是黑色 - 所有NULL结点称为叶子节点,且
  • 红黑树

    万次阅读 2011-02-11 21:56:00
    红黑树和之前所讲的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。...
  • 看这篇文章 需要了解AVL树,知道AVL树的 删除,旋转调整等操作。这是我对红黑树删除的一些理解
  • 红黑树删除一个节点,可以先用普通二叉搜索树的方法,将节点从红黑树删除掉,然后再将被破坏的红黑性质进行恢复。 首先我们来看看普通二叉树的节点删除方法:  我们回忆一下普通二叉树的节点删除方法:Z...
  • 红黑树的5个性质: 性质1. 节点是红色或黑色。 性质2. 根节点是黑色。 性质3.所有叶子都是黑色。(叶子是NUIL节点) 性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的...
  • 看了很多材料,关于红黑树的删除,大概所有的总结都大同小异,今天先聊聊对红黑树删除的情况分析: 红黑树的删除操作 1:节点命名约定 D表示要被删除的节点。即:取 Delete 的首字母; P 表示父节点。即:取 ...
  • 1. 红黑树删除操作过程分析 1. 首先看一下普通搜索二叉树的删除操作,普通搜索二叉树删除结点找替代结点有3种情情景: 情景1:删除结点无子结点,直接删除 情景2:删除结点只有一个子结点 情景3:删除...
  • 红黑树插入删除详解

    万次阅读 多人点赞 2018-07-11 15:54:05
    红黑树插入删除操作的介绍转载自:红黑树 练习题转载自:红黑树练习 R-B Tree简介  R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,...
  • 理解红黑树(下)删除操作

    千次阅读 多人点赞 2017-11-14 17:13:41
    1. 引言红黑树的结点增删改查效率非常优良,都为logn,其应用十分广泛: 1. Linux内核进程调度由红黑树管理进程控制块。 2. Epoll用红黑树管理事件块。 3. nginx服务器用红黑树管理定时器。 4. C++ STL中的...
  • 一、红黑树(Red Black Tree)删除操作 B树中,最后真正被删除的元素都在叶子节点中 1、删除 – RED节点 直接删除,不用作任何调整 2、删除 – BLACK节点 有 3 种情况 ①、拥有 2 个RED 子节点的BLACK 节点 ✓ 不...
  • 红黑树 删除调整步骤终极详解

    千次阅读 2019-01-14 17:16:46
    红黑树删除无疑是最难的,抛开调整,红黑树的插入删除都跟选择二叉树一样,所以前面的步骤网上很多了,在这里只讲如何调整,以满足红黑树性质。  还是从头到尾理一下吧...  先定义一下,删除节点为d,真实删除...
  • 前面我们讨论了红黑树的插入的实现,基本思想是分类讨论;然后分情况讨论以后我们发现插入操作调整函数只需要处理三种情况,并不是太复杂。但是删除操作会更复杂一点...下面先放出红黑树删除函数的代码://红黑树删除
  • 红黑树删除节点——这一篇就够了

    千次阅读 多人点赞 2019-10-11 11:38:24
    红黑树常用的操作是插入、删除和查找,并且它对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保,对于红黑树的概念、性质、插入、查找和旋转等这里不再多讲,不了解的请点击wikipedia rb-tree,这里重点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,459
精华内容 24,583
关键字:

红黑树的删除操作