ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【C++】红黑树 [打印本页]

---

作者: 怀念夏天    时间: 2024-9-6 10:55
标题: 【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企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4