【C++】红黑树

前言：

   AVL树是二叉平衡搜索树，红黑树是基于AVL树的改造，是基于旋转的次数的减少。
  红黑树简介

红黑树的性质

• 每个结点不是红色就是黑色
  
• 根节点是黑色的
  
• 假如一个节点是红色的，则它的两个孩子结点是黑色的
  
• 对于每个结点，从该结点到其全部后代叶结点的简朴路径上，均 包罗相同数目的黑色结点
  
• 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
  

红黑树操作

红黑树是一种自平衡的二叉搜索树，它通过在每个节点上添加颜色属性（红色或黑色）并遵循特定的规则来保持树的平衡，从而包管了插入、删除和查找操作的对数时间复杂度。
在C++中实现红黑树通常涉及以下步调：

• 定义节点结构，包罗数据、颜色、左右子节点指针等。
  
• 实现红黑树的基本操作，如插入、删除、左旋、右旋、颜色翻转等。
  
• 维护红黑树的性质，确保在每次插入或删除后通过一系列旋转和颜色调解操作来规复平衡。
  

红黑树的实现

存储结构

• 整体的存贮结构类似于AVL树，AVL实现平衡的需要平衡因子_bf
  
• 红黑树的节点定义不是红色节点就是黑色节点，根据颜色的区分并且包管红红黑树的性质。
  

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

复制代码

红黑树的插入、

• 整体的思想和BST和AVL树是一样的左边小右边大
  

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.     }
9.     Node* parent = nullptr;
10.     Node* cur = _root;
11.     while (cur)
12.     {
13.         if (kv.first > cur->_kv.first)
14.         {
15.             parent = cur;
16.             cur = cur->_right;
17.         }
18.         else if (kv.first < cur->_kv.first)
19.         {
20.             parent = cur;
21.             cur = cur->_left;
22.         }
23.         else
24.         {
25.             return false;
26.         }
27.     }
29.     cur = new Node(kv);
30.     cur->_col = RED;
32.     if (kv.first < parent->_kv.first)
33.     {
34.         parent->_left = cur;
35.     }
36.     else
37.     {
38.         parent->_right = cur;
39.     }
40.     cur->_parent = parent;、
41.     //调账
42.   ...
43. }

复制代码

调解（旋转）

• 红黑树的底层类似于AVL，仅仅是旋转次数变少，但是时间复杂度依旧是O（lgN）
  

左旋

1. void RotateL(Node* parent)
2. {
4.         Node* cur = parent->_right;
6.         Node* curleft = cur->_left;
8.         parent->_right = curleft;
10.         if (curleft)
11.         {
12.                 curleft->_parent = parent;
13.         }
15.         cur->_left = parent;
17.         Node* ppnode = parent->_parent;
19.         parent->_parent = cur;
21.         if (parent == _root)
22.         {
23.                 _root = cur;
24.                 cur->_parent = nullptr;
25.         }
26.         else
27.         {
28.                 if (ppnode->_left == parent)
29.                 {
30.                         ppnode->_left = cur;
31.                 }
32.                 else
33.                 {
34.                         ppnode->_right = cur;
35.                 }
37.                 cur->_parent = ppnode;
38.         }
39. }

复制代码

右旋

1. void RotateR(Node* parent)
2. {
3.         Node* cur = parent->_left;
4.         Node* curright = cur->_right;
6.         parent->_left = curright;
8.         if (curright)
9.         {
10.                 curright->_parent = parent;
11.         }
13.         cur->_right = parent;
15.         Node* ppnode = parent->_parent;
17.         parent->_parent = cur;
19.         if (ppnode == nullptr)
20.         {
21.                 _root = cur;
22.                 cur->_parent = nullptr;
23.         }
24.         else
25.         {
26.                 if (ppnode->_left == parent)
27.                 {
28.                         ppnode->_left = cur;
29.                 }
30.                 else
31.                 {
32.                         ppnode->_right = cur;
33.                 }
35.                 cur->_parent = ppnode;
36.         }
38. }

复制代码

导致红黑树的不平衡缘故原由

• 红黑树不可以连续个连续的节点是红色
  
• 包管每一个路径黑色节点数目是一样的（根据这个条件，我们要插入红色节点）
  

环境一

• u节点存在，并且是红色
  

环境二

• u节点不存在或者u节点为黑色
  

如何包管红黑树平衡

• 我们需要寻找parent的节点的兄弟节点定义为uncle，举行判断，空，黑，红。
  
• 假如是红色节点，将parent和uncle节点的颜色转换为黑色，继续向上调解
  
• 假如节点不存在或者为黑的环境下，举行旋转，调解节点颜色。
  

1. while (parent && parent->_col == RED)
2. {
3.     Node* grandparent = parent->_parent;
4.     if (parent == grandparent->_left)
5.     {
6.         Node* uncle = grandparent->_right;
7.         if (uncle && uncle->_col == RED)
8.         {
9.             parent->_col = uncle->_col = BLACK;
10.             grandparent->_col = RED;
11.             cur = grandparent;
12.             parent = cur->_parent;
13.         }
14.         else//uncle is not or black
15.         {
16.             if (cur == parent->_left)
17.             {
18.                 RotateR(grandparent);
19.                 grandparent->_col = RED;
20.                 parent->_col = BLACK;
21.             }
22.             else
23.             {
24.                 RotateL(parent);
25.                 RotateR(grandparent);
26.                 grandparent->_col = RED;
27.                 cur->_col = BLACK;
28.             }
29.             break;
30.         }
31.     }
32.     else//parent == grandparent->_right
33.     {
34.         Node* uncle = grandparent->_left;
36.         if (uncle && uncle->_col == RED)
37.         {
38.             grandparent->_col = RED;
39.             parent->_col = uncle->_col= BLACK;
40.             cur = grandparent;
41.             parent = cur->_parent;
42.         }
43.         else
44.         {
45.             if (cur == parent->_right)
46.             {
47.                 RotateL(grandparent);
48.                 parent->_col = BLACK;
49.                 grandparent->_col = RED;
50.             }
51.             else
52.             {
53.                 RotateR(parent);
54.                 RotateL(grandparent);
55.                 cur->_col = BLACK;
56.                 grandparent->_col = RED;
57.             }
58.         }
59.         break;
60.     }
61. }

复制代码

红黑树平衡的验证

• 根节点不需要举行验证直接返回就好
  
• 根节点假如是红色的节点可以举行返回。包管根节点是黑色的
  
• 红黑树的特点就是每一个路径的黑色节点数目是一样的。这时候就需要查抄黑色节点的数目
  

1. bool is_balance(Node* root)
2. {
3.     if (root == nullptr)
4.     {
5.         return true;
6.     }
8.     if (root->_col == RED)
9.     {
10.         return false;
11.     }
12.     int stdnum = 0;
13.     Node* cur = root;
14.     while (cur)
15.     {
16.         if (cur->_col == BLACK)
17.         {
18.             ++stdnum;
19.         }
20.         cur = cur->_left;
21.     }
23.     return Checknum(root, 0, stdnum);
24. }

复制代码

查抄黑色节点

• 使用传值调用，递归实现
  
• 走到根节点举行判断，假如是和标准相等的环境下，返回true。
  

1. bool Checknum(Node* root, int blacknum, int stdnum)
2. {
3.     if (root == nullptr)
4.     {
5.         if (blacknum != stdnum)
6.         {
7.             return false;
8.         }
9.         return true;
10.     }
12.     if (root->_col == BLACK)
13.     {
14.         ++blacknum;
15.     }
17.     return Checknum(root->_left, blacknum, stdnum)
18.         && Checknum(root->_right, blacknum, stdnum);
19. }

复制代码

源码

1. #pragma once
4. #include<iostream>
5. #include<assert.h>
6. #include<utility>
8. using namespace std;
10. namespace RBTree
11. {
12.         enum Colour
13.         {
14.                 RED,
15.                 BLACK
16.         };
17.         template<class K, class V>
18.         class RBTreeNode
19.         {
20.         public:
21.                 RBTreeNode<K, V>* _left;
22.                 RBTreeNode<K, V>* _right;
23.                 RBTreeNode<K, V>* _parent;
24.                 pair<K, V> _kv;
25.                 Colour _col;
27.                 RBTreeNode(const pair<K, V>& kv)
28.                         :_left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv)
29.                 {}
30.         };
32.         template<class K, class V>
33.         class RBTree
34.         {
35.                 typedef RBTreeNode<K, V> Node;
37.         public:
38.                 bool is_balance()
39.                 {
40.                         return is_balance(_root);
41.                 }
43.                 bool Checknum(Node* root, int blacknum, int stdnum)
44.                 {
45.                         if (root == nullptr)
46.                         {
47.                                 if (blacknum != stdnum)
48.                                 {
49.                                         return false;
50.                                 }
51.                                 return true;
52.                         }
54.                         if (root->_col == BLACK)
55.                         {
56.                                 ++blacknum;
57.                         }
59.                         return Checknum(root->_left, blacknum, stdnum)
60.                                 && Checknum(root->_right, blacknum, stdnum);
61.                 }
62.                 bool is_balance(Node* root)
63.                 {
64.                         if (root == nullptr)
65.                         {
66.                                 return true;
67.                         }
69.                         if (root->_col == RED)
70.                         {
71.                                 return false;
72.                         }
73.                         int stdnum = 0;
74.                         Node* cur = root;
75.                         while (cur)
76.                         {
77.                                 if (cur->_col == BLACK)
78.                                 {
79.                                         ++stdnum;
80.                                 }
81.                                 cur = cur->_left;
82.                         }
84.                         return Checknum(root, 0, stdnum);
85.                 }
86.                 bool insert(const pair<K, V>& kv)
87.                 {
88.                         if (_root == nullptr)
89.                         {
90.                                 _root = new Node(kv);
91.                                 _root->_col = BLACK;
92.                                 return true;
93.                         }
94.                         Node* parent = nullptr;
95.                         Node* cur = _root;
96.                         while (cur)
97.                         {
98.                                 if (kv.first > cur->_kv.first)
99.                                 {
100.                                         parent = cur;
101.                                         cur = cur->_right;
102.                                 }
103.                                 else if (kv.first < cur->_kv.first)
104.                                 {
105.                                         parent = cur;
106.                                         cur = cur->_left;
107.                                 }
108.                                 else
109.                                 {
110.                                         return false;
111.                                 }
112.                         }
114.                         cur = new Node(kv);
115.                         cur->_col = RED;
117.                         if (kv.first < parent->_kv.first)
118.                         {
119.                                 parent->_left = cur;
120.                         }
121.                         else
122.                         {
123.                                 parent->_right = cur;
124.                         }
125.                         cur->_parent = parent;
127.                         while (parent && parent->_col == RED)
128.                         {
129.                                 Node* grandparent = parent->_parent;
130.                                 if (parent == grandparent->_left)
131.                                 {
132.                                         Node* uncle = grandparent->_right;
133.                                         if (uncle && uncle->_col == RED)
134.                                         {
135.                                                 parent->_col = uncle->_col = BLACK;
136.                                                 grandparent->_col = RED;
137.                                                 cur = grandparent;
138.                                                 parent = cur->_parent;
139.                                         }
140.                                         else//uncle is not or black
141.                                         {
142.                                                 if (cur == parent->_left)
143.                                                 {
144.                                                         RotateR(grandparent);
145.                                                         grandparent->_col = RED;
146.                                                         parent->_col = BLACK;
147.                                                 }
148.                                                 else
149.                                                 {
150.                                                         RotateL(parent);
151.                                                         RotateR(grandparent);
152.                                                         grandparent->_col = RED;
153.                                                         cur->_col = BLACK;
154.                                                 }
155.                                                 break;
156.                                         }
157.                                 }
158.                                 else//parent == grandparent->_right
159.                                 {
160.                                         Node* uncle = grandparent->_left;
162.                                         if (uncle && uncle->_col == RED)
163.                                         {
164.                                                 grandparent->_col = RED;
165.                                                 parent->_col = uncle->_col= BLACK;
166.                                                 cur = grandparent;
167.                                                 parent = cur->_parent;
168.                                         }
169.                                         else
170.                                         {
171.                                                 if (cur == parent->_right)
172.                                                 {
173.                                                         RotateL(grandparent);
174.                                                         parent->_col = BLACK;
175.                                                         grandparent->_col = RED;
176.                                                 }
177.                                                 else
178.                                                 {
179.                                                         RotateR(parent);
180.                                                         RotateL(grandparent);
181.                                                         cur->_col = BLACK;
182.                                                         grandparent->_col = RED;
183.                                                 }
184.                                         }
185.                                         break;
186.                                 }
187.                         }
188.                         _root->_col = BLACK;
189.                         return true;
190.                 }
192.                 void RotateR(Node* parent)
193.                 {
194.                         Node* cur = parent->_left;
195.                         Node* curright = cur->_right;
197.                         parent->_left = curright;
199.                         if (curright)
200.                         {
201.                                 curright->_parent = parent;
202.                         }
204.                         cur->_right = parent;
206.                         Node* ppnode = parent->_parent;
208.                         parent->_parent = cur;
210.                         if (ppnode == nullptr)
211.                         {
212.                                 _root = cur;
213.                                 cur->_parent = nullptr;
214.                         }
215.                         else
216.                         {
217.                                 if (ppnode->_left == parent)
218.                                 {
219.                                         ppnode->_left = cur;
220.                                 }
221.                                 else
222.                                 {
223.                                         ppnode->_right = cur;
224.                                 }
226.                                 cur->_parent = ppnode;
227.                         }
229.                 }
230.                 void RotateL(Node* parent)
231.                 {
233.                         Node* cur = parent->_right;
235.                         Node* curleft = cur->_left;
237.                         parent->_right = curleft;
239.                         if (curleft)
240.                         {
241.                                 curleft->_parent = parent;
242.                         }
244.                         cur->_left = parent;
246.                         Node* ppnode = parent->_parent;
248.                         parent->_parent = cur;
250.                         if (parent == _root)
251.                         {
252.                                 _root = cur;
253.                                 cur->_parent = nullptr;
254.                         }
255.                         else
256.                         {
257.                                 if (ppnode->_left == parent)
258.                                 {
259.                                         ppnode->_left = cur;
260.                                 }
261.                                 else
262.                                 {
263.                                         ppnode->_right = cur;
264.                                 }
266.                                 cur->_parent = ppnode;
267.                         }
268.                 }
270.         private:
271.                 Node* _root = nullptr;
272.         };
274. }
276.         }
277.                 void RotateL(Node* parent)
278.                 {
280.                         Node* cur = parent->_right;
282.                         Node* curleft = cur->_left;
284.                         parent->_right = curleft;
286.                         if (curleft)
287.                         {
288.                                 curleft->_parent = parent;
289.                         }
291.                         cur->_left = parent;
293.                         Node* ppnode = parent->_parent;
295.                         parent->_parent = cur;
297.                         if (parent == _root)
298.                         {
299.                                 _root = cur;
300.                                 cur->_parent = nullptr;
301.                         }
302.                         else
303.                         {
304.                                 if (ppnode->_left == parent)
305.                                 {
306.                                         ppnode->_left = cur;
307.                                 }
308.                                 else
309.                                 {
310.                                         ppnode->_right = cur;
311.                                 }
313.                                 cur->_parent = ppnode;
314.                         }
315.                 }
317.         private:
318.                 Node* _root = nullptr;
319.         };
321. }

复制代码

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