算法导论第十三章 红黑树
写在前面：这一章真的把我害惨了，之前至少尝试看过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源码剖析》
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2015-10-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
相关产品与服务
容器服务
腾讯云容器服务（Tencent Kubernetes Engine, TKE）基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务，覆盖 Serverless、边缘计算、分布式云等多种业务部署场景，业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者，主导开源项目Crane，全面助力客户实现资源优化、成本控制。
腾讯云开发者
