RBTree改造，并模拟实现set&map

目录
RBTree改造
给红黑树增加迭代器
前置++
前置--
RBT细节改造
模拟set
模拟map

---

RBTree改造

给红黑树增加迭代器

前置++

前置++的作用是找下一个较大的节点。

假如我们it指向的是5，++it则是将it指向6。加入it指向的是7，则++it则是将it指向8。
也就是说如果右子树不为空，++it是指向的是右子树的最左节点（较大的）。
如果右子树为空（分析该子树已被访问完），++it应该沿着根路径指向孩子是父亲左孩子的那个祖先。

1. //前置++
2.         self& operator++() {
3.                 if (_node->_right) {
4.                         Node* min = _node->_right;
5.                         while (min->_left) {
6.                                 min = min->_left;
7.                         }
8.                         _node = min;
9.                 }
10.                 else {
11.                         Node* cur = _node;
12.                         Node* parent = cur->_parent;
13.                         while (parent && cur == parent->_right) {//这个循环作用是找父亲的左孩子
14.                                 cur = cur->_parent;
15.                                 parent = parent->_parent;
16.                         }
17.                         _node = parent;
18.                 }
19.                 return *this;
20.         }

复制代码

前置--

前置--的作用是找下一个较小的节点。

 假如it指向的是8，--it则是将it指向7。假如it指向的是12，--it则就将it指向了11。
也就是说如果左子树不为空，--it是指向的是左子树的最右节点（较小的）。
如果左子树为空（分析该子树已被访问完），--it应该沿着根路径指向孩子是父亲右孩子的那个祖先。++it的次序是左根右，--it的次序是右根左。

1. //前置--
2.         self& operator--() {
3.                 if (_node->_left) {
4.                         Node* max = _node->_left;
5.                         while (max->_right) {
6.                                 max = max->_right;
7.                         }
8.                         _node = max;
9.                 }
10.                 else {
11.                         Node* cur = _node;
12.                         Node* parent = cur->_parent;
13.                         while (parent && cur == parent->_left) {
14.                                 cur = parent;
15.                                 parent = parent->_parent;
16.                         }
17.                         _node = parent;
18.                 }
19.                 return *this;
20.         }

复制代码

RBT细节改造

1、将节点存放数据的位置改为_data，也就是说无论是set还是map存放的数据都在这个_data内里。

1. template<class T>
2. struct rbtreeNode{
3.         rbtreeNode<T>* _left;
4.         rbtreeNode<T>* _right;
5.         rbtreeNode<T>* _parent;
6.         T _data;
7.         Color _col;
8.         rbtreeNode(const T& data)
9.                 :_left(nullptr)
10.                 ,_right(nullptr)
11.                 ,_parent(nullptr)
12.                 ,_col(RED)
13.                 ,_data(data)
14.         {}
15. };

复制代码

2、采用上边的方式的话，需要在RBTree中的函数模板中增加一个KeyOfT的仿函数，用于取set中的值，和map中的key进行比较。

3、迭代器的begin的位置应该找到最左节点（最小）

1. iterator begin() {
2.                 Node* min = _pHead;
3.                 while (min && min->_left) {
4.                         min = min->_left;
5.                 }
6.                 return iterator(min);
7.         }

复制代码

4、插入的返回值修改为pair<iterator,bool>范例，方便后边map的operator[]的实现
5、查找的返回值原本是Node*，而迭代器也相当于指针，所以也将放回置修改为迭代器
模拟set

set的底层就是红黑树，因此set的私有成员的范例就是红黑树。

1. RBTree<K, K, SetKeyOfT> _rt;

复制代码

set里边需要写一个仿函数，让红黑树能拿到存储的数据。并将这个仿函数范例传给红黑树

1. struct SetKeyOfT {
2.                 const K& operator()(const K& k) {
3.                         return k;
4.                 }
5.         };

复制代码

其他的接口复用红黑树的就行了。完备的代码如下：

1. #pragma once#include "RBTree1.h"template<class K>class mySet {public:        struct SetKeyOfT {
2.                 const K& operator()(const K& k) {
3.                         return k;
4.                 }
5.         };        typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;        iterator begin() {                return _rt.begin();        }        iterator end() {                return _rt.end();        }        pair<iterator,bool> insert(const K& key) {                return _rt.Insert(key);        }        iterator find(const K& key) {                return _rt.Find();        }        size_t size() {                return _rt.Size();        }private:        RBTree<K, K, SetKeyOfT> _rt;};void test_MySet() {        mySet<int> ms;        int a[] = { 7,4,1,8,5,2,9,6,3 };        for (auto e : a) {                ms.insert(e);        }        mySet<int>::iterator it = ms.begin();        while (it != ms.end()) {                cout << *it << " ";                ++it;        }        cout << endl;        cout << "size:" << ms.size() << endl;}

复制代码

模拟map

map的模拟和set雷同，底层也是红黑树。我们这里说说map的operator[]的逻辑。insert的返回值是pair<iterator, bool>范例，insert插入原来没有的数据时，返回的是新插入节点的迭代器，并返回true。如果插入原本有的数据的时间，返回的是这个存在的key的迭代器，bool值为false。而operator[]就是依赖这个insert来实现的。operator[]的返回值是value的引用，也就是说我们可以通过operator[]对value进行查找、修改和插入等操作。

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