C++模拟实现map和set

模拟实现map和set实际上是对红黑树的封装，如对红黑树的实现有疑问，请移步：C++手撕红黑树

1、STL源代码分析

map和set的底层都是红黑树，但是对于set来说，只存储key，而对于map来说，需要存储key和value——也就是pair类型。那么我们是实现两份红黑树的代码吗？实则不然，因为他们只有存储类型上的区别，所以我们要尽量的实现代码复用，通过对一份红黑树的代码封装同时实现map和set。
我们先来看看库里是怎么实现的：

我们可以看到，树的节点是继承了一个__rb_tree_node_base的类，这个基类存储了颜色、左孩子、右孩子、父亲的指针，继承后多了一个value_field的变量，这个变量实际上就是存储的数据类型。

---

继续往下看：

map的前两个模板参数：Key和T对应的就是key和value。将Key重命名为key_type，将pair<Key, T>重命名为value_type。然后将key_type和value_type作为模板参数传给红黑树。
set有一个Key模板参数，将Key重命名为key_type，还将Key重命名为value_type。然后将这两个作为模板参数传给红黑树。
红黑树的前两个模板参数为：Key和Value。红黑树内部将Value作为模板参数传给了红黑树的节点，红黑树的节点中通过Value声明了value_field成员变量，value_field就是存储的数据类型，所以红黑树是通过模板参数Value来控制存储的类型的。
我们分析发现，当使用的是map时，会将pair<K, V>传给红黑树的模板参数Value，红黑树存储的数据类型就是pair<K, V>。当使用的是set时，就会将Key传给红黑树的模板参数Value，这时候Key就是存储的数据类型。

接下来，我们开始封装实现map和set，请你思考一下：既然红黑树这里是通过模板参数Value来控制数据类型的，那么是不是就不需要传Key了？

---

2、实现出复用红黑树的框架

首先我们来修改红黑树的代码：我们将存储的数据类型统一定义为T。先修改节点的模板参数，然后修改红黑树的模板。注意：由于修改了模板参数名，因此类内涉及模板参数名的代码都需要修改。

template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class K, class T>
class RBTree
{typedef RBTreeNode<T> Node;
private:Node* _root = nullptr;
};

---

然后创建新文件：MySet.h和MyMap.h

#pragma once
#include "RBTree.h"namespace zzy
{template<class K>class set{public:private:RBTree<K, K> _t;};
}

#pragma once
#include "RBTree.h"namespace zzy
{template<class K, class V>class map{public:private:RBTree<K, pair<K, V>> _t;};
}

---

由于节点存储的数据类型我们改为_data，因此在红黑树中访问数据的代码都得修改。我们先来看Insert的修改：

bool Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_data < data){parent = cur;cur = cur->_right;}else if (cur->_data > data){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data);if (parent->_data < data)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;return true;
}

在插入数据的过程中，需要将插入的数据data和当前节点的数据_data进行比较，如果是set就可以直接比，如果是map需要按key比。但是这里的比较有问题：当T为pair时，cur->_data和data就是两个pair的比较了，那么我们看看库里pair是否重载了比较，如果重载了是否满足我们的需求？

库里果然实现了pair类的六个运算符重载比较函数，那么是否满足我们的要求？——按key，也就是first来比较。

阅读代码：库里实现的operator<是先比较first是否小于，如果first不小于再比较second是否小于。也就是说如果first小于则返回true，如果frist不小于但是second小于也返回true，这种比较方式是不符合我们的需求的。因此我们要自己实现比较。
那么如何实现呢？——仿函数

我们发现红黑树的模板参数还存在KeyOfValue，这个名字很形象，就是取出Value中的Key。对于set，传入key直接将key返回。对于map，传入pair<key, value>，将key返回。
仿函数——可以像函数一样实现，实际上就是重载了operator()。所以我们需要在map和set中自己定义并将类传给红黑树，然后在红黑树中实例化对象，然后通过operator()取出T中的key，然后进行比较。
实现如下：这里我们直接定义为内部类更为方便

#pragma once
#include "RBTree.h"namespace zzy
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:private:RBTree<K, K, SetKeyOfT> _t;};
}

#pragma once
#include "RBTree.h"namespace zzy
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:private:RBTree<K, pair<K, V>, MapKeyOfT> _t;};
}

然后给红黑树添加一个模板参数，并修改Insert函数如下：

bool Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(data);if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;return true;
}

在Insert函数中，我们通过KeyOfT创建出kot对象，然后通过kot()并传入数据对象，该函数会将key返回。这样对于set，传入key返回key，没有变化。对于map传入pair<K, V>，返回pair的first。这样就可以适配map和set的比较了。这里可以说是set迁就于map，因为set本身就是key，但是map需要获取key。
其他函数如Erase、Find修改也是类似的，需要通过KeyOfT创建出kot对象，通过kot()仿函数来获取key进行比较。其他函数请你自行修改。

修改完毕后，可以将map和set的insert函数写出来，然后测试一下。
针对前面的问题：红黑树这里还是需要传入Key的，因为我们在查找、删除函数中需要用到。其他函数代码请你自行修改。

---

3、实现红黑树的迭代器

这里类似前面的list，由于空间不连续，所以我们需要创建自定义类型。
先来看看库里的实现：

基本上类似前面list的迭代器实现，只不过红黑树这里迭代器进行++和--会稍微复杂一点。
红黑树的迭代器遍历本质上是中序遍历，因此begin我们返回的是最左节点(最小节点)，end我们返回最右节点的下一个数据就是nullptr。
我们先把其他函数写出来，这里的Ref和Ptr就是为了控制实现普通迭代器和const迭代器的。

template<class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;Node* _node;__TreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(operator*());}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

---

下面我们要实现operator++和operator--：

Self& operator++()
{if (_node->_right){Node* subLeft = _node->_right;while (subLeft->_left)subLeft = subLeft->_left;_node = subLeft;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}Self operator++(int)
{Self tmp(_node);++* this;return tmp;
}Self& operator--()
{if (_node->_left){Node* subRight = _node->_left;while (subRight->_right)subRight = subRight->_right;_node = subRight;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}Self operator--(int)
{Self tmp(_node);--* this;return tmp;
}

紧接着在红黑树中加入如下代码：

typedef __TreeIterator<T, T&, T*> iterator;
typedef __TreeIterator<T, const T&, const T*> const_iterator;iterator begin()
{Node* leftMin = _root;while (leftMin && leftMin->_left)leftMin = leftMin->_left;return iterator(leftMin);
}iterator end()
{return iterator(nullptr);
}const_iterator begin() const 
{Node* leftMin = _root;while (leftMin && leftMin->_left)leftMin = leftMin->_left;return iterator(leftMin);
}const_iterator end() const
{return iterator(nullptr);
}

然后在map和set中加入迭代器，就可以配合insert来进行测试了：

typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}

typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}

---

上图是库里的实现方式，库里多了一个哨兵位的头节点，左孩子指向树中最左节点(最小节点)，右孩子指向树中最右节点(最大节点)。通过这种实现方式可以快速返回begin()，但是也带来了维护较为麻烦的问题。这里了解一下即可。

---

4、解决map和set中key不可修改问题

测试insert和迭代器通过后，我们还需要解决map和set中key不可修改的问题。而现在我们的迭代器是可以修改的。那么如何实现呢？

对于set来说，不管是普通迭代器还是const迭代器都是不可修改的，所以直接将const迭代器作为普通迭代器来使用，这是库里的解决方式。

但是这么写会报错，因此_t还是普通对象，走的还是普通迭代器的begin，调用树的begin返回的也是普通迭代器，所以就出现了普通迭代器无法向const迭代器转换的问题。
处理方式：
1、支持普通迭代器构造const迭代器。
2、类似库里的实现方式。直接在后面加上const。不实现普通类型的迭代器函数了。

如上图，这样就解决了。

---

set的问题解决了，下面看map，map能这样实现吗？
答案是不行的，如果这样的话整个pair都不能修改了，不仅key不能修改，value也不能修改。但是我们只要key不可修改，value是可以修改的。
下面看库里的实现方式：

直接用const将key锁死，这样value还是可以修改的。

---

5、解决insert返回值问题

之前介绍map和set的使用，insert的返回值是一个pair<iterator, bool>的对象，现在我们需要对红黑树的返回值进行修改，同时实现map的operator[]重载函数。

我们将红黑树的insert函数返回值修改为pair<iterator, bool>，插入成功返回piar<新插入节点的迭代器，true>，插入失败返回pair<已存在节点的迭代器，false>。然后对map和set中insert的返回值进行修改。
修改后运行程序发现：

这是因为在set这里，无论是iterator还是const_iterator，它们实际上都是const_iterator。而我们的树是普通对象，调用insert之后返回的是普通的迭代器，所以就出现了pair<iterator，bool>向pair<const_iterator，bool>进行转换。但是这里是无法转换的。
我们可以这样处理：

pair<iterator, bool> insert(const K& key)
{pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);
}

先接受红黑树底层的返回值，然后通过ret.first和ret.second去构造新的pair返回。
但是现在还是无法运行：

这是因为ret.first是普通迭代器，要构造的pair的first是const迭代器，不支持普通迭代器向const迭代器的转换。所以我们需要实现一个普通迭代器构造const迭代器的函数，如下：

无论类模板实例化出const迭代器还是普通迭代器，这里的Iterator都是普通迭代器。
1、这个类被实例化为const迭代器时，这个函数是一个构造函数，支持普通迭代器向const迭代器转换。
2、这个类被实例化为普通迭代器时，这个函数是一个拷贝构造函数。

---

修改了Insert函数的返回值就可以来实现map中operator[]的重载了：

pair<iterator, bool> insert(const pair<K, V>& kv)
{return _t.Insert(kv);
}V& operator[](const K& key)
{pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;
}

---

完整代码

// MySet.h
#pragma once
#include "RBTree.h"namespace zzy
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& key){pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree<K, K, SetKeyOfT> _t;};
}

// MyMap.h
#pragma once
#include "RBTree.h"namespace zzy
{template<class K, class V>class map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}

// RBTree.h
#pragma onceenum Colour {RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class T, class Ref, class Ptr>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ref, Ptr> Self;typedef __TreeIterator<T, T&, T*> Iterator;Node* _node;__TreeIterator(Node* node):_node(node){}__TreeIterator(const Iterator& it):_node(it._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(operator*());}Self& operator++(){if (_node->_right){Node* subLeft = _node->_right;while (subLeft->_left)subLeft = subLeft->_left;_node = subLeft;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self operator++(int){Self tmp(_node);++* this;return tmp;}Self& operator--(){if (_node->_left){Node* subRight = _node->_left;while (subRight->_right)subRight = subRight->_right;_node = subRight;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self operator--(int){Self tmp(_node);--* this;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator<T, T&, T*> iterator;typedef __TreeIterator<T, const T&, const T*> const_iterator;iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left)leftMin = leftMin->_left;return iterator(leftMin);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left)leftMin = leftMin->_left;return const_iterator(leftMin);}const_iterator end() const{return const_iterator(nullptr);}RBTree():_root(nullptr){}RBTree(const RBTree<K, T, KeyOfT>& t):_root(nullptr){_root = Copy(t._root, nullptr);}RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);}pair<iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < kot(data)){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > kot(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);if (kot(parent->_data) < kot(data))parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;Node* newnode = cur;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateL(parent);RotateR(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);grandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);}bool Erase(const K& key){KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->_data) < key){parent = cur;cur = cur->_right;}else if (kot(cur->_data) > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (_root == cur){_root = cur->_right;if (_root){_root->_parent = nullptr;_root->_col = BLACK;}delete cur;return true;}}else if (cur->_right == nullptr){if (_root == cur){_root = cur->_left;if (_root){_root->_parent = nullptr;_root->_col = BLACK;}delete cur;return true;}}else{parent = cur;Node* rightMin = cur->_right;while (rightMin->_left){parent = rightMin;rightMin = rightMin->_left;}cur->_data = rightMin->_data;cur = rightMin;}break;}}if (cur == nullptr) return false;Node* del = cur;Node* delParent = parent;if (cur->_col == BLACK && !cur->_left && !cur->_right){while (parent){if (parent->_left == cur){Node* brother = parent->_right;if (brother->_col == RED){brother->_col = BLACK;parent->_col = RED;RotateL(parent);brother = parent->_right;}if ((!brother->_left || brother->_left->_col == BLACK)&& (!brother->_right || brother->_right->_col == BLACK)){brother->_col = RED;if (parent->_col == RED){parent->_col = BLACK;break;}cur = parent;parent = cur->_parent;}else{if (!brother->_right || brother->_right->_col == BLACK){brother->_left->_col = BLACK;brother->_col = RED;RotateR(brother);brother = parent->_right;}brother->_right->_col = BLACK;brother->_col = parent->_col;parent->_col = BLACK;RotateL(parent);break;}}else{Node* brother = parent->_left;if (brother->_col == RED){brother->_col = BLACK;parent->_col = RED;RotateR(parent);brother = parent->_left;}if ((!brother->_left || brother->_left->_col == BLACK)&& (!brother->_right || brother->_right->_col == BLACK)){brother->_col = RED;if (parent->_col == RED){parent->_col = BLACK;break;}cur = parent;parent = cur->_parent;}else{if (!brother->_left || brother->_left->_col == BLACK){brother->_right->_col = BLACK;brother->_col = RED;RotateL(brother);brother = parent->_left;}brother->_left->_col = BLACK;brother->_col = parent->_col;parent->_col = BLACK;RotateR(parent);break;}}}}cur = del, parent = delParent;if (cur->_left == nullptr){if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;if (cur->_right){cur->_right->_parent = parent;cur->_right->_col = BLACK;}}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;if (cur->_left){cur->_left->_parent = parent;cur->_left->_col = BLACK;}}delete cur;return true;}Node* Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key)cur = cur->_right;else if (kot(cur->_data) > key)cur = cur->_left;elsereturn cur;}return nullptr;}bool IsBalance(){return IsBalance(_root);}int Height(){return Height(_root);}void InOrder(){InOrder(_root);cout << endl;}private:void InOrder(Node* root){if (root == nullptr) return;InOrder(root->_left);cout << root->_kv.first << " ";InOrder(root->_right);}int Height(Node* root){if (root == nullptr) return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;}Node* Copy(Node* root, Node* parent){if (root == nullptr) return nullptr;Node* copy = new Node(root->_kv);copy->_col = root->_col;copy->_parent = parent;copy->_left = Copy(root->_left, copy);copy->_right = Copy(root->_right, copy);return copy;}void Destroy(Node*& root){if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}bool IsBalance(Node* root){if (root == nullptr) return true;if (root->_col != BLACK) return false;int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK) benchmark++;cur = cur->_left;}return CheckColour(root, 0, benchmark);}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark) return false;return true;}if (root->_col == BLACK) blacknum++;if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续的红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;parent->_right = curleft;if (curleft)curleft->_parent = parent;cur->_left = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent)ppnode->_left = cur;elseppnode->_right = cur;cur->_parent = ppnode;}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;parent->_left = curright;if (curright)curright->_parent = parent;cur->_right = parent;parent->_parent = cur;if (_root == parent){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent)ppnode->_left = cur;elseppnode->_right = cur;cur->_parent = ppnode;}}
private:Node* _root = nullptr;
};