基于红黑树的插入功能，对Set和Map部分功能进行封装实现

一、红黑树的迭代器

        在上一篇中，对红黑树的插入功能进行了实现，但是要封装出set和map，还需要实现出红黑树的迭代器。

        红黑树的迭代器本质上还是红黑树树结点的指针，但是需要实现一些符号重载：

template<class T, class ref, class ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, ref, ptr> Self;Node* _node = nullptr;RBTreeIterator(Node* node):_node(node){}Self& operator++() {if (_node->_right != nullptr) {_node = _node->_right;while (_node->_left != nullptr) {_node = _node->_left;}return *this;}else {Node* parent = _node->_parent;Node* cur = _node;while (parent && cur == parent->_right) {cur = parent;parent = cur->_parent;}_node = parent;return *this;}}ref operator*() {return _node->_data;}ptr operator->() {return &(_node->_data);}bool operator!=(const Self& s)const {return s._node != _node;}bool operator==(const Self& s)const {return s._node == _node;}
};

 1.1 operator++的重载

        由于红黑树 本质上还是搜索二叉树，迭代器在移动时，是按照中序遍历的顺序进行移动，以便于在进行范围for等操作时，有序输出。

        因此，++操作，我们需要知道的就是，一个结点在中序遍历的情况下，下一个结点该如何寻找。

        我们以4结点为例子，假如要对4进行++，下一个结点应该是5，而5与4的关系就是，5是4结点右子树中最左的结点，因此，如果一个结点有右子树，就去找右子树最左的结点。

        那么再看5，5的下一个结点应该是6，按照第一步来判断，5结点右子树为空，因此需要向上查找，6是5的父结点，那么就直接找父结点吗？

        再来看看3结点，3结点的下一个结点是4，并不是3结点的父结点。这又有什么规律呢？其实与结点和父结点之间的位置决定。

        由于中序遍历是左根右，如果3结点被访问，3结点又是2结点的右子树，说明2结点以及之前的结点一定被访问过了。

        因此，当右子树不存在时，需要向上寻找，直到找到子树是父结点的左子树的父结点，例如：5是6的左子树，那么下一个结点就是6结点。

1.2 const_iterator的实现

        红黑树的const_iterator与list的实现相同，通过增加两个模板参数，封装出两个不同版本的iterator，即：

        如果传过来的模板参数是<T, T&, T*>那么就是普通的iterator，如果传过来的是<T, const T&, const T*>那么就是const_iterator。

二、对红黑树进行修改

        由于set与map的数据类型不一样，如果说set的数据类型是T，那么map的数据类型就是pair<K, T>，如果不是按照上一篇中的K,V结构红黑树来进行封装，在读取map的数据进行插入时，就会出现问题，因为pair的大小比较，不仅会涉及到K，还会涉及到T。因此，对红黑树进行修改，同时，也在map和set中增加一个伪函数，传入红黑树中，用来读取插入数据中的K，从而进行比较：

template<class K, class T, class KOT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> iterator;typedef RBTreeIterator<T, const T&, const T*> const_iterator;iterator begin() {Node* tmp = _root;while (tmp->_left != nullptr) {tmp = tmp->_left;}return tmp;}iterator end() {return nullptr;}const_iterator begin() const{if (_root == nullptr) return nullptr;Node* tmp = _root;while (tmp->_left != nullptr) {tmp = tmp->_left;}return tmp;}const_iterator end() const{return nullptr;}~RBTree(){Destroy(_root);_root = nullptr;}void clear() {Destroy(_root);_root = nullptr;}iterator find(const K& key) {Node* tmp = _root;KOT kot;while (tmp) {if (kot(tmp->_data) < key) {tmp = tmp->_right;}else if (kot(tmp->_data) > key) {tmp = tmp->_left;}else {return tmp;}}return nullptr;}pair<Node*, bool> Insert(const T& kv) {if (_root == nullptr) {_root = new Node(kv);_root->_col = BLACK;return make_pair(_root, true);}Node* cur = _root;Node* parent = nullptr;KOT kot;while (cur) {parent = cur;if (kot(cur->_data) < kot(kv)) {cur = cur->_right;}else if (kot(cur->_data) > kot(kv)) {cur = cur->_left;}else {return make_pair(cur, false);}}cur = new Node(kv);cur->_parent = parent;if (kot(parent->_data) > kot(kv)) {parent->_left = cur;}else {parent->_right = cur;}if (parent->_col == BLACK) {return make_pair(cur,true);}Node* pp = parent->_parent;while (parent && pp) {Node* uncle = nullptr;if (parent == pp->_left) {uncle = pp->_right;}else {uncle = pp->_left;}if (uncle != nullptr && uncle->_col == RED) {parent->_col = BLACK;pp->_col = RED;uncle->_col = BLACK;cur = pp;if (cur->_parent == nullptr) {cur->_col = BLACK;return make_pair(cur,true);}if (cur->_parent->_col == BLACK) return make_pair(cur,true);parent = cur->_parent;pp = parent->_parent;}else {if (parent == pp->_left && cur == parent->_left) {RotateR(pp);parent->_col = BLACK;pp->_col = RED;}else if (parent == pp->_left && cur == parent->_right) {RotateLR(pp);cur->_col = BLACK;pp->_col = RED;}else if (parent == pp->_right && cur == parent->_left) {RotateRL(pp);cur->_col = BLACK;pp->_col = RED;}else {RotateL(pp);parent->_col = BLACK;pp->_col = RED;}break;}}while (parent != nullptr && parent->_parent != nullptr) {parent = parent->_parent;}_root = parent;return make_pair(cur,true);}bool IsBalanceTree(){if (_root == nullptr)return true;if (_root->_col == RED)return false;// 参考值int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return Check(_root, 0, refNum);}void InOrder() {_InOrder(_root);}private:void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}// 前序递归遍历bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){// 前序遍历走到空时，意味着一条路径走完了//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色结点的数量不相等的路径" << endl;return false;}return true;}// 检查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲就方便多了if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色结点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}// 右单旋void RotateR(Node* pParent) {Node* cur = pParent->_left;pParent->_left = cur->_right;cur->_right = pParent;if (pParent->_left != nullptr) {pParent->_left->_parent = pParent;}cur->_parent = pParent->_parent;pParent->_parent = cur;if (cur->_parent != nullptr) {if (cur->_parent->_left == pParent) {cur->_parent->_left = cur;}else {cur->_parent->_right = cur;}}}// 左单旋void RotateL(Node* pParent) {Node* cur = pParent->_right;pParent->_right = cur->_left;cur->_left = pParent;if (pParent->_right != nullptr) {pParent->_right->_parent = pParent;}cur->_parent = pParent->_parent;pParent->_parent = cur;if (cur->_parent != nullptr) {if (cur->_parent->_left == pParent) {cur->_parent->_left = cur;}else {cur->_parent->_right = cur;}}}// 右左双旋void RotateRL(Node* pParent) {Node* cur = pParent->_right;Node* left = cur->_left;RotateR(cur);RotateL(pParent);}// 左右双旋void RotateLR(Node* pParent) {Node* cur = pParent->_left;Node* right = cur->_right;RotateL(cur);RotateR(pParent);}Node* _root = nullptr;
};

 此时，树的结点类型，也不再是K,V而是T：

template<class T>
struct RBTreeNode
{// 这里更新控制平衡也要加入 parent指针T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Colour _col;RBTreeNode(const T& kv):_data(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};

        那么红黑树的修改，到这里就完成了。

三、Set与Map的封装

3.1 Set

        由于对红黑树进行了一系列修改，那么，我们只需要增加一个读取数据中K值的伪函数，然后传入红黑树即可：

template<class K>
class set
{typedef K ValueType;struct KeyOfValue{const K& operator()(const ValueType& data){return data;}};typedef RBTree<K, ValueType, KeyOfValue> RBTree;typename typedef RBTree::const_iterator iterator;typename typedef RBTree::const_iterator const_iterator;
public:set() : t() {}iterator begin() const{return t.begin();}iterator end() const{return t.end();}bool empty()const {return t == nullptr;}size_t size()const {size_t i = 0;for (auto& e : t) {i++;}return i;}///// modifypair<iterator, bool> insert(const ValueType& data) {return t.Insert(data);}void clear() {t.clear();}iterator find(const K& key) {return t.find(key);}
private:RBTree t;
};

3.2 Map

        map也是同样的，唯一需要注意的就是，需要多实现一个对operator[]的重载，在了解了原理以后，实现起来也并不困难：

template<class K, class V>
class map
{typedef pair<K, V> ValueType;struct KeyOfValue{const K& operator()(const ValueType& data){return data.first;}};typename typedef RBTree<K, pair<const K, V>, KeyOfValue>::iterator iterator;typename typedef RBTree<K, pair<const K, V>, KeyOfValue>::const_iterator const_iterator;
public:map() : t() {}iterator begin() {return t.begin();}iterator end() {return t.end();}const_iterator begin() const{return t.begin();}const_iterator end() const{return t.end();}bool empty()const {return t == nullptr;}size_t size()const {size_t i = 0;for (auto& e : t) {i++;}return i;}V& operator[](const K& key) {pair<iterator, bool> a = t.Insert(make_pair(key,V()));return a.first->second;}pair<iterator, bool> insert(const ValueType& data) {return t.Insert(data);}void clear() {t.clear();}iterator find(const K& key) {return t.find(key);}
private:RBTree<K, pair<const K, V>, KeyOfValue> t;
};