STL 改造红黑树 模仿封装set和map

改造红黑树


目录

• 改造红黑树
  
  
  
  • 适配STL迭代器的红黑树
    
    
    
    • 基本结构
      
    • RBTreeNode
      
    • __RBTree_iterator
      
    • RBTree
      
    • 完备代码
      
    
    
  • 封装的set
    
  • 封装的map
    
  
  

在初次看STL中实现红黑树的源码时有些不理解,然后自己实验对set以RBTree的方式封装红黑树的迭代器;实现过程发现,这样封装复用程度特别低,也特别冗余,因此才能意会到STL源码实现红黑树复用时的英华.下文将模仿STL的实现方式改造红黑树和封装map和set.

参考的STL版本为SGI30

适配STL迭代器的红黑树

红黑树数据操作的代码实现是旧版本的,新版本在上一篇博客中有详细分析.
本篇主要特点在迭代器适配上
基本结构

1. #pragma once
3. #include<assert.h>
4. #include<iostream>
5. using std::cout;
6. using std::endl;
7. using std::cin;
8. using std::pair;
9. using std::make_pair;
10. using std::string;
13. namespace test
14. {
15.         enum Colour { RED, BLACK };
16.         template<class T> struct RBTreeNode;
17.         template<class T, class Ref, typename Ptr> struct __RBTree_iterator;
18.         template<class K, class T, class keyOfT> class RBTree;
19. }

复制代码

RBTreeNode

1.         template<class T> // T为key或pair,T是key或者key-value类型
2.         struct RBTreeNode
3.         {
4.                 RBTreeNode* _left;
5.                 RBTreeNode* _right;
6.                 RBTreeNode* _parent;
7.                 T _data; //data是key或pair
8.                 Colour _col;
10.                 RBTreeNode(const T& data)
11.                         : _left(nullptr)
12.                         , _right(nullptr)
13.                         , _parent(nullptr)
14.                         , _data(data)
15.                         , _col(RED)
16.                 {}
17.         };

复制代码

__RBTree_iterator

1. template<class T, class Ref, typename Ptr>
2.         struct __RBTree_iterator
3.         {
4.                 typedef RBTreeNode<T> node;
5.                 node* _node;
6.                 __RBTree_iterator(node* node)
7.                         :_node(node)
8.                 {}
10.                 //首先,<class T, class Ref, class Ptr>这种写法能够提高复用性和灵活性(实现不同类型的迭代器)等,,库里迭代器都这么写
11.                 //其次,模板参数中,T用于获取类型,Ref用于返回引用,Ptr用于返回指针
13.                 using Self           = __RBTree_iterator<T,Ref,Ptr>;            //自己--实例化出下面两种迭代器
14.                 using iterator       = __RBTree_iterator<T,T&,T*>;              //普通迭代器
15.                 using const_iterator = __RBTree_iterator<T,const T&,const T*>;  //const迭代器
16.                 __RBTree_iterator(const iterator& it)
17.                         :_node(it._node)
18.                 {}
19.                 //这个构造函数的作用,
20.             //a.当迭代器被实例化成iterator时,他就是拷贝构造函数.      __RBTree_iterator<T,T&,T*>
21.                 //b.当迭代器被实例化成const_iterator时,他是支持隐式类型转换的带参构造函数. __RBTree_iterator<T,const T&,const T*>
23.                 //这样实现的目的
24.             // 能够复用普通迭代器,可以通过类型转换后直接实现出const迭代器
27.                 //Ref为 T& 或 const T&, Ptr为 T* 或 const T*
28.                 //typedef __RBTree_iterator<T, Ref, Ptr> Self;
30.                 Ref operator*()
31.                 {
32.                         return _node->_data;
33.                 }
34.                 Ptr operator->()
35.                 {
36.                         return &(_node->_data);
37.                 }
38.                 bool operator!=(const Self& x)
39.                 {
40.                         return _node != x._node;
41.                 }
42.     //前置++
43.     Self& operator++() {
44.         //此版本实现迭代器不需要判空,为空说明遍历结束,要么是用户错误使用
45.         Node* cur = _node;
46.         //1. 有右子树
47.         if (cur->_right) {
48.             //找右子树的最小结点
49.             Node* rightMin = cur->_right;
50.             while (rightMin->_left) {
51.                 rightMin = rightMin->_left;
52.             }
53.             _node = rightMin;
54.         }
55.         //2. 没有右子树
56.         else {
57.             ////1.没有父亲,说明是根
58.             //Node* parent = cur->_parent;
59.             //if (parent == nullptr) {
60.             //    _node == nullptr;
61.             //}
62.             ////2.且我是父的左子树,说明父亲是下一个正序值
63.             //else if (parent->_left == cur) {
64.             //    _node = parent;
65.             //}
66.             ////3.或我是父亲的右子树,说明走完了当前最小分支祖先这棵树.迭代往上
67.             //else if (parent->_right == cur) {
68.             //    while (parent && cur != parent->_left) {
69.             //        cur = parent;
70.             //        parent = parent->_parent;
71.             //    }
72.             //    _node = parent;
73.             //}
74.             //else {
75.             //    asssert(false);
76.             //}
78.             //上面3种情况可以合并成一种情况:找最近的不是右孩子的祖父
79.             Node* parent = cur->_parent;
80.             while (parent && cur != parent->_left) {
81.                 cur = parent;
82.                 parent = parent->_parent;
83.             }
84.             _node = parent;
85.         }
86.         return *this;
87.     }
89.     //后置++
90.     Self operator++(int) {
91.         Self tmp(_node);
92.         operator++();
93.         return tmp;
94.     }
97.     Self& operator--() {
98.         //将++反过来就是--
99.         Node* cur = _node;
100.         //左子树存在,就找最大
101.         if (cur->_left) {
102.             Node* leftMax = cur->_left;
103.             while (leftMax->_right) {
104.                 leftMax = leftMax->_right;
105.             }
106.             _node = leftMax;
107.         }
108.         //2. 没有左子树
109.         else {
110.             Node* parent = cur->_parent;
111.             while (parent && cur != parent->_right) {
112.                 cur = parent;
113.                 parent = parent->_parent;
114.             }
115.             _node = parent;
116.         }
117.         return *this;
118.     }
120.     Self operator--(int) {
121.         Self tmp(_node);
122.         operator--();
123.         return tmp;
124.     }
125.         };

复制代码

RBTree

1.         //参数K用在find,erase等,虽然K也可以被T取代了,但没必要,K更快
2.         template<class K, class T, class keyOfT> //库中还有1个compare，先不写了
3.         class RBTree
4.         {
5.         public:
6.                 typedef RBTreeNode<T> node; //T是key或pair
7.         public:
8.                 typedef __RBTree_iterator<T, T&, T*> iterator;
9.                 typedef __RBTree_iterator<T, const T&, const T*> const_iterator;
11.                 iterator begin()
12.                 {
13.                         node* cur = _root;
14.                         while (cur && cur->_left)//不能走到空
15.                         {
16.                                 cur = cur->_left;
17.                         }
18.                         return iterator(cur);//返回中序的第一个结点,最左结点
19.                 }
21.                 iterator end() //end是最一个位置的下一个
22.                 {
23.                         return iterator(nullptr);//暂时可以这么写
24.                 }
26.                 const_iterator begin()const
27.                 {
28.                         node* cur = _root;
29.                         while (cur && cur->_left)
30.                         {
31.                                 cur = cur->_left;
32.                         }
33.                         return iterator(cur);
34.                 }
36.                 const_iterator end() const
37.                 {
38.                         return iterator(nullptr);
39.                 }
41.         private:
42.                 node* _root = nullptr;
43.         public:
44.                 node* find(const K& key)
45.                 {
46.                         keyOfT kot;//kot是个仿函数,根据不同参数返回不同的参数对象
47.                         node* cur = _root;
48.                         while (cur)
49.                         {
50.                                 if (key < kot(cur->_data)) // -------------------------------------------- 只需要重载一个 '<' 或 '>' 就可以比较大小
51.                                 {
52.                                         cur = cur->_left;
53.                                 }
54.                                 else if (kot(cur->_data) < key) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
55.                                 {
56.                                         cur = cur->_right;
57.                                 }
58.                                 else
59.                                 {
60.                                         return cur;
61.                                 }
62.                         }
63.                         return nullptr;
64.                 }
66.                 pair<iterator, bool> insert(const T& data)
67.                 {
68.                         if (!_root)
69.                         {
70.                                 _root = new node(data);
71.                                 _root->_col = BLACK;
72.                                 return std::make_pair(iterator(_root), true);
73.                         }
74.                        
75.                         keyOfT kot;
77.                         node* cur = _root;
78.                         node* parent = nullptr;
79.                         while (cur)
80.                         {
81.                                 if (kot(cur->_data) < kot(data)  ) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
82.                                 {
83.                                         parent = cur;
84.                                         cur = cur->_right;
85.                                 }
86.                                 else if (kot(data) < kot(cur->_data)) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
87.                                 {
88.                                         parent = cur;
89.                                         cur = cur->_left;
90.                                 }
91.                                 else
92.                                 {
93.                                         return std::make_pair(iterator(cur), false);
94.                                 }
95.                         }
96.                         cur = new node(data);
97.                         if ( kot(parent->_data) < kot(data)) // --------------------------------------------
98.                         {
99.                                 parent->_right = cur;
100.                         }
101.                         else
102.                         {
103.                                 parent->_left = cur;
104.                         }
105.                         cur->_parent = parent;
107.                         //调整/旋转
108.                         node* newnode = cur;//调整过程cur会发生变化,将cur结点记住 -- 记住原来key的位置
109.                         while (parent && parent->_col == RED)
110.                         {
111.                                 node* g = parent->_parent;
112.                                 if (parent == g->_right)
113.                                 {
114.                                         node* u = g->_left;
115.                                         if (u && u->_col == RED)
116.                                         {
117.                                                 g->_col = RED;
118.                                                 parent->_col = BLACK;
119.                                                 u->_col = BLACK;
120.                                                 cur = g;
121.                                                 parent = cur->_parent;
122.                                         }
123.                                         else
124.                                         {
125.                                                 if (cur == parent->_right)
126.                                                 {
127.                                                         RotateL(g);
128.                                                         parent->_col = BLACK;
129.                                                         g->_col = RED;
130.                                                 }
131.                                                 else
132.                                                 {
133.                                                         RotateR(parent);
134.                                                         RotateL(g);
135.                                                         g->_col = RED;
136.                                                         cur->_col = BLACK;
137.                                                 }
138.                                                 break;
139.                                         }
141.                                 }
142.                                 else
143.                                 {
144.                                         node* u = g->_right;
145.                                         if (u && u->_col == RED)
146.                                         {
147.                                                 g->_col = RED;
148.                                                 parent->_col = BLACK;
149.                                                 u->_col = BLACK;
150.                                                 cur = g;
151.                                                 parent = cur->_parent;
152.                                         }
153.                                         else
154.                                         {
155.                                                 if (cur == parent->_left)
156.                                                 {
157.                                                         RotateR(g);
158.                                                         parent->_col = BLACK;
159.                                                         g->_col = RED;
160.                                                 }
161.                                                 else
162.                                                 {
163.                                                         RotateL(parent);
164.                                                         RotateR(g);
165.                                                         g->_col = RED;
166.                                                         cur->_col = BLACK;
167.                                                 }
168.                                                 break;
169.                                         }
170.                                 }
171.                         }
172.                         _root->_col = BLACK;
173.                         return std::make_pair(iterator(newnode), true);
174.                 }
175.         public:
176.                 void InOrderTraversal()
177.                 {
178.                         _InOrderTraversal(_root);
179.                 }
181.                 bool isBalanceTree()
182.                 {
183.                         //需要判断3个规则
184.                         //1.根为黑
185.                         if (_root && _root->_col == RED)
186.                         {
187.                                 cout << "错误:根是红色" << endl;
188.                                 return false;
189.                         }
191.                         //2.不能有连续得红
192.                         //3.黑同
193.                         int benchmark = 0;
194.                         node* cur = _root;
195.                         while (cur)
196.                         {
197.                                 if (cur->_col == BLACK)
198.                                 {
199.                                         ++benchmark;
200.                                 }
201.                                 cur = cur->_left;
202.                         }
203.                         return _check(_root, 0, benchmark);
204.                 }
206.                 int Height()
207.                 {
208.                         return _Height(_root);
209.                 }
210.                 ~RBTree()
211.                 {
212.                         Destroy(_root);
213.                 }
215.         private:
216.                 void Destroy(node*& root)
217.                 {
218.                         if (!root)
219.                         {
220.                                 return;
221.                         }
222.                         Destroy(root->_left);
223.                         Destroy(root->_right);
224.                         delete root;
225.                         root = nullptr;
226.                 }
228.                 bool _check(node* root, int blackNum, int benchmark)
229.                 {
230.                         keyOfT kot;
231.                         if (!root) //
232.                         {
233.                                 if (blackNum != benchmark)
234.                                 {
235.                                         cout << "错误:存在不同路径的黑色结点数量不相同" << endl;
236.                                         return false;
237.                                 }
238.                                 return true;
239.                         }
241.                         if (root->_col == BLACK)
242.                         {
243.                                 ++blackNum;
244.                         }
246.                         if (root->_col == RED && root->_parent->_col == RED)
247.                         {
248.                                 cout << kot(root->_data) << " 错误,与父节点同时为红色"; // --------------------------------------------
249.                                 return false;
250.                         }
252.                         return _check(root->_left, blackNum, benchmark) && _check(root->_right, blackNum, benchmark);
253.                 }
255.                 int _Height(node* root)
256.                 {
257.                         if (!root)
258.                         {
259.                                 return 0;
260.                         }
261.                         int leftH = _Height(root->_left);
262.                         int rightH = _Height(root->_right);
264.                         return leftH > rightH ? leftH + 1 : rightH + 1;
265.                 }
267.                 void _InOrderTraversal(node* root)
268.                 {
269.                         keyOfT kot;
270.                         if (root == nullptr)
271.                         {
272.                                 return;
273.                         }
274.                         _InOrderTraversal(root->_left);
275.                         cout << kot(root->_data) << " "; // --------------------------------------------
276.                         _InOrderTraversal(root->_right);
277.                 }
279.                 void RotateL(node* parent)
280.                 {
281.                         node* subR = parent->_right;
282.                         node* subRL = subR->_left;
284.                         parent->_right = subRL;
285.                         if (subRL)
286.                         {
287.                                 subRL->_parent = parent;
288.                         }
290.                         node* pparent = parent->_parent;
292.                         subR->_left = parent;
293.                         parent->_parent = subR;
295.                         if (!pparent)
296.                         {
297.                                 _root = subR;
298.                                 _root->_parent = nullptr;
299.                         }
300.                         else
301.                         {
302.                                 if (pparent->_left == parent)
303.                                 {
304.                                         pparent->_left = subR;
305.                                 }
306.                                 else
307.                                 {
308.                                         pparent->_right = subR;
309.                                 }
310.                                 subR->_parent = pparent;
311.                         }
312.                 }
314.                 void RotateR(node* parent)
315.                 {
316.                         node* subL = parent->_left;
317.                         node* subLR = subL->_right;
319.                         parent->_left = subLR;
320.                         if (subLR)
321.                         {
322.                                 subLR->_parent = parent;
323.                         }
325.                         node* pparent = parent->_parent;
327.                         subL->_right = parent;
328.                         parent->_parent = subL;
331.                         if (parent == _root)
332.                         {
333.                                 _root = subL;
334.                                 _root->_parent = nullptr;
335.                         }
336.                         else
337.                         {
338.                                 if (pparent->_left == parent)
339.                                 {
340.                                         pparent->_left = subL;
341.                                 }
342.                                 else
343.                                 {
344.                                         pparent->_right = subL;
345.                                 }
346.                                 subL->_parent = pparent;
347.                         }
348.                 }
349.         };

复制代码

完备代码

1. #pragma once#include#includeusing std::cout;using std::endl;using std::cin;using std::pair;using std::make_pair;using std::string;namespace test{        //与库中的RBT差异        /**         *         * 库中另有结点数量 count         *         * 库中RBT是带头结点哨兵卫的,头结点的左是中序第一个(最小结点),右节点是中序的末了一个(最大结点),         * 哨兵卫的parent指向根节点,根节点的parent指向哨兵卫         *         * 库中的begin直接取head的left -- 函数:leftmost() //最左结点         * 库中的end 是head的right -- 不是rightmost,rightmost是最右结点,end是最右结点的下一个         * 库中的end 需要判断一下,防止只有左子树的歪脖子树时,end == head->right,死循环         *         * 和库的区别就是end,库的end能走回到head,我的不能,只能走到空就没了d         *         */        enum Colour { RED, BLACK };        template //T是什么,为什么只传T? T为key或pair,T是key或者key-value范例        struct RBTreeNode        {                RBTreeNode* _left;                RBTreeNode* _right;                RBTreeNode* _parent;                T _data; //data是key或pair                Colour _col;                RBTreeNode(const T& data)                        : _left(nullptr)                        , _right(nullptr)                        , _parent(nullptr)                        , _data(data)                        , _col(RED)                {}        };        //const_iterator        //iterator        template<class T, class Ref, typename Ptr>
2.         struct __RBTree_iterator
3.         {
4.                 typedef RBTreeNode<T> node;
5.                 node* _node;
6.                 __RBTree_iterator(node* node)
7.                         :_node(node)
8.                 {}
10.                 //首先,<class T, class Ref, class Ptr>这种写法能够提高复用性和灵活性(实现不同类型的迭代器)等,,库里迭代器都这么写
11.                 //其次,模板参数中,T用于获取类型,Ref用于返回引用,Ptr用于返回指针
13.                 using Self           = __RBTree_iterator<T,Ref,Ptr>;            //自己--实例化出下面两种迭代器
14.                 using iterator       = __RBTree_iterator<T,T&,T*>;              //普通迭代器
15.                 using const_iterator = __RBTree_iterator<T,const T&,const T*>;  //const迭代器
16.                 __RBTree_iterator(const iterator& it)
17.                         :_node(it._node)
18.                 {}
19.                 //这个构造函数的作用,
20.             //a.当迭代器被实例化成iterator时,他就是拷贝构造函数.      __RBTree_iterator<T,T&,T*>
21.                 //b.当迭代器被实例化成const_iterator时,他是支持隐式类型转换的带参构造函数. __RBTree_iterator<T,const T&,const T*>
23.                 //这样实现的目的
24.             // 能够复用普通迭代器,可以通过类型转换后直接实现出const迭代器
27.                 //Ref为 T& 或 const T&, Ptr为 T* 或 const T*
28.                 //typedef __RBTree_iterator<T, Ref, Ptr> Self;
30.                 Ref operator*()
31.                 {
32.                         return _node->_data;
33.                 }
34.                 Ptr operator->()
35.                 {
36.                         return &(_node->_data);
37.                 }
38.                 bool operator!=(const Self& x)
39.                 {
40.                         return _node != x._node;
41.                 }
42.     //前置++
43.     Self& operator++() {
44.         //此版本实现迭代器不需要判空,为空说明遍历结束,要么是用户错误使用
45.         Node* cur = _node;
46.         //1. 有右子树
47.         if (cur->_right) {
48.             //找右子树的最小结点
49.             Node* rightMin = cur->_right;
50.             while (rightMin->_left) {
51.                 rightMin = rightMin->_left;
52.             }
53.             _node = rightMin;
54.         }
55.         //2. 没有右子树
56.         else {
57.             ////1.没有父亲,说明是根
58.             //Node* parent = cur->_parent;
59.             //if (parent == nullptr) {
60.             //    _node == nullptr;
61.             //}
62.             ////2.且我是父的左子树,说明父亲是下一个正序值
63.             //else if (parent->_left == cur) {
64.             //    _node = parent;
65.             //}
66.             ////3.或我是父亲的右子树,说明走完了当前最小分支祖先这棵树.迭代往上
67.             //else if (parent->_right == cur) {
68.             //    while (parent && cur != parent->_left) {
69.             //        cur = parent;
70.             //        parent = parent->_parent;
71.             //    }
72.             //    _node = parent;
73.             //}
74.             //else {
75.             //    asssert(false);
76.             //}
78.             //上面3种情况可以合并成一种情况:找最近的不是右孩子的祖父
79.             Node* parent = cur->_parent;
80.             while (parent && cur != parent->_left) {
81.                 cur = parent;
82.                 parent = parent->_parent;
83.             }
84.             _node = parent;
85.         }
86.         return *this;
87.     }
89.     //后置++
90.     Self operator++(int) {
91.         Self tmp(_node);
92.         operator++();
93.         return tmp;
94.     }
97.     Self& operator--() {
98.         //将++反过来就是--
99.         Node* cur = _node;
100.         //左子树存在,就找最大
101.         if (cur->_left) {
102.             Node* leftMax = cur->_left;
103.             while (leftMax->_right) {
104.                 leftMax = leftMax->_right;
105.             }
106.             _node = leftMax;
107.         }
108.         //2. 没有左子树
109.         else {
110.             Node* parent = cur->_parent;
111.             while (parent && cur != parent->_right) {
112.                 cur = parent;
113.                 parent = parent->_parent;
114.             }
115.             _node = parent;
116.         }
117.         return *this;
118.     }
120.     Self operator--(int) {
121.         Self tmp(_node);
122.         operator--();
123.         return tmp;
124.     }
125.         };        //参数K用在find,erase等,虽然K也可以被T取代了,但没必要,K更快
126.         template<class K, class T, class keyOfT> //库中还有1个compare，先不写了
127.         class RBTree
128.         {
129.         public:
130.                 typedef RBTreeNode<T> node; //T是key或pair
131.         public:
132.                 typedef __RBTree_iterator<T, T&, T*> iterator;
133.                 typedef __RBTree_iterator<T, const T&, const T*> const_iterator;
135.                 iterator begin()
136.                 {
137.                         node* cur = _root;
138.                         while (cur && cur->_left)//不能走到空
139.                         {
140.                                 cur = cur->_left;
141.                         }
142.                         return iterator(cur);//返回中序的第一个结点,最左结点
143.                 }
145.                 iterator end() //end是最一个位置的下一个
146.                 {
147.                         return iterator(nullptr);//暂时可以这么写
148.                 }
150.                 const_iterator begin()const
151.                 {
152.                         node* cur = _root;
153.                         while (cur && cur->_left)
154.                         {
155.                                 cur = cur->_left;
156.                         }
157.                         return iterator(cur);
158.                 }
160.                 const_iterator end() const
161.                 {
162.                         return iterator(nullptr);
163.                 }
165.         private:
166.                 node* _root = nullptr;
167.         public:
168.                 node* find(const K& key)
169.                 {
170.                         keyOfT kot;//kot是个仿函数,根据不同参数返回不同的参数对象
171.                         node* cur = _root;
172.                         while (cur)
173.                         {
174.                                 if (key < kot(cur->_data)) // -------------------------------------------- 只需要重载一个 '<' 或 '>' 就可以比较大小
175.                                 {
176.                                         cur = cur->_left;
177.                                 }
178.                                 else if (kot(cur->_data) < key) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
179.                                 {
180.                                         cur = cur->_right;
181.                                 }
182.                                 else
183.                                 {
184.                                         return cur;
185.                                 }
186.                         }
187.                         return nullptr;
188.                 }
190.                 pair<iterator, bool> insert(const T& data)
191.                 {
192.                         if (!_root)
193.                         {
194.                                 _root = new node(data);
195.                                 _root->_col = BLACK;
196.                                 return std::make_pair(iterator(_root), true);
197.                         }
198.                        
199.                         keyOfT kot;
201.                         node* cur = _root;
202.                         node* parent = nullptr;
203.                         while (cur)
204.                         {
205.                                 if (kot(cur->_data) < kot(data)  ) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
206.                                 {
207.                                         parent = cur;
208.                                         cur = cur->_right;
209.                                 }
210.                                 else if (kot(data) < kot(cur->_data)) // --------------------------------------------只需要重载一个 '<' 或 '>' 就可以比较大小
211.                                 {
212.                                         parent = cur;
213.                                         cur = cur->_left;
214.                                 }
215.                                 else
216.                                 {
217.                                         return std::make_pair(iterator(cur), false);
218.                                 }
219.                         }
220.                         cur = new node(data);
221.                         if ( kot(parent->_data) < kot(data)) // --------------------------------------------
222.                         {
223.                                 parent->_right = cur;
224.                         }
225.                         else
226.                         {
227.                                 parent->_left = cur;
228.                         }
229.                         cur->_parent = parent;
231.                         //调整/旋转
232.                         node* newnode = cur;//调整过程cur会发生变化,将cur结点记住 -- 记住原来key的位置
233.                         while (parent && parent->_col == RED)
234.                         {
235.                                 node* g = parent->_parent;
236.                                 if (parent == g->_right)
237.                                 {
238.                                         node* u = g->_left;
239.                                         if (u && u->_col == RED)
240.                                         {
241.                                                 g->_col = RED;
242.                                                 parent->_col = BLACK;
243.                                                 u->_col = BLACK;
244.                                                 cur = g;
245.                                                 parent = cur->_parent;
246.                                         }
247.                                         else
248.                                         {
249.                                                 if (cur == parent->_right)
250.                                                 {
251.                                                         RotateL(g);
252.                                                         parent->_col = BLACK;
253.                                                         g->_col = RED;
254.                                                 }
255.                                                 else
256.                                                 {
257.                                                         RotateR(parent);
258.                                                         RotateL(g);
259.                                                         g->_col = RED;
260.                                                         cur->_col = BLACK;
261.                                                 }
262.                                                 break;
263.                                         }
265.                                 }
266.                                 else
267.                                 {
268.                                         node* u = g->_right;
269.                                         if (u && u->_col == RED)
270.                                         {
271.                                                 g->_col = RED;
272.                                                 parent->_col = BLACK;
273.                                                 u->_col = BLACK;
274.                                                 cur = g;
275.                                                 parent = cur->_parent;
276.                                         }
277.                                         else
278.                                         {
279.                                                 if (cur == parent->_left)
280.                                                 {
281.                                                         RotateR(g);
282.                                                         parent->_col = BLACK;
283.                                                         g->_col = RED;
284.                                                 }
285.                                                 else
286.                                                 {
287.                                                         RotateL(parent);
288.                                                         RotateR(g);
289.                                                         g->_col = RED;
290.                                                         cur->_col = BLACK;
291.                                                 }
292.                                                 break;
293.                                         }
294.                                 }
295.                         }
296.                         _root->_col = BLACK;
297.                         return std::make_pair(iterator(newnode), true);
298.                 }
299.         public:
300.                 void InOrderTraversal()
301.                 {
302.                         _InOrderTraversal(_root);
303.                 }
305.                 bool isBalanceTree()
306.                 {
307.                         //需要判断3个规则
308.                         //1.根为黑
309.                         if (_root && _root->_col == RED)
310.                         {
311.                                 cout << "错误:根是红色" << endl;
312.                                 return false;
313.                         }
315.                         //2.不能有连续得红
316.                         //3.黑同
317.                         int benchmark = 0;
318.                         node* cur = _root;
319.                         while (cur)
320.                         {
321.                                 if (cur->_col == BLACK)
322.                                 {
323.                                         ++benchmark;
324.                                 }
325.                                 cur = cur->_left;
326.                         }
327.                         return _check(_root, 0, benchmark);
328.                 }
330.                 int Height()
331.                 {
332.                         return _Height(_root);
333.                 }
334.                 ~RBTree()
335.                 {
336.                         Destroy(_root);
337.                 }
339.         private:
340.                 void Destroy(node*& root)
341.                 {
342.                         if (!root)
343.                         {
344.                                 return;
345.                         }
346.                         Destroy(root->_left);
347.                         Destroy(root->_right);
348.                         delete root;
349.                         root = nullptr;
350.                 }
352.                 bool _check(node* root, int blackNum, int benchmark)
353.                 {
354.                         keyOfT kot;
355.                         if (!root) //
356.                         {
357.                                 if (blackNum != benchmark)
358.                                 {
359.                                         cout << "错误:存在不同路径的黑色结点数量不相同" << endl;
360.                                         return false;
361.                                 }
362.                                 return true;
363.                         }
365.                         if (root->_col == BLACK)
366.                         {
367.                                 ++blackNum;
368.                         }
370.                         if (root->_col == RED && root->_parent->_col == RED)
371.                         {
372.                                 cout << kot(root->_data) << " 错误,与父节点同时为红色"; // --------------------------------------------
373.                                 return false;
374.                         }
376.                         return _check(root->_left, blackNum, benchmark) && _check(root->_right, blackNum, benchmark);
377.                 }
379.                 int _Height(node* root)
380.                 {
381.                         if (!root)
382.                         {
383.                                 return 0;
384.                         }
385.                         int leftH = _Height(root->_left);
386.                         int rightH = _Height(root->_right);
388.                         return leftH > rightH ? leftH + 1 : rightH + 1;
389.                 }
391.                 void _InOrderTraversal(node* root)
392.                 {
393.                         keyOfT kot;
394.                         if (root == nullptr)
395.                         {
396.                                 return;
397.                         }
398.                         _InOrderTraversal(root->_left);
399.                         cout << kot(root->_data) << " "; // --------------------------------------------
400.                         _InOrderTraversal(root->_right);
401.                 }
403.                 void RotateL(node* parent)
404.                 {
405.                         node* subR = parent->_right;
406.                         node* subRL = subR->_left;
408.                         parent->_right = subRL;
409.                         if (subRL)
410.                         {
411.                                 subRL->_parent = parent;
412.                         }
414.                         node* pparent = parent->_parent;
416.                         subR->_left = parent;
417.                         parent->_parent = subR;
419.                         if (!pparent)
420.                         {
421.                                 _root = subR;
422.                                 _root->_parent = nullptr;
423.                         }
424.                         else
425.                         {
426.                                 if (pparent->_left == parent)
427.                                 {
428.                                         pparent->_left = subR;
429.                                 }
430.                                 else
431.                                 {
432.                                         pparent->_right = subR;
433.                                 }
434.                                 subR->_parent = pparent;
435.                         }
436.                 }
438.                 void RotateR(node* parent)
439.                 {
440.                         node* subL = parent->_left;
441.                         node* subLR = subL->_right;
443.                         parent->_left = subLR;
444.                         if (subLR)
445.                         {
446.                                 subLR->_parent = parent;
447.                         }
449.                         node* pparent = parent->_parent;
451.                         subL->_right = parent;
452.                         parent->_parent = subL;
455.                         if (parent == _root)
456.                         {
457.                                 _root = subL;
458.                                 _root->_parent = nullptr;
459.                         }
460.                         else
461.                         {
462.                                 if (pparent->_left == parent)
463.                                 {
464.                                         pparent->_left = subL;
465.                                 }
466.                                 else
467.                                 {
468.                                         pparent->_right = subL;
469.                                 }
470.                                 subL->_parent = pparent;
471.                         }
472.                 }
473.         };}

复制代码

封装的set

红黑树改造完成后,封装set和map就比较简单了,基本上都是套用红黑树的功能,特别方便,这也体会到了实现STL的大佬们的厉害.
[code]#pragma once#include"RBT.hpp"namespace test{        template        class set        {        private:                struct setKeyOfT//取出RBT的范例T中的key                {                        const K& operator()(const K& key)                         {                                return key;                         }                };        private:                RBTree< K, K, setKeyOfT>_t;        public:                //利用类域的要加typename,以防和静态变量辩论                typedef typename RBTree::const_iterator iterator; //寻常迭代器                typedef typename RBTree::const_iterator const_iterator; //const迭代器                iterator begin()                {                        return _t.begin(); //begin是寻常迭代器,返回值是const,发生隐式范例转换(单参数)                        //如果有相应的构造函数,则支持隐式范例转换 ,但此时迭代器没有参数为迭代器的构造函数,需要添加                }                iterator end()                {                        return _t.end();                }                const_iterator begin()const                {                        return _t.begin();                }                const_iterator end()const                {                        return _t.end();                }                        public:                pair insert(const K& key)                {                        return _t.insert(key);                }        };        void test_mySet1()        {                test::set s;                s.insert(2);                s.insert(1);                s.insert(3);                set::iterator it = s.begin();                //while (it!=s.end())                //{                //        cout