算法导论第十三章 红黑树

  写在前面:这一章真的把我害惨了,之前至少尝试看过3遍,每次看之前都下定决定一定要把它拿下,可是由于内容较多,深度够深,以致于每次要不是中途有什么事放弃了就跳过了,要不是花时间太多仍然不能理解而放弃。这次总算挺过来了,前后零零散散的时间加起来差不多也有两天时间。这次能坚持下来并攻克,我想大概有这么几个原因吧:第一是之前下定的决心要写一个最新版《算法导论》的读书笔记,之前几章都坚持写了,不能让这个成为拦路虎,即使再难再花时间都要弄懂;第二是通过前面几章的动手实践,发现自己的理解能力、动手能力都进步了,自然这章理解起来也不那么费力了;第三,如果有,那就是现在懂的东西多了,视野开阔了^-^。但说实话,也是费了不少心血,看了一下自己的打的草稿,超过十页以上,密密麻麻都是一些红黑树,这些努力我觉得都是值得的,但我之所以说“把我害惨了”,甚至有点不甘的是:我好大一部分时间都花在了调试代码上,原因是粗心大意写错了一些变量、指针......这一章由于涉及到多个指针的替换,所以切记在写的时候一定足够专注,尽量一口气写完,不要拖。

一、红黑树概览

  红黑树是一种平衡二叉树,什么是平衡二叉树?我的理解是加上”平衡条件“的二叉搜索树。其实这样的理解还不准确,因为二叉搜索树只在某些特殊的情况下是不平衡的。比如下图所示:

  所以,所谓树形平衡与否,并没有一个绝对的标准,”平衡“ 的大致意义是:没有任何一个结点深度过大。二叉搜索树在某些特殊情况下,无法维持绝对的平衡,所以,其动态集合操作,最坏的时间复杂度为O(n)。因此就出现一些通过加上某种”平衡条件“来促使二叉搜索树达到绝对的平衡(确保整棵树的深度维持在O(lgn))。红黑树的”平衡条件“是:赋予结点不同颜色,并对根结点到任何叶子结点的颜色进行约束。这样的平衡不算太好,近似平衡,但性能已经比二叉搜索树提升了不少。

  红黑树不仅是二叉搜索树,且必须满足以下5条平衡规则:

1)每个结点或是红色,或是是黑色。 2)根结点是黑的。 3)所有的叶结点(NULL)是黑色的。(NULL被视为一个哨兵结点,所有应该指向NULL的指针,都看成指向了NULL结点。) 4)如果一个结点是红色的,则它的两个儿子节点都是黑色的。 5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

简单的记法就是:红黑 黑 黑 红黑黑 黑

黑高度的定义: 从某个结点出发(不包括该结点)到达一个叶结点的任意一条路径上,黑色结点的个数成为该结点x的黑高度。红黑树的黑高度定义为其根结点的黑高度。

二、平衡二叉树历史概览

  最好的平衡是形如满二叉树这种,所以可以把全是黑色节点的满二叉树看做是红黑树的一个特列,其性能是最好的。但是是无论如何也不可能找到这样的平衡条件,有一种树退而求其次,它的平衡条件是要求任何结点的左右子树高度相差不超过1,就是AVL树。AVL树是最早提出的将搜索树平衡化的想法的实践。此外,还有由J.E.Hopcroft提出的一种”2-3“树,这种树是通过操纵结点的度数来维持平衡的。Bayer提出一种”2-3“树的推广,B树。Anderson提出了一种代码更简单的红黑树变种,称为AA树,AA树和红黑树类似,只是左边孩子永远不能为红色。还有一种treap树则是由Seidel和Aragon提出的。

  此外,平衡二叉树还有很多变种,包括带权的平衡树、k近邻树,以及替罪羊树,还有一种比较有趣的”伸展树“,伸展树不需要明确的平衡条件来维持平衡,替代的是,每次存取时的”伸展操作“在树内进行,后面会涉及到。另外还有就是跳表,跳表是扩展了一些额外指针的链表。

  但是,红黑树是真正的在实际中得到大量应用的复杂数据结构:C++STL中的关联容器map,set都是红黑树的应用(所以标准库容器的效率太好了,能用标准库容器尽量使用标准库容器);Linux内核中的用户态地址空间管理也使用了红黑树。

三、红黑树实现

经验之谈:

1)插入删除和二叉搜索树类似,插入的结点必须着红色(因为如果是黑色,是一定会破坏性质5,难以修复,而如果是红色,则可能破坏性质2和4,容易修复);

2)插入修复三种情况:发生在插入结点的父结点为红色的情况下,即破坏了性质4,这个时候考虑插入点的uncle结点进行修复;性质2破坏,直接着黑色;

3)删除恢复四种情况:发生在删除结点为黑色的情况下,即破坏了性质5,这个时候考虑删除点的brother结点进行修复;

4)旋转操作注意指针的指向,每个都要考虑全了,parent、left、right缺一不可。

如果按照《算法导论》书的步骤一步步往下看,是一定看得懂的,因为书上的东西是写的最全的,网友写的博客虽然有些也不错,但都是经过自己过滤过的,且不说语言表达怎样,肯定没有书本记录得详细。只是有些地方书本上表达得太深奥,可以借助一些博客来理解。比如说我在看到删除修复的四种情况时,书上说的什么”双重黑色、红+黑,x既不是黑色,也不是红色“,把我搞得稀里糊涂的,看了之后整个人都不好了,后来看了July的博客才弄懂了个大概(见后面的参考引文),再回过头来看就发现原来如此。

关于红黑树查找、删除等具体的细节就不再做过多的赘述,这里只记录下自己学习了之后的一些规律总结及心得。

关于旋转:

旋转有些书分为单旋和双旋,双旋顾名思义就是单旋两次,单旋又分为左旋和右旋,操作是对称的。旋转操作对于理解树的指针指向是再好不过了,就像理解链表的指针指向再好不过是元素的插入了。这里要确保一个结点的三个指针:parent、left、right都要更新了。书上没说具体的方法论,如果让我们在纸上写个左旋,估计好多人都要跪,因为指针指来指去,没有思路完全不行。根据我的经验,总结这样的一个规律(仅供参考):

就拿左旋作为例子,如下图所示:

规律可以总结成3个字:补——>提——>降

注意:图2由于纸张不够的原因,代码没写全,见下面的代码部分:

附上左旋的代码(C++模板类):

 1 //左旋
 2 template<typename TKey, typename TValue> 
 3 void RBTree<TKey, TValue>::_LeftRotate( RBTreeNode *x_node )
 4 {
 5     //assert
 6     if ( !(x_node->isValid() && x_node->Right->isValid()) )
 7         throw exception( "左旋操作要求对非哨兵进行操作,并且要求右孩子也不是哨兵" );
 8 
 9     RBTreeNode *y_node = x_node->Right;
10 
11     //以下三步的宗旨是用 y 替换 x,注意将 x 的Parent、Left、Right都换成 y 的
12     // 1) x 和 y 分离 (补)
13     x_node->Right = y_node->Left;
14     if (y_node->Left != m_pNil)
15         y_node->Left->Parent = x_node;
16     
17     // 2) 设置y->Parent (提)
18     y_node->Parent = x_node->Parent;
19     if (x_node->Parent == m_pNil)
20         m_pRoot = y_node;
21     else if (x_node->Parent->Left == x_node)
22         x_node->Parent->Left = y_node;
23     else
24         x_node->Parent->Right = y_node;
25 
26     // 3) 设置y->Left (降)
27     y_node->Left = x_node;
28     x_node->Parent = y_node;
29 }

关于删除修复的”双重黑、红+黑“:

  如何理解?这个地方,书上没说明白,在说这个意思之前,我们先来看看红黑树的删除修复究竟是怎么个回事?

  红黑树的删除务必不能破坏了红黑树的5条性质,但这是不可能的,如果删除的结点破坏了5条中任何一条性质,这个时候就需要采用措施进行修复,我们分析一下:删除什么结点会破坏性质,破坏哪条性质?

1)如果删除的是红色结点,则无影响;

2)如果删除的是黑色结点,则不用想,第5条性质破坏了,其中:

  a)如果这个黑色结点是根结点,同时根结点的非空子结点,即将要替换它的结点为红色,则破坏性质2;

  b)如果这个黑色结点的父结点和非空子结点都为红色,则破坏性质4。

知道了这点,我们再来看下什么是”双重黑、红+黑“,其实,这个说法主要是一种假设,假设存在着这样的节点,那么红黑树的性质就满足了,但实际上这样的结点是不存在的,所以需要转换,而转换的过程就是修复的过程。说白了,这个假设是为了便于代码实现,为了方便完成四种修复操作的一个假设性规律。因为删除修复不像插入修复那么明显,有了它就像找到什么诀窍一样,删除的四种修复不用”强制性记忆“就能明白为什么要这样做^-^。

红黑树的删除与二叉搜索树的删除基本一样,不同之处在于需要记录替换被删结点到那个结点,然后以它为根进行修复。”双重黑、红+黑“就体现在这里,如下两图所示:

其中,delete结点被其后继结点 x (这里两种情况:一是后继就是delete的右孩子,二是比delete大的最小结点)替换。需要修复的条件是:删除结点得是黑色,如果 x 也是黑色,则称为”双黑“;如果 x 是红色,则称为”红黑“。好了,知道了这点,在对照着删除修复的四种情况看,就很容易懂了,其修复的过程就是看 x 的颜色情况和 x的兄弟结点的颜色情况,有双重黑的,就去掉一重黑,使之平衡,四种情况分别有不同的去重情况,整个过程是很好理解的,具体的细节就不做赘述,想必知道这点,整个删除修复就很好理解了。

  这一章我觉得难点就在于删除修复,插入修复是比较容易想到的,然后我认为需要着重注意的地方都记录下来了,下面贴上自己写的基于C++模板的代码,有点长。

1)red_black_tree.h

  1 #ifndef __RED_BLACK_TREE_
  2 #define __RED_BLACK_TREE_
  3 
  4 //使用模板类
  5 template< typename TKey, typename TValue >
  6 class RBTree 
  7 {
  8 /************************************************************************/
  9 /* 红黑树结点属性                                                               
 10 /************************************************************************/
 11 public:
 12     //结点的颜色-枚举
 13     enum RBTreeNodeColor {
 14         RED,    //红色
 15         BLACK    //黑色
 16     };
 17 
 18     //结点的属性
 19     struct RBTreeNode {
 20         TKey                Key;
 21         TValue                Value;
 22         RBTreeNodeColor        Color;
 23         RBTreeNode            *Parent;
 24         RBTreeNode            *Left;
 25         RBTreeNode            *Right;
 26         
 27         //@brief 红黑树中的哨兵结点T.nil实际上是空结点,为无效结点
 28         //@return 返回某个结点是否为无效结点
 29         //@retval = true 非nil结点
 30         //@retval = false nil结点
 31         inline bool isValid() const {
 32             return ( this != m_pNil );
 33         }
 34     };
 35 
 36 /************************************************************************/
 37 /* 红黑树公有属性                                                          
 38 /************************************************************************/
 39 public:
 40     RBTree();    //构造函数
 41     ~RBTree();    //析构函数
 42 
 43     //@brief 插入一个结点
 44     bool Insert( TKey key, TValue value );
 45 
 46     //@brief 删除一个结点
 47     bool Delete( TKey key );
 48 
 49     //@brief 搜索一个结点
 50     RBTreeNode * Search( TValue const &value );
 51 
 52     //@brief 判断红黑树是否为空
 53     bool Empty();
 54 
 55     //@brief 显示当前红黑树
 56     void Display() const;
 57 
 58 /************************************************************************/
 59 /* 红黑树私有属性                                                          
 60 /************************************************************************/
 61 private:
 62     //@brief 递归删除所有结点
 63     void _RecursiveReleaseNode ( RBTreeNode *node );
 64     
 65     //@brief 显示
 66     void _Display( RBTreeNode *node ) const;
 67     
 68     //@brief 真正的插入函数
 69     void _InsertRBTree( RBTreeNode *node ); 
 70 
 71     //@brief 对插入操作的修复
 72     void _InsertFixup( RBTreeNode *node );
 73 
 74     //@brief 左旋
 75     void _LeftRotate( RBTreeNode *node );
 76 
 77     //@brief 右旋
 78     void _RightRotate( RBTreeNode *node );
 79 
 80     //@brief 真正的删除操作
 81     void _Delete( RBTreeNode *node );
 82 
 83     //@brief 专属红黑树的替换操作
 84     void _RB_Transplant( RBTreeNode *unode, RBTreeNode *vnode );
 85     
 86     //@brief 对删除操作的修复
 87     void _DeleteFixup( RBTreeNode *node );
 88 
 89     //@brief 后继
 90     RBTreeNode * _Successor( RBTreeNode *node );
 91 
 92     //@brief 前驱
 93     RBTreeNode * _Predecessor( RBTreeNode *node );
 94 
 95     //@brief Maximum
 96     RBTreeNode * _Maximum( RBTreeNode *node );
 97     
 98     //@brief Minimum
 99     RBTreeNode * _Minimum( RBTreeNode *node );
100 
101 
102 private:
103     //红黑树的数据成员
104     RBTreeNode    *m_pRoot;    //根结点
105     static RBTreeNode    *m_pNil;    //哨兵空结点
106 };
107 #endif//__RED_BLACK_TREE_

2)red_black_tree.cpp

  1 #include <iostream>
  2 #include <ctime>
  3 #include <cassert>
  4 #include <sstream>
  5 using namespace std;
  6 
  7 #include "red_black_tree.h"
  8 
  9 //静态成员变量初始化
 10 template<typename TKey, typename TValue>
 11 typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::m_pNil = NULL;
 12 
 13 template<typename TKey, typename TValue>
 14 RBTree<TKey, TValue>::RBTree() 
 15 {
 16     if ( !m_pNil ) {
 17         //叶结点是一个特殊的黑结点
 18         m_pNil = new RBTreeNode();
 19         m_pNil->Color = BLACK;
 20     }
 21     m_pRoot = m_pNil;
 22 }
 23 
 24 template<typename TKey, typename TValue>
 25 RBTree<TKey, TValue>::~RBTree()
 26 {
 27     _RecursiveReleaseNode( m_pRoot );
 28 }
 29 
 30 template<typename TKey, typename TValue>
 31 void RBTree<TKey, TValue>::_RecursiveReleaseNode( RBTreeNode *node )
 32 {
 33     if ( node->isValid() ) {
 34         _RecursiveReleaseNode( node->Left );
 35         _RecursiveReleaseNode( node->Right );
 36         delete node;
 37     }
 38 }
 39 
 40 template<typename TKey, typename TValue>
 41 bool RBTree<TKey, TValue>::Empty()
 42 {
 43     return !(m_pRoot->isValid());
 44 }
 45 
 46 //左旋
 47 template<typename TKey, typename TValue> 
 48 void RBTree<TKey, TValue>::_LeftRotate( RBTreeNode *x_node )
 49 {
 50     //assert
 51     if ( !(x_node->isValid() && x_node->Right->isValid()) )
 52         throw exception( "左旋操作要求对非哨兵进行操作,并且要求右孩子也不是哨兵" );
 53 
 54     RBTreeNode *y_node = x_node->Right;
 55 
 56     //以下三步的宗旨是用 y 替换 x,注意将 x 的Parent、Left、Right都换成 y 的
 57     // 1) x 和 y 分离 (补)
 58     x_node->Right = y_node->Left;
 59     if (y_node->Left != m_pNil)
 60         y_node->Left->Parent = x_node;
 61     
 62     // 2) 设置y->Parent (提)
 63     y_node->Parent = x_node->Parent;
 64     if (x_node->Parent == m_pNil)
 65         m_pRoot = y_node;
 66     else if (x_node->Parent->Left == x_node)
 67         x_node->Parent->Left = y_node;
 68     else
 69         x_node->Parent->Right = y_node;
 70 
 71     // 3) 设置y->Left (降)
 72     y_node->Left = x_node;
 73     x_node->Parent = y_node;
 74 }
 75 
 76 //右旋
 77 template<typename TKey, typename TValue> 
 78 void RBTree<TKey, TValue>::_RightRotate( RBTreeNode *x_node )
 79 {
 80     //assert
 81     if ( !(x_node->isValid() && x_node->Left->isValid()) )
 82         throw exception( "右旋操作要求对非哨兵进行操作,并且要求左孩子也不是哨兵" );
 83     RBTreeNode *y_node = x_node->Left;
 84 
 85     //以下三步的宗旨是用 y 替换 x,注意将 x 的Parent、Left、Right都换成 y 的
 86     // 1) x 和 y 分离 (补)
 87     x_node->Left = y_node->Right;
 88     if (y_node->Right != m_pNil)
 89         y_node->Right->Parent = x_node;
 90 
 91     // 2) 设置y->Parent (提)
 92     y_node->Parent = x_node->Parent;
 93     if (x_node->Parent == m_pNil)
 94         m_pRoot = y_node;
 95     else if (x_node->Parent->Right == x_node)
 96         x_node->Parent->Right = y_node;
 97     else
 98         x_node->Parent->Left = y_node;
 99 
100     // 3) 设置y->Left (降)
101     y_node->Right = x_node;
102     x_node->Parent = y_node;
103 }
104 
105 //搜索
106 template<typename TKey, typename TValue> 
107 typename RBTree<TKey, TValue>::RBTreeNode* RBTree<TKey, TValue>::Search( TValue const &value )
108 {
109     RBTreeNode *node = m_pRoot;
110     while( node != m_pNil && node->Value != value )
111         node = ((value < node->Value) ? node->Left:node->Right);
112     return node;
113 }
114 
115 //插入
116 template<typename TKey, typename TValue> 
117 bool RBTree<TKey, TValue>::Insert( TKey key, TValue value )
118 {
119     if ( Search(value)->isValid() )
120         //value 重复,添加失败
121         return false;
122     else {
123         //新添加的节点为红结点,left=right=nil
124         RBTreeNode *new_node = new RBTreeNode();
125         new_node->Key = key;
126         new_node->Value = value;
127         new_node->Color = RED;
128         new_node->Left = new_node->Right = m_pNil;
129     
130         //插入
131         _InsertRBTree(new_node);
132         //修复
133         _InsertFixup(new_node);
134         return true;
135     }
136 }
137 
138 //真正的插入:与二叉搜索树几乎一样
139 template<typename TKey, typename TValue> 
140 void RBTree<TKey, TValue>::_InsertRBTree( RBTreeNode *new_node )
141 {
142     RBTreeNode *current_node = m_pNil;
143     RBTreeNode *next_node = m_pRoot;
144 
145     //找到插入点
146     while ( next_node != m_pNil ) {
147         current_node = next_node;
148         next_node = ( new_node->Value < next_node->Value )? next_node->Left: next_node->Right;
149     }
150 
151     new_node->Parent = current_node;
152     if ( current_node == m_pNil ) //空树
153         m_pRoot = new_node;
154     else if ( new_node->Value < current_node->Value )
155         current_node->Left = new_node; //插入左子树
156     else
157         current_node->Right = new_node; //插入右子树
158 
159     //设置new_node-left-right = nil, color = red
160     new_node->Left = m_pNil;
161     new_node->Right = m_pNil;
162     new_node->Color = RED;    //插入结点为红色
163 }
164 
165 //插入修复
166 //new_node -> z, uncle_node -> y;
167 template<typename TKey, typename TValue> 
168 void RBTree<TKey, TValue>::_InsertFixup( RBTreeNode *new_node )
169 {
170 //////////////////////////////////////////////////////////////////////////
171 //啰嗦的写法
172 /*
173     while ( new_node->Parent->Color == RED ) {
174         RBTreeNode *uncle_node = new RBTreeNode();
175         if ( new_node->Parent == new_node->Parent->Parent->Left ) { //new的父结点为祖父结点的左孩子
176             uncle_node = new_node->Parent->Right; //uncle结点在右边
177 
178             if ( uncle_node->Color == RED ) { //case1: new 的叔结点为红色
179                 new_node->Color = BLACK;
180                 uncle_node->Color = BLACK;
181                 new_node->Parent->Color = RED;
182                 new_node = new_node->Parent->Parent;
183             }
184 
185             else if ( uncle_node->Color == BLACK && new_node->Parent->Right )  //case2: new 叔结点为黑色且new是一个右孩子
186                 _LeftRotate( new_node->Parent ); 
187 
188             new_node->Parent->Color = BLACK;    //case3: new 叔结点为黑色且new是左孩子
189             new_node->Parent->Parent->Color = RED;
190             _RightRotate( new_node->Parent->Parent ); 
191         }
192         else { //和上面对称的相同操作
193             ///
194         }    
195     }
196 */
197 //////////////////////////////////////////////////////////////////////////
198 //精炼的写法
199     while ( new_node->Parent->Color == RED ) {
200 
201         //标识new的父结点是否是祖父结点的左孩子
202         bool parent_is_left_child_flag = ( new_node->Parent == new_node->Parent->Parent->Left );
203         RBTreeNode *uncle_node = ( parent_is_left_child_flag ? new_node->Parent->Parent->Right: new_node->Parent->Parent->Left );
204 
205         if ( uncle_node->Color == RED ) { //case1: new 的叔结点为红色
206             new_node->Parent->Color = BLACK;  //!!!
207             uncle_node->Color = BLACK;
208             new_node->Parent->Parent->Color = RED; //!!!这两个地方写错了,tmd,还得老子改了大半天
209             new_node = new_node->Parent->Parent;
210         }
211 
212         else {
213             if ( new_node == ( parent_is_left_child_flag ? new_node->Parent->Right: new_node->Parent->Left ) ) {//case2: new 叔结点为黑色且new是一个右孩子
214                 new_node = new_node->Parent;
215                 parent_is_left_child_flag ? _LeftRotate( new_node ):_RightRotate( new_node );
216             }
217 
218             new_node->Parent->Color = BLACK;    //case3: new 叔结点为黑色且new是左孩子
219             new_node->Parent->Parent->Color = RED;
220             parent_is_left_child_flag ? _RightRotate( new_node->Parent->Parent ): _LeftRotate( new_node->Parent->Parent );
221         }
222     }
223     m_pRoot->Color = BLACK;
224 }
225 
226 //删除
227 template<typename TKey, typename TValue> 
228 bool RBTree<TKey, TValue>::Delete( TKey key )
229 {
230     //没有找到该结点
231     RBTreeNode *delete_node = Search( key );
232     if ( !(delete_node->isValid()) ) //!isValid()
233         return false;
234     else {
235         _Delete( delete_node );
236         return true;
237     }
238 }
239 
240 //真正的删除
241 //形如二叉搜索树的删除,只不过需要记录待删除节点的右孩子的颜色值
242 //delete_node -> z; min_node -> y; temp_node -> x
243 template<typename TKey, typename TValue> 
244 void RBTree<TKey, TValue>::_Delete( RBTreeNode *delete_node )
245 {
246     RBTreeNode *temp_node = delete_node;
247     int color = delete_node->Color; //记录待删除结点原来的颜色
248 
249     if ( delete_node->Left == m_pNil ) { //左孩子为空
250         temp_node = delete_node->Right;
251         _RB_Transplant( delete_node, delete_node->Right );
252     }
253     else if ( delete_node->Right == m_pNil ) {//右孩子为空
254         temp_node = delete_node->Left;
255         _RB_Transplant( delete_node, delete_node->Left );
256     }
257     else {
258         RBTreeNode *min_node = _Minimum( delete_node->Right ); //delete的后继结点min_node
259         temp_node = min_node->Right;
260         color = min_node->Color; //更新color
261 
262         if ( min_node->Parent == delete_node )
263             temp_node->Parent = min_node;
264 
265         else {
266             _RB_Transplant( min_node, min_node->Right );
267             min_node->Right = delete_node->Right;
268             min_node->Right->Parent = min_node;
269         }
270         _RB_Transplant( delete_node, min_node );
271         min_node->Left = delete_node->Left;
272         min_node->Left->Parent = min_node;
273         min_node->Color = delete_node->Color;
274     }
275     if ( color == BLACK )
276         _DeleteFixup( temp_node ); //template_node x
277 }
278 
279 //删除修复
280 template<typename TKey, typename TValue> 
281 void RBTree<TKey, TValue>::_DeleteFixup( RBTreeNode *node )
282 {
283     while ( node != m_pRoot && node->Color == BLACK ) {
284         //标识node是否是其父结点的左孩子
285         bool node_is_left_child_flag = ( node == node->Parent->Left );
286         //node的兄弟节点
287         RBTreeNode *brother = ( node_is_left_child_flag ? node->Parent->Right : node->Parent->Left );
288         
289         //case1 node的兄弟结点为红色,一次旋转操作变成case2
290         if ( brother->Color == RED ) { 
291             node->Parent->Color = RED;
292             brother->Color = BLACK;
293             node_is_left_child_flag ? _LeftRotate( node->Parent ):_RightRotate( node->Parent );
294             
295             //更新brother结点
296             brother = ( node_is_left_child_flag ? node->Parent->Right : node->Parent->Left );
297         }
298 
299         //case2 node 的兄弟结点为黑色,且brother两个孩子结点皆为黑色
300         if ( brother->Left->Color == BLACK && brother->Right->Color == BLACK ) { 
301             brother->Color = RED;
302             node = node->Parent; //node更新为上一层
303         }
304         
305         //case3 node的兄弟结点为黑色,且brother的左孩子为红色,右孩子为黑色
306         else {
307             if ( ( node_is_left_child_flag ? brother->Right->Color : brother->Left->Color ) == BLACK ) { 
308                 brother->Color = RED;
309                 //注意左右的不同
310                 ( node_is_left_child_flag ? brother->Left->Color : brother->Right->Color ) = BLACK;
311                 node_is_left_child_flag ? _RightRotate( brother ):_LeftRotate( brother );
312                 brother = ( node_is_left_child_flag ? node->Parent->Right:node->Parent->Left ); //更新brother结点 -> 变成case4
313             }
314             
315             //case4 node结点的兄弟结点为黑色,且brother 结点的右孩子为红色
316             brother->Color = /*node->Parent->Color*/RED; 
317             node->Parent->Color = BLACK;
318             
319             ( node_is_left_child_flag ? brother->Right->Color : brother->Left->Color ) = BLACK;
320             node_is_left_child_flag ? _LeftRotate( node->Parent ):_RightRotate( node->Parent );
321             
322             node = m_pRoot; //最后赋给root
323         }
324     }
325     //最后只需要简单置x为黑结点就可以,_root的改变已经由左右旋自动处理了
326     node->Color = BLACK;
327 }
328 
329 //RB替换操作
330 template<typename TKey, typename TValue> 
331 void RBTree<TKey, TValue>::_RB_Transplant( RBTreeNode *unode, RBTreeNode *vnode )
332 {
333     if ( unode->Parent == m_pNil )
334         m_pRoot = vnode;
335     else if ( unode->Parent->Left == unode )
336         unode->Parent->Left = vnode;
337     else
338         unode->Parent->Right = vnode;
339     vnode->Parent = unode->Parent; //!!!别漏了
340 }
341 
342 //显示
343 template<typename TKey, typename TValue> 
344 void RBTree<TKey, TValue>::Display() const
345 {
346     _Display( m_pRoot );
347     std::cout << std::endl;
348 }
349 
350 template<typename TKey, typename TValue> 
351 void RBTree<TKey, TValue>::_Display( RBTreeNode *node ) const
352 {
353 //     if ( node->isValid() ) {
354 //         cout << node->Value << " ";
355 //         if (node->Left->isValid())
356 //             _Display(node->Left);
357 //         if (node->Right->isValid())
358 //             _Display(node->Right);
359 //     }
360     if ( node->Parent == m_pNil ) 
361         cout << "root: " << node->Value << "( " << node->Color << " )" << endl;
362     else if ( node->Parent->Left == node )
363         cout << "left: " << node->Value << "( " << node->Color << " )" << " " << "parent: " << node->Parent->Value << "( " << node->Parent->Color << " )" << endl;
364     else cout << "right: " << node->Value << "( " << node->Color << " )" << " " << "parent: " << node->Parent->Value << "( " << node->Parent->Color << " )" << endl;
365     if ( node->Left->isValid() )
366         _Display(node->Left);
367     if ( node->Right->isValid() )
368         _Display(node->Right);
369 }
370 
371 //@brief 后继
372 template<typename TKey, typename TValue> 
373 typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::_Successor( RBTreeNode *node )
374 {
375     if(node->m_pRight)
376         return _GetMaximum(node);
377 
378     _Node *pTemp = node->m_pParent;
379     while (pTemp && node == pTemp->m_pRight ) {
380         node = pTemp;
381         pTemp = pTemp->m_pParent;
382     }
383     return pTemp;
384 }
385 
386 //@brief 前驱
387 template<typename TKey, typename TValue> 
388 typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::_Predecessor( RBTreeNode *node )
389 {
390     if (node->m_pLeft)
391         return _GetMinimum(node);
392 
393     _Node *pTemp = node->m_pParent;
394     while (pTemp && node == pTemp->m_pLeft) {
395         node = pTemp;
396         pTemp = pTemp->m_pParent;
397     }
398     return pTemp;
399 }
400 
401 //@brief Maximum
402 template<typename TKey, typename TValue> 
403 typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::_Maximum( RBTreeNode *node )
404 {
405     while( node->Right != m_pNil ) {
406         node = node->Right;
407     }
408     return node;
409 }
410 
411 //@brief Minimum
412 template<typename TKey, typename TValue> 
413 typename RBTree<TKey, TValue>::RBTreeNode * RBTree<TKey, TValue>::_Minimum( RBTreeNode *node )
414 {
415     while( node->Left != m_pNil ) {
416         node = node->Left;
417     }
418     return node;
419 }
420 
421 int main()
422 {
423     srand((unsigned)time(NULL));
424     RBTree<int, int> rbt;
425     int ninsert[] = {12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17};
426     //int ninsert[] = {3,7,12,10,14,15,16,17,21,19,20,23,26,41,30,28,38,35,39,47};
427     int n = sizeof(ninsert)/sizeof(ninsert[0]);
428 
429     //用随机值生成一棵二叉查找树
430     for ( int i = 0; i < n; ++i )
431     {
432         //int v = rand() % 100;
433         rbt.Insert( ninsert[i], ninsert[i] );
434         //rbt.Insert( i, i );
435     }
436     rbt.Display();
437     
438 //     for ( int i = 0; i < n; i ++)
439 //         rbt.Delete( ninsert[i] );
440 
441 //     删除所有的小奇数
442     for ( int i = 1; i < n; ++i )
443     {
444         if ( i % 2 == 1 /*&& i < 50*/ )
445         {
446             if ( rbt.Delete( i ) )
447             {
448                 cout << "Deleted [" << i << "]" << endl;
449             }
450         }
451     }
452     rbt.Display();
453 //         //删除所有的大偶数
454 //         for ( int i = 0; i < 100; ++i )
455 //         {
456 //             if ( i % 2 == 0 && i > 50 )
457 //             {
458 //                 if ( rbt.Delete( i ) )
459 //                 {
460 //                     cout << "Deleted [" << i << "]" << endl;
461 //                 }
462 //             }
463 //         }
464 //         rbt.Display();
465 
466     return 0;
467 }

参考资料:

《算法导论》第三版

《STL源码剖析》

July的博客:红黑树算法的逐步实现与层层分析

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2438 Turn the corner(三分查找)

托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,AC了一题,写法确实方便,还是我太弱了,漫漫AC路!各路大神,以后你们有啥好的简便写法...

2925
来自专栏木宛城主

PowerShell 获取Site Collection下被签出的文件

由于权限的设置,当文件被签出时导致别人不可见了,这对校验文件个数的人来说着实是件烦恼的事。幸好利用PowerShell,可以获取Site Collection下...

2017
来自专栏xingoo, 一个梦想做发明家的程序员

文件上传---动作条

  利用Apache commons fileupload上传文件,直接显示其完成的进度条。----示例代码源自《JAVA WEB王者归来》   1 首先要显示...

2548
来自专栏用户画像

jQuery validate

691
来自专栏码匠的流水账

java字符全角半角转换

951
来自专栏算法+

声音变调算法PitchShift(模拟汤姆猫) 附完整C++算法实现代码

上周看到一个变调算法,挺有意思的,原本计划尝试用来润色TTS合成效果的。 实测感觉还需要进一步改进,待有空再思考改进方案。 算法细节原文,移步链接: http:...

57710
来自专栏码匠的流水账

聊聊pg jdbc的queryTimeout及next方法

本文主要介绍一下pg jdbc statement的queryTimeout及resultSet的next方法

3341
来自专栏一个会写诗的程序员的博客

【Kotlin 反应式编程】第1讲 你好,Reactive Programming

【Kotlin 反应式编程】第1讲 你好,Reactive Programming

862

.NET中的密钥加密

本教程将演示如何通过System.Security.Cryptography在.NET Framework 1.1中实现对称加密/密钥加密。

6018
来自专栏24k

web3j调用合约的两种方式以及eth转账

1502

扫码关注云+社区

领取腾讯云代金券