C++（初阶）（十九）——红黑树

红黑树


  
概念

红⿊树是⼀棵⼆叉搜索树。它的每个结点增加⼀个存储位来表示结点的颜⾊，可以是红色大概玄色（并不会出现第三种颜色）。
通过对结点颜色特殊的规则举行束缚，红黑树确保没有任何⼀条路径会比其他路径长出2倍，即保证最长路径（一黑一红）<= 最短路径*2（全黑），因此红黑树是靠近均衡的。
规则

1，每个结点不是红色就是玄色。
2，根结点是玄色的。
3，如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是玄色的，也就是说任意⼀条路径不会有连续的红色结点。
4，对于任意⼀个结点，从该结点到其所有空结点（NULL）的简朴路径上，均包含相同数量的玄色结点。
5，最长路径（一黑一红）<= 最短路径*2（全黑）。
阐明：《算法导论》等册本上补充了⼀条每个叶⼦结点(NIL)都是玄色的规则。他这⾥所指的叶⼦结点 不是传统的意义上的叶⼦结点，⽽是我们说的空结点，有些册本上也把NIL叫做外部结点。NIL是为了 ⽅便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道 ⼀下这个概念即可
实现

结点

1. // 枚举值表⽰颜⾊
2. enum Colour
3. {
4.     RED,
5.     BLACK
6. };
8. // 这⾥我们默认按key_value结构实现
9. template<class K, class V>
10. struct RBTreeNode
11. {
12.     pair<K, V> _kv;
13.     RBTreeNode<K, V>* _left;
14.     RBTreeNode<K, V>* _right;
15.     //这⾥更新控制平衡也要加⼊parent指针
16.     RBTreeNode<K, V>* _parent;
17.     Colour _col;
18.     //构造
19.     RBTreeNode(const pair<K, V>& kv)
20.         :_kv(kv)
21.         , _left(nullptr)
22.         , _right(nullptr)
23.         , _parent(nullptr)
24.         , _col(BLACK)
25.     {
26.     }
27. };

复制代码

插入

起首实现最简朴的插入操作。
1，起首判断是否是空树，因为空树也是红黑树。如果是空树，创建新节点，颜色是玄色（根节点必须是玄色），返回即可。
2，查找我们数据应该插入的位置，查找规则和二叉搜索树一样。比当前结点大，再去和右孩子的结点比较；比当前结点小，再去和左孩子的结点比较；即大就向右走，小就向左走，直到找到空，实行插入操作。
3，不是空树，创建新增结点，默认颜色是红色。为什么不给玄色，细致分析红黑树的规则发现：如果新增结点是玄色的话，那么就可能会粉碎其他简朴路径上玄色结点数量，造成简朴路径玄色结点的数量不相等。所以默认是红色结点，这样更方便。
那是否可以将全部结点都设置为玄色呢？按照红黑树的规则来看，逻辑上没有问题，但是这样的红黑树就失去了原本意义，全部都是玄色结点和二叉搜索树没有区别，而且还浪费了存储颜色的额外空间。
4，最简朴的情况是，新节点的父亲结点是玄色，则插入成功后就结束。
但是如果父亲结点是红色，那么插入新节点后就需要举行变色处理，缘故原由是红黑树不会存在连续的红色结点，变色处理稍微麻烦，放到后边位置详细阐明。
参考代码：

1. template<class K, class V>
2. class RBTree
3. {
4.         typedef RBTreeNode<K, V> Node;
5. public:
6.         //插入
7.         bool Insert(const pair<K, V>& kv)
8.         {
9.                 if (_root == nullptr)
10.                 {
11.                         _root = new Node(kv);
12.                         return true;
13.                 }
15.                 //记录cur的父结点
16.                 Node* parent = nullptr;
17.                 Node* cur = _root;
18.                 while (cur)
19.                 {
20.                         if (cur->_kv.first < kv.first)
21.                         {
22.                                 parent = cur;
23.                                 cur = cur->_right;
24.                         }
25.                         else if (cur->_kv.first > kv.first)
26.                         {
27.                                 parent = cur;
28.                                 cur = cur->_left;
29.                         }
30.                         else
31.                         {
32.                                 return false;
33.                         }
34.                 }
36.                 //新增结点，初始给红色
37.                 cur = new Node(kv);
38.                 cur->_col = RED;
39.                 if (parent->_kv.first < kv.first)
40.                 {
41.                         parent->_right = cur;
42.                 }
43.                 else
44.                 {
45.                         parent->_left = cur;
46.                 }
47.                 cur->_parent = parent;
49.                 return true;
50.         }
51.         private:
52.                 Node* _root = nullptr;
53. };

复制代码

变色

前面分析过，如果新节点的父亲结点存在且为红色，那么需要对先人结点举行变色。
但是变色依旧有多种情况，需要分别讨论。
为了方便利用缩写展示：g代表grandfather，p代表parent，u代表uncle，c代表cur即新结点。
1，

• 父亲结点存在且为红色
  
• 此时的父亲结点是爷爷结点的左孩子
  
• 叔叔结点存在而且为红色
  

此时颠末分析得到，我们需要对父亲结点举行变色处理，以下是参考过程：

• 将父亲和叔叔结点颜色变黑，爷爷结点颜色变红
  
• 注意：为了防止此处将根结点也变为红色，所以在末了一处_root->_col = RED
  
• 如果此时符合红黑树的规则，那么即可结束，反之向上更新结点，直到结束。
  

1. //更新结点位置，向上更新
2. cur = grandfather;
3. parent = cur->_parent;

复制代码

2，

• 父亲结点存在且为红色
  
• 此时的父亲结点是爷爷结点的左孩子
  
• 叔叔结点不存在大概存在且为玄色
  

此时需要举行变色+旋转处理。
但是旋转时又有所差异：如果cur是parent的左孩子（如下图），需要以grandfather为旋转点举行右单旋；

如果cur是parent的右孩子（如下图），需要先以parent为旋转点左单旋，再以grandfather为旋转点举行右单旋的左右双旋，末了要记得将旋转后的cur改为玄色，grandfather改为红色。

3，

• 父亲结点存在且为红色
  
• 此时的父亲结点是爷爷结点的右孩子
  
• 叔叔结点存在且为红色
  

与情况1雷同不再赘述。
4，

• 父亲结点存在且为红色
  
• 此时的父亲结点是爷爷结点的右孩子
  
• 叔叔结点不存在大概存在且为玄色
  

与情况2雷同不再赘述。
变色参考代码：

1.                 //变色处理
2.                 while (parent && parent->_col == RED)
3.                 {
4.                         Node* grandfather = parent->_parent;
5.                         //  g
6.                         //p   u
7.                         if (parent == grandfather->_left)
8.                         {
9.                                 Node* uncle = grandfather->_right;
10.                                 //叔叔结点存在，并且为红色
11.                                 if (uncle && uncle->_col == RED)
12.                                 {
13.                                         //将父亲和叔叔结点颜色变黑，爷爷结点颜色变红
14.                                         //为了防止此处将根结点也变为红色，所以在最后一处_root->_col = RED
16.                                         parent->_col = uncle->_col = BLACK;
17.                                         grandfather->_col = RED;
18.                                         //更新结点位置，向上更新
19.                                         cur = grandfather;
20.                                         parent = cur->_parent;
21.                                 }
22.                                 //叔叔结点不存在，或者存在并且为黑色
23.                                 //变色+旋转
24.                                 else
25.                                 {
26.                                         //    g
27.                                         //  p   u
28.                                         //c
29.                                         if (cur == parent->_left)
30.                                         {
31.                                                 RotateR(grandfather);
32.                                                 parent->_col = BLACK;
33.                                                 grandfather->_col = RED;
34.                                         }
35.                                         //cur == parent->_right
36.                                         else
37.                                         {
38.                                                 //    g
39.                                                 //  p   u
40.                                                 //    c
41.                                                 //双旋
42.                                                 RotateL(parent);
43.                                                 RotateR(grandfather);
44.                                                 cur->_col = BLACK;
45.                                                 grandfather->_col = RED;
46.                                         }
47.                                         break;
48.                                 }
49.                         }
51.                         //    g
52.                          //  u   p
53.                         //parent == grandfather->_right
54.                         else
55.                         {
56.                                 Node* uncle = grandfather->_left;
57.                                 //叔叔结点存在，并且为红色
58.                                 if (uncle && uncle->_col == RED)
59.                                 {
60.                                         //将父亲和叔叔结点颜色变黑，爷爷结点颜色变红
61.                                         //为了防止此处将根结点也变为红色，所以在最后一处_root->_col = RED
63.                                         parent->_col = uncle->_col = BLACK;
64.                                         grandfather->_col = RED;
65.                                         //更新结点位置，向上更新
66.                                         cur = grandfather;
67.                                         parent = cur->_parent;
68.                                 }
69.                                 //叔叔结点不存在，或者存在并且为黑色
70.                                 //变色+旋转
71.                                 else
72.                                 {
73.                                         //    g
74.                                         //  u   p
75.                                         //                   c
76.                                         if (cur == parent->_right)
77.                                         {
78.                                                 RotateL(grandfather);
79.                                                 parent->_col = BLACK;
80.                                                 grandfather->_col = RED;
81.                                         }
82.                                         //cur == parent->_left
83.                                         else
84.                                         {
85.                                                 //    g
86.                                                 //  p   u
87.                                                 //    c
88.                                                 //双旋
89.                                                 RotateR(parent);
90.                                                 RotateL(grandfather);
91.                                                 cur->_col = BLACK;
92.                                                 grandfather->_col = RED;
93.                                         }
94.                                         break;
95.                                 }
96.                         }
97.                 }
98.                 _root->_col = BLACK;

复制代码

查找

查找很简朴，与二叉搜索树的查找规则一样。
即要查找的cur结点的值大于根结点就向右走，比当前结点小就向左走，直到查找到大概走到空为止。
查找参考代码

1. //查找
2. Node* Find(const K& key)
3. {
4.     Node* cur = _root;
5.     while (cur)
6.     {
7.         if (cur->_kv.first < key)
8.         {
9.             cur = cur->_right;
10.         }
11.         else if (cur->_kv.first > key)
12.         {
13.             cur = cur->_left;
14.         }
15.         else
16.         {
17.             return cur;
18.         }
19.     }
20.     return nullptr;
21. }

复制代码

遍历

因为红黑树是二叉搜索树，所以利用中序遍历即可。

1. //中序遍历
2. void _InOrder(Node* root)
3. {
4.     if (root == nullptr)
5.     {
6.         return;
7.     }
8.     _InOrder(root->_left);
9.     cout << root->_kv.first << " ";
10.     _InOrder(root->_right);
11. }

复制代码

红黑树查抄

对红黑树查抄时，可以从红黑树的规则入手。
1，每个结点不是红色就是玄色。
2，根结点是玄色的。
3，如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红色结点。
4，对于任意⼀个结点，从该结点到其所有NULL结点的简朴路径上，均包含相同数量的⿊⾊结点。
对于规则1，我们在实现时，利用的就是红色和玄色的罗列，不可能出现其他颜色。
对于规则2，也很好判断，加一句判断语句即可。
对于规则3，前序遍历查抄，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来查抄⽗亲的颜⾊就⽅便多了。
对于规则4，前序遍历，遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就盘算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点 数量作为参考值，依次⽐较即可。

1. bool Check(Node* root, int blackNum, const int refNum)
2. {
3.         if (root == nullptr)
4.         {
5.                 //前序遍历⾛到空时，意味着⼀条路径⾛完了
6.                 //cout << blackNum << endl;
7.                 if (refNum != blackNum)
8.                 {
9.                         cout << "存在⿊⾊结点的数量不相等的路径" << endl;
10.                         return false;
11.                 }
13.                 return true;
14.         }
16.         //因为孩子结点可能有两个，也可能不存在，所以检查父亲结点更方便
17.         if (root->_col == RED && root->_parent->_col == RED)
18.         {
19.                 cout << root->_kv.first << "存在连续的红色结点" << endl;
20.                 return false;
21.         }
23.         if (root->_col == BLACK)
24.         {
25.                 ++blackNum;
26.         }
28.         return Check(root->_left, blackNum, refNum)
29.                 && Check(root->_right, blackNum, refNum);
30. }
32. bool IsBalance()
33. {
34.         //首先，如果是空树也是红黑树
35.         if (_root == nullptr)
36.         {
37.                 return true;
38.         }
39.         //再者，如果根结点是红色，不是红黑树
40.         if (_root->_col == RED)
41.         {
42.                 return false;
43.         }
45.         //剩余情况，需要依照参考值判断
46.         //参考值
47.         int refNum = 0;
48.         Node* cur = _root;
49.         while (cur)
50.         {
51.                 if (cur->_col == BLACK)
52.                 {
53.                         ++refNum;
54.                 }
55.                 cur = cur->_left;
56.         }
58.         return Check(_root, 0, refNum);
59. }

复制代码

完备代码

https://gitee.com/any10/c_plus_plus/blob/master/2025c%2B%2B/RBTree_5_5/RBTree.h