数据结构：红黑树

前言

前面我们先容了AVL树来办理搜索二叉树不平衡的问题，本日我们带来一种新的办理方案，同时，这种办理方案在实践中比AVL树更常用，这种数据结构就是红黑树
红黑树的概念

   红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是靠近平衡的。
  概念还是很抽象，我们直接看图来理解红黑树

一览无余，红黑树嘛，每个节点要么是黑色，要么是赤色。
留意：红黑树并不像AVL树一样是绝对平衡的，红黑树是相对平衡的，红黑树通过让最长路径长度不超过最短路径长度的两倍来控制相对平衡。

---

红黑树的性子

   

• 每个结点不是赤色就是黑色
  
• 根节点是黑色的
  
• 假如一个节点是赤色的，则它的两个孩子结点是黑色的 （不能出现一连赤色节点）
  
• 对于每个结点，从该结点到其全部子女叶结点的简单路径上，均 包含相同数目的黑色结点（每条路径上黑色节点个数相同）
  
• 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
  

  我们来思考一下，为什么这几条性子就可以帮红黑树处于平衡状态呢？
在这些性子的限制下，我们可以发现：
最短路径：全部是黑色节点
最长路径：一黑一红交替出现
以是，最长路径不会超过最短路径的两倍，以是红黑树可以到达相对平衡

---

红黑树的节点(以K_V型为例）

红黑树的节点，我们依旧接纳三叉链
但是，我们不需要平衡因子，
我们需要引入颜色变量，
由于只有赤色和黑色，我们就直接使用枚举范例来表示颜色

1. enum Color
2. {
3.         RED,
4.         BLACK
5. };
7. template<class K,class V>
8. struct RBTreeNode
9. {
10.         RBTreeNode<K,V>* _left = nullptr;
11.         RBTreeNode<K,V>* _right = nullptr;
12.         RBTreeNode<K,V>* _parent = nullptr;
13.         Color _col = RED;
14.         pair<K, V> _value;
15.        
16.         RBTreeNode(const pair<K,V>& value)
17.                 :_value(value)
18.         {}
19. };

复制代码

---

红黑树的插入

在学习完了AVL树之后，再来理解红黑树的插入是非常简单的。
新插入节点颜色

在学习插入之前，我们来思考一个问题，新插入的节点，我们究竟给什么颜色呢？
给黑色还是赤色呢？
假如我们给黑色，那么我们就破坏了第四条性子
此时，新插入的节点的这条路径上的黑色节点数量多了一个，直接影响了整棵树，破坏性非常强
假如我们给赤色，那么我们就破坏了第三条性子
此时，只是影响了当前的这一棵子树，破坏性比上面的情况小
于是，我们选择坏处小的这种情况。
我们给新插入节点的颜色默以为赤色。（当然根节点除外）

---

插入

首先还是按照搜索二叉树的插入方法一样，大的往右走，小的往左走，然后连接上父亲节点。
处理完这一系列操作之后
我们就要像AVL树更新平衡因子一样，更新颜色了。
我们插入的是赤色节点，破坏了第三条性子，不能出现一连赤色节点，以是我们需要维护颜色。
   当我们需要调解的时候，一定是这种情况
cur = 红，parent = 红，grandparent = 黑
假如父亲不是红，就不需要调解，假如爷爷是红，那么早就该调解了。
  因此我们只需要思量爷爷的另一个节点的颜色即可，也就是叔叔节点的颜色
叔叔存在且为赤色（变色）

此时我们只需要调解颜色即可，我们将parent 和uncle都酿成黑色，把爷爷酿成赤色，
这样既办理了一连赤色节点的问题，又没有给该路径增加新节点
调解后酿成了下图

此时爷爷变红了，需要担心爷爷的父亲是否也是赤色，那么就需要向上继承调解，直到爷爷的父亲不是赤色节点为止。

留意：根节点除外，当爷爷的父亲不存在的时候，就到了根节点，根节点始终要保持黑色，我们可以在出循环之后，给根节点置为黑色，就可以避免在循环内额外处理这种情况。

---

叔叔不存在或叔叔为黑色（旋转 + 变色）

（1）单旋

   此时单纯的变色已经不可以大概办理问题了，需要额外引入旋转
看左边这个图，出现了一连的赤色节点，需要调解了，分析左边高了，我们就需要通过旋转来控制平衡，
这里的旋转和AVL树的旋转操作一样，
这里进行右单旋即可
右单旋之后，酿成了右图
旋转之后，将父亲置为黑色，爷爷置为赤色
即消除了一连赤色节点，又没有新增每条路径上的黑色节点。
  左单旋也是一样，就不多赘述了。
(2)双旋

双旋和单旋的区别在于，cur究竟是在parent的左边还是右边
假如在左边就是完全失衡，只需要右单旋，假如在右边则偏了，需要先左单旋成完全失衡，再右单旋进行调解。
像第一幅图，cur在parent的右边，就需要进行双旋，先一parent为root，进行左单旋，
就酿成了第二幅图，此时以grandparent为root进行右单旋即可
就酿成了第三幅图
此时对颜色的调解为
cur需要酿成黑色，grandparent需要酿成赤色（图中出现了一点问题，信任读者能看出来）

---

对于旋转，我们在旋转完成之后的子树的根节点就是黑色，不大概出现一连的赤色节点，以是不需要继承向上调解，我们也就可以跳出循环，直接break掉。
另外另一个方向的双旋也是类似，这里也不多赘述了

---

代码

1. #include <iostream>
3. using namespace std;
5. namespace bit
6. {
7.         enum Color
8.         {
9.                 RED,
10.                 BLACK
11.         };
13.         template<class K,class V>
14.         struct RBTreeNode
15.         {
16.                 RBTreeNode<K,V>* _left = nullptr;
17.                 RBTreeNode<K,V>* _right = nullptr;
18.                 RBTreeNode<K,V>* _parent = nullptr;
19.                 Color _col = RED;
20.                 pair<K, V> _value;
21.                 RBTreeNode(const pair<K,V>& value)
22.                         :_value(value)
23.                 {}
24.         };
26.         template<class K,class V>
27.         class RBTree
28.         {
29.                 typedef RBTreeNode<K, V> Node;
30.         private:
31.                 Node* _root = nullptr;
33.                 void RotateR(Node* parent)
34.                 {
35.                         Node* subL = parent->_left;
36.                         Node* subLR = subL->_right;
38.                         Node* pparent = parent->_parent;
40.                         parent->_left = subLR;
41.                         if (subLR)
42.                                 subLR->_parent = parent;
44.                         subL->_right = parent;
45.                         parent->_parent = subL;
47.                         if (pparent == nullptr)
48.                         {
49.                                 _root = subL;
50.                                 subL->_parent = nullptr;
51.                         }
52.                         else
53.                         {
54.                                 subL->_parent = pparent;
55.                                 if (pparent->_left == parent)
56.                                 {
57.                                         pparent->_left = subL;
58.                                 }
59.                                 else
60.                                 {
61.                                         pparent->_right = subL;
62.                                 }
63.                         }
65.                 }
67.                 void RotateL(Node* parent)
68.                 {
69.                         Node* subR = parent->_right;
70.                         Node* subRL = subR->_left;
71.                         Node* pparent = parent->_parent;
73.                         parent->_right = subRL;
74.                         if (subRL)
75.                                 subRL->_parent = parent;
77.                         subR->_left = parent;
78.                         parent->_parent = subR;
80.                         if (pparent == nullptr)
81.                         {
82.                                 _root = subR;
83.                                 subR->_parent = nullptr;
84.                         }
85.                         else
86.                         {
87.                                 subR->_parent = pparent;
88.                                 if (pparent->_left == parent)
89.                                 {
90.                                         pparent->_left = subR;
91.                                 }
92.                                 else
93.                                 {
94.                                         pparent->_right = subR;
95.                                 }
96.                         }
97.                 }
99.                 void inorder(Node* root)
100.                 {
101.                         if (root == nullptr)
102.                                 return;
104.                         inorder(root->_left);
105.                         cout << root->_value.first << ":" << root->_value.second << endl;
106.                         inorder(root->_right);
107.                 }
109.         public:
110.                 void InOrder()
111.                 {
112.                         inorder(_root);
113.                 }
115.                 bool insert(const pair<K, V>& value)
116.                 {
117.                         if (_root == nullptr)//空树就直接申请节点，将根节点处理成黑色
118.                         {
119.                                 _root = new Node(value);
120.                                 _root->_col = BLACK;
121.                                 return true;
122.                         }
124.                         Node* cur = _root;
125.                         Node* parent = nullptr;
126.                         while (cur)
127.                         {
128.                                 if (value.first > cur->_value.first)
129.                                 {
130.                                         parent = cur;
131.                                         cur = cur->_right;
132.                                 }
133.                                 else if (value.first < cur->_value.first)
134.                                 {
135.                                         parent = cur;
136.                                         cur = cur->_left;
137.                                 }
138.                                 else
139.                                 {
140.                                         return false;//已经存在就插入失败
141.                                 }
142.                         }
144.                         cur = new Node(value);
145.                         cur->_parent = parent;
147.                         if (value.first > parent->_value.first)
148.                         {
149.                                 parent->_right = cur;
150.                         }
151.                         else
152.                         {
153.                                 parent->_left = cur;
154.                         }
156.                         while (parent && parent->_col == RED)
157.                         {
158.                                 Node* grandparent = parent->_parent;
159.                                 if (parent == grandparent->_left)//parent在左侧
160.                                 {
161.                                         Node* uncle = grandparent->_right;
163.                                         if (uncle && uncle->_col == RED)//叔叔存在且为红
164.                                         {
165.                                                 parent->_col = uncle->_col = BLACK;
166.                                                 grandparent->_col = RED;
167.                                                 cur = grandparent;
168.                                                 parent = cur->_parent;
169.                                         }
170.                                         else//叔叔不存在或者叔叔为黑色，则进行旋转 + 变色
171.                                         {
172.                                                 if (cur == parent->_left)//进行右单旋即可
173.                                                 {
174.                                                         RotateR(grandparent);
175.                                                         parent->_col = BLACK;
176.                                                         grandparent->_col = RED;
177.                                                 }
178.                                                 else
179.                                                 {
180.                                                         RotateL(parent);
181.                                                         RotateR(grandparent);
182.                                                         cur->_col = BLACK;
183.                                                         grandparent->_col = RED;
184.                                                 }
186.                                                 break;
187.                                         }
188.                                 }
189.                                 else//parent在右侧
190.                                 {
191.                                         Node* uncle = grandparent->_left;
193.                                         if (uncle && uncle->_col == RED)//叔叔存在且为红
194.                                         {
195.                                                 parent->_col = uncle->_col = BLACK;
196.                                                 grandparent->_col = RED;
197.                                                 cur = grandparent;
198.                                                 parent = cur->_parent;
199.                                         }
200.                                         else//叔叔不存在或者叔叔为黑色
201.                                         {
202.                                                 if (cur == parent->_right)
203.                                                 {
204.                                                         RotateL(grandparent);
205.                                                         parent->_col = BLACK;
206.                                                         grandparent->_col = RED;
207.                                                 }
208.                                                 else
209.                                                 {
210.                                                         RotateR(parent);
211.                                                         RotateL(grandparent);
212.                                                         cur->_col = BLACK;
213.                                                         grandparent->_col = RED;
214.                                                 }
215.                                                 break;
216.                                         }
218.                                 }
219.                         }
221.                         _root->_col = BLACK;
223.                         return true;
224.                 }
226.         };
227. }

复制代码

---

关于红黑树的删除，这里就不进行解说了，感兴趣的同砚可以去看看算法导论和殷人昆老师的数据结构课本，内里可以找到答案。