【红黑树变色+旋转】

一. 红黑树规则

对于红黑树，举行变色+旋转处置惩罚，终究都是为了维持颜色+以下几条规则，只有颜色和规则维持住了，红黑树就维持住了最长路径的长度不高出最短路径的两倍。
规则：

• 根是黑的。
  
• 没有一连的红节点。
  
• 每条路径的黑色数量相称。
  

二. 环境一叔叔存在且为红

留意点：红黑树插入的节点都是红色的，因为在红黑树中动黑色节点是非常忌讳的，因为要维持每条路径黑色数量相称非常困难，所以插入的节点默认都是红色的。
当插入红色节点后：1.如果父亲为黑或者父亲不存在，结束，不须要任何处置惩罚。
2. 如果父亲存在且为红，由于插入节点为红，存在一连红节点，须要处置惩罚，可以肯定的是爷爷肯定是黑，因为插入节点前就是一棵红黑树了，既然父亲和爷爷颜色确定，重要看叔叔。
1.叔叔存在且为红

环境二.变色+旋旋

叔叔存在且为黑或者叔叔不存在都需变色+旋转，关键分析是左单旋，右单旋，照旧左右双旋，照旧右左双旋只要旋转后，就均衡了，直接结束，不须要向上更新
1. 变色+单旋

对于叔叔存在且为黑或不存在这种环境，不大概是因为直接插入红色节点导致一连红这种环境直接发生的，因为这发生了，原本就不是红黑树，肯定是由上述图一第一种环境处置惩罚更新上来导致的。
办理办法：curp->left, pg->left 左左右单旋g点+
p变黑，g变红。
同理：如果上述环境curp->right, pg->right，右右左单旋g点+p变黑，g变红
2.变色+双旋

对于这种环境：curp->right, pg->left,左右双旋，
将p左旋，g右旋，+ cur变黑+g变红。
同理：curp->left, pg->right, 右左双旋，将p右旋，g左旋，+cur变黑+g变红
总结单纯变色处置惩罚，须要不停向上更新至父亲不存在或者父亲为黑结束，旋转+变色处置惩罚完就均衡了直接结束。
一下是代码实现

1. bool Insert(const pair<K, V>& kv)
2.                 {
3.                         if (_root == nullptr)
4.                         {
5.                                 _root = new Node(kv);
6.                                 _root->_col = BLACK;        //根为黑色
7.                                 return true;
8.                         }
10.                         Node* parent = nullptr;
11.                         Node* cur = _root;
12.                         while (cur)
13.                         {
14.                                 if (cur->_kv.first < kv.first)
15.                                 {
16.                                         parent = cur;
17.                                         cur = cur->_right;
18.                                 }
19.                                 else if (cur->_kv.first > kv.first)
20.                                 {
21.                                         parent = cur;
22.                                         cur = cur->_left;
23.                                 }
24.                                 else
25.                                 {
26.                                         return false;
27.                                 }
28.                         }
30.                         cur = new Node(kv);
31.                         if (parent->_kv.first < kv.first)
32.                         {
33.                                 parent->_right = cur;
34.                         }
35.                         else
36.                         {
37.                                 parent->_left = cur;
38.                         }
39.                         cur->_parent = parent;
40.                         //父亲存在且为红，连续红节点，处理(如果父亲不存在管你红黑就结束了，如果为黑也结束了）
41.                         while (parent && parent->_col == RED)
42.                         {
43.                                 Node* grandfather = parent->_parent;  //算出爷爷，根据父亲为爷爷的左右，确定叔叔
44.                                 if (parent == grandfather->_left)
45.                                 {
46.                                         Node* uncle = grandfather->_right;
47.                                         //情况一：叔叔存在且为红 变色处理
48.                                         if (uncle && uncle->_col == RED)
49.                                         {
50.                                                 parent->_col = uncle->_col = BLACK;
51.                                                 grandfather->_col = RED;
52.                                                 //根节点保证为黑下面处理
54.                                                 //继续往上处理
55.                                                 cur = grandfather;
56.                                                 parent = cur->_parent;
57.                                         }
58.                                         //情况二：叔叔不存在/叔叔存在且为黑
59.                                         else
60.                                         {
61.                                                 //需要判别单旋还是左旋，确定cur的位置
62.                                                 //旋转+变色
63.                                                 if (cur == parent->_left)
64.                                                 {
65.                                                         //                g
66.                                                         //         p                u
67.                                                         //c
68.                                                         //左左右单旋
69.                                                         RotateR(grandfather);
70.                                                         parent->_col = BLACK;
71.                                                         grandfather->_col = RED;
72.                                                 }
73.                                                 else
74.                                                 {
75.                                                         //                g
76.                                                         //        p                u
77.                                                         //           c
78.                                                         //左右双旋+变色
79.                                                         RotateL(parent);
80.                                                         RotateR(grandfather);
81.                                                         cur->_col = BLACK;
82.                                                         grandfather->_col = RED;
83.                                                 }
84.                                                 break;        //只要旋转结束就平衡了结束
85.                                         }
86.                                 }
87.                                 else
88.                                 {
89.                                         Node* uncle = grandfather->_left;
90.                                         //情况一：叔叔存在且为红 变色处理
91.                                         if (uncle && uncle->_col == RED)
92.                                         {
93.                                                 parent->_col = uncle->_col = BLACK;
94.                                                 grandfather->_col = RED;
95.                                                 //根节点保证为黑下面处理
97.                                                 //继续往上处理
98.                                                 cur = grandfather;
99.                                                 parent = cur->_parent;
100.                                         }
101.                                         //情况二：叔叔不存在/叔叔存在且为黑
102.                                         else
103.                                         {
104.                                                 if (cur == parent->_right)
105.                                                 {
106.                                                         //                g
107.                                                         //        u                p
108.                                                         //                                c
109.                                                         RotateL(grandfather);
110.                                                         parent->_col = BLACK;
111.                                                         grandfather->_col = RED;
112.                                                 }
113.                                                 else
114.                                                 {
115.                                                         //                g
116.                                                         //        u                p
117.                                                         //                 c
118.                                                         //右左双旋
119.                                                         RotateR(parent);
120.                                                         RotateL(grandfather);
121.                                                         cur->_col = BLACK;
122.                                                         grandfather->_col = RED;
123.                                                 }
124.                                                 //只要旋转完了，就平衡结束了
125.                                                 break;
126.                                         }
127.                                 }
128.                         }
129.                         _root->_col = BLACK;        //变色没有处理根，无论怎么处理都保证根是黑的
130.                         return true;
131.                 }
133.                 void RotateL(Node* parent)
134.                 {
135.                         ++rotateSize;
136.                         Node* subR = parent->_right;
137.                         Node* subRL = subR->_left;
138.                         parent->_right = subRL;
139.                         if (subRL)
140.                                 subRL->_parent = parent;
141.                         subR->_left = parent;
142.                         Node* ppnode = parent->_parent;
143.                         parent->_parent = subR;
144.                         if (_root == parent)
145.                         {
146.                                 _root = subR;
147.                                 subR->_parent = nullptr;
148.                         }
149.                         else
150.                         {
151.                                 if (parent == ppnode->_left)
152.                                 {
153.                                         ppnode->_left = subR;
154.                                 }
155.                                 else
156.                                 {
157.                                         ppnode->_right = subR;
158.                                 }
159.                                 subR->_parent = ppnode;
160.                         }
161.                 }
162.                 void RotateR(Node* parent)
163.                 {
164.                         ++rotateSize;
165.                         Node* subL = parent->_left;
166.                         Node* subLR = subL->_right;
167.                         parent->_left = subLR;
168.                         if (subLR)
169.                                 subLR->_parent = parent;
170.                         subL->_right = parent;
171.                         Node* ppnode = parent->_parent;
172.                         parent->_parent = subL;
173.                         if (parent == _root)
174.                         {
175.                                 _root = subL;
176.                                 subL->_parent = nullptr;
177.                         }
178.                         else
179.                         {
180.                                 if (parent == ppnode->_left)
181.                                 {
182.                                         ppnode->_left = subL;
183.                                 }
184.                                 else
185.                                 {
186.                                         ppnode->_right = subL;
187.                                 }
188.                                 subL->_parent = ppnode;
189.                         }
190.                 }
191.                

复制代码

无论怎么方式处置惩罚完都须要包管根是黑的，最后加上

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。