C++ 红黑树万字详解（含模拟实现（两种版本））

目录

红黑树的概念

红黑树的性质

红黑树的删除

红黑树与AVL树的比较

红黑树的应用

红黑树的模拟实现

---

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

最长路径 <= 最短路径*2

注：虽然严格上来看，红黑树不如AVL树(红黑树的高度一般要比AVL树高)，但是实际上并没有太大的影响(因为最多也就是多出一倍的高度)，通过之前AVL树那里的测试能知道，插入 几千万 个值，AVL树的高度也就 二十几，即使高度翻一倍，查找效率还是超级快。

红黑树出现的原因：AVL树虽然已经很优秀了，但是AVL树为了控制其严格的平衡性，付出了很多的代价，比如插入和删除操作时可能需要很多次的旋转调节。

红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的 

3(重点). 如果一个节点是红色的，则它的两个孩子结点是黑色的(不存在连续的红色结点)

4(重点). 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(每条路径都存在相同数量的黑色结点) 

5. 每个叶子结点(NIL)都是黑色的(此处的叶子结点(NIL)指的是空结点)

思考：为什么满足上面的(1、2、3、4)性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

答：满足上面的性质时有：1、最短的路径就是全黑的路径。2、最长的路径就是一黑一红间隔的路径。

注：红黑树的路径指的是从根走到NIL(空)才算一条路径。

注：红黑树中一定要永远保证性质4不能被破坏。-- 所以新插入的节点一定要默认为红色

红黑树的删除

红黑树的删除这里不做讲解，有兴趣的可参考：《算法导论》或者《STL源码剖析》

https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用

1. C++ STL库 -- map / set、mutil_map / mutil_set

2. Java 库

3. linux内核

4. 其他一些库

红黑树的模拟实现

红黑树插入时单纯的颜色调整

红黑树插入时颜色调整+单旋 

 红黑树插入时颜色调整+双旋

RBTree.h

#pragma once#include<iostream>
#include<vector>
#include<assert.h>enum Color // 颜色就定义成枚举值
{BLACK,RED
};// 注：这个版本的RBTree是写死的，只适合用来给map封装，库里的操作则更nb，是一种泛型编程。template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent; std::pair<K, V> _kv;Color _col; // AVL树用的是平衡因子，红黑树用的是颜色RBTreeNode(const std::pair<K, V>& kv,Color color = RED) // 默认新增的节点为红色:_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(color){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:// 红黑树的插入和AVL树的插入是差不多的，都要遵循着二叉搜索树的规则插入，只不过AVL还可能需要调整平衡因子，而红黑树还可能需要调整颜色// 注：新插入的结点，默认为红色(可能违法红黑树的性质3)，默认为黑色的话，必然会违反红黑树的性质4。bool insert(const std::pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK; // 根结点是黑色return true;}Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;if ((cur->_kv).first < kv.first){cur = cur->_right;}else if ((cur->_kv).first > kv.first){cur = cur->_left;}else{return false;}}cur = new Node(kv); // 新增结点默认为红色if ((parent->_kv).first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent; // 上面只是完成了新节点的插入// 因为新节点的默认颜色是红色。// 因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；// 但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：// 约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点// 情况一：cur为红，p为红，g为黑，u存在且为红(还需要继续向上调整，因为调整一次之后这颗(子)树的根结点还是红色)// 解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。//	 	    (如果g本身就是这整棵树的根结点，那么g可以就保持为黑色，不用变红)//          (不过模拟实现的过程还是直接就不管三七二十一先把g变红了再说，如果最后发现g就是整棵树的根，再把g变为黑)// 注：看截图：红黑树插入时单纯的颜色调整// 情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑(无需继续向上调整，因为调整一次之后这颗(子)树的根结点已经是黑色了) // 此时又有两种情况：// 情况一(单旋)：若p为g的左孩子，cur为p的左孩子，则进行右单旋转；//			     相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转；//         所以：单旋要先将p变为黑，g变为红。(谁最后变成这颗子树的根，谁就要变黑)// 注：看截图：红黑树插入时颜色调整+单旋// 情况二(双旋)：若p为g的左孩子，cur为p的右孩子，则进行左右双旋；//			     相反，p为g的右孩子，cur为p的左孩子，则进行右左双旋；//		   注意：双旋这里会先对p进行一个单旋，单旋完之后p就变到了cur的位置，cur变到了p的位置//         所以：双旋要先将cur变为黑，g变为红。(谁最后变成这颗子树的根，谁就要变黑)// 注：看截图：红黑树插入时颜色调整+双旋// 补充：如果 u结点 不存在，则 cur结点 一定是新插入的结点，//	     因为如果 cur结点 不是新插入结点，//       则 cur结点 和 p结点 中一定有一个结点的颜色是黑色，这就会导致不满足性质4：每条路径黑色结点个数相同。//		 如果 u结点 存在且为黑，则 cur结点 原来的颜色一定是黑色的，//		 现在看到 cur结点 为红色的原因是因为 cur结点 的子树在调整的过程中将 cur结点 的颜色由黑色改为了红色。while (parent && parent->_col == RED) // 当新增结点的父亲存在且颜色也是红色的时候才需要进行调整{Node* g = parent->_parent;if (g->_left == parent){Node* u = g->_right;if (u && u->_col == RED) // 情况一{parent->_col = u->_col = BLACK;g->_col = RED;cur = g;parent = cur->_parent;}else // 情况二{if (cur == parent->_left) // 右单旋{parent->_col = BLACK;g->_col = RED;RotateR(g);}else // 左右双旋(因为红黑树没有平衡因子，所以这里的双旋没有什么其他的处理){cur->_col = BLACK;g->_col = RED;RotateL(parent);RotateR(g);}break;}}else{Node* u = g->_left;if (u && u->_col == RED) // 情况一{ parent->_col = u->_col = BLACK;g->_col = RED;cur = g;parent = cur->_parent;}else // 情况二{if (cur == parent->_right) // 左单旋{parent->_col = BLACK;g->_col = RED;RotateL(g);}else // 右左双旋(因为红黑树没有平衡因子，所以这里的双旋没有什么其他的处理){cur->_col = BLACK;g->_col = RED;RotateR(parent);RotateL(g);}break;}}}// 注：这一部分调整可以看截图_root->_col = BLACK; // 不管上面的循环最终是调整到哪结束的(可能有调整到根，可能没有)，都把根的颜色始终变为黑return true;}void RotateR(Node* parent) // 右单旋 {// 要抬高左边，降低右边Node* subL = parent->_left; Node* subLR = subL->_right; // subL 的右子树 要给给 parent，当 parent 的左子树// subL的值 < subLR的值 < parent的值parent->_left = subLR; // 将 subL 的右子树给给 parentif (subLR) // 这边要注意 subLR 可能是 nullptrsubLR->_parent = parent;subL->_right = parent; // 抬高左边subL->_parent = parent->_parent; // 要注意，要先把 parent 的 parent 给给 subLif (parent->_parent) // 还要注意改 parent 的 parent // 因为 parent 可能就是根，那么 parent 的 parent 就是 nullptr，所以这里要 if 判断一下{if (parent->_parent->_left == parent){parent->_parent->_left = subL;}else{parent->_parent->_right = subL;}}else // 如果原本的 parent 是根的话，就更新一下根{_root = subL;}parent->_parent = subL; // 降低右边}void RotateL(Node* parent) // 左单旋 {// 要抬高右边，降低左边Node* subR = parent->_right; Node* subRL = subR->_left; // subR 的左子树 要给给 parent，当 parent 的右子树// parent的值 < subRL的值 < subR的值parent->_right = subRL; // 将 subR 的右子树给给 parentif (subRL) // 这边要注意 subRL 可能是 nullptrsubRL->_parent = parent;subR->_left = parent; // 抬高右边subR->_parent = parent->_parent; // 要注意，要先把 parent 的 parent 给给 subRif (parent->_parent) // 还要注意改 parent 的 parent // 因为 parent 可能就是根，那么 parent 的 parent 就是 nullptr，所以这里要 if 判断一下{if (parent->_parent->_left == parent){parent->_parent->_left = subR;}else{parent->_parent->_right = subR;}}else // 如果原本的 parent 是根的话，就更新一下根{_root = subR;}parent->_parent = subR; // 降低右边}void InOrder(){_InOrder(_root);std::cout << std::endl;}bool IsBalance(){if (_root->_col == RED) return false; // 检查根是否为黑int ReferenceValues = 0; // 参考值，记录第一次算出的任意一条路径的黑子数量 -- 因为理论上所有路径的黑子数量要相等// 这个参考值也可以弄成全局变量(是真正的全局，不是在这个类里面定义)，但这样就需要你在每一次调用 IsBalance() 这个函数之前，把它置为0，才能保证该函数逻辑正确Node* cur = _root;while (cur){if (cur->_col == BLACK) ++ReferenceValues;cur = cur->_left; // 这里就记录一下最左路径的黑子数，记录其他路径的也行，随你。}return Check(_root, 0, ReferenceValues);}private:bool Check(Node* root, int BlackNum, const int ReferenceValues){if (root == nullptr){if (BlackNum != ReferenceValues){ std::cout << "存在黑子数不相等的路径" << std::endl; // 违法规则4return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){std::cout << "结点值为：" << root->_kv.first << "处存在连续的红色结点" << std::endl; // 违法规则3return false; // 检查有没有连续的红色结点}if (root->_col == BLACK) ++BlackNum; // 记录黑子的数量 // BlackNum要定义成函数参数，不要是全局变量，且不能用传址/传引用，不然 回溯 的时候，就需要你手动“恢复现场”return Check(root->_left, BlackNum, ReferenceValues) && Check(root->_right, BlackNum, ReferenceValues);}void _InOrder(Node* root /* = _root */) // 注意：这里不能给缺省值 _root，因为 _root 需要this指针调用，但是this指针本身就是形参，这样写玩不了。{if (root == nullptr)return;_InOrder(root->_left); // 左std::cout << (root->_kv).first << ":" << (root->_kv).second << ":" << root->_col << std::endl; //根_InOrder(root->_right); // 右}private:Node* _root=nullptr;size_t _Size = 0; // 这个 _Size 根据实际情况，可加可不加
};void Test_RBTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };int a1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a2[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;for (auto& x : a2){t.insert({ x,x });std::cout << x << "->" << t.IsBalance() << std::endl;}// t.InOrder(); // 这里有个问题，没法给 InOrder() 这个函数传参，因为 _root 是私有函数，你在这里调不动。// 那么该怎么解决呢？// 给个缺省值吗？ 这是不行的，给不了// 那该怎么办？// 三种方法：1、把这个测试函数定义成友元。(这个方法很不好，就一个测试函数又不是要经常用，定义成友元有点太没边界感了)//           2、学Java，弄一个 Get() 函数，把 _root 拿出来。//			 3、看上面的操作。(封装一下，套一层)
}void Test_RBTree2()
{const int N = 1000000;srand((unsigned int)time(nullptr));std::vector<int> v(N);RBTree<int, int> t;for (int i = 0; i < N; ++i){v[i] = rand() + i;}for (auto x : v){t.insert({ x,x });}std::cout << "t.IsBalance():" << t.IsBalance() << std::endl;
}

RBTree - 优化版.h

#pragma once// 注：这里是优化版(泛型编程)#include<iostream>
#include<vector>
#include<assert.h>enum Color // 颜色就定义成枚举值
{BLACK,RED
};template<class D>
struct RBTreeNode
{RBTreeNode<D>* _left;RBTreeNode<D>* _right;RBTreeNode<D>* _parent; D _data;Color _col;RBTreeNode(const D& data,Color color = RED):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(color){}
};template<class D, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<D> Node;typedef __RBTreeIterator<D, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}// ++ 只需要考虑中序的下一个！！Self& operator++() // 重难点！！！{// ++也是遵循着中序遍历，左 根 右 来走的if (_node->_right) // 如果右不为空{// 就去找右的最左节点Node* leftMin = _node->_right;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else // 如果右为空(右访问完了，这颗(子)树也访问完了)，就一直向上找，找到 cur == parent->_left(左访问完了，就该访问根了) 的时候{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right) // 注意：当parent为nullptr时，说明整棵树都遍历完了{cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--() // 思路就是跟++反过来{// -- 也是遵循着中序遍历，左 根 右 来走的if (_node == nullptr) // 因为按照自己写的这棵树的构造，end()会是nullptr，所以无法实现 --end()的操作，库里的可以，因为库里是用了一个哨兵位的头节点去充当这个end()。{// 要返回整棵树的最右节点，那么就需要先找到这棵树的根，但因为这里没法获取到树的根，所以实现不了	}else if (_node->_left) // 如果左不为空{// 就去找左的最右节点Node* rightMin = _node->_left;while (rightMin && rightMin->_right){rightMin = rightMin->_right;}_node = rightMin;}else // 如果左为空，就一直向上找，找到 cur==parent->_right 的时候{ Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left) // 注意：当parent为nullptr时，说明整棵树都遍历完了{cur = parent;parent = cur->_parent;}_node = parent;}return *this;}
};// 注：第二个模板参数D的设计是一种泛型编程的体现，第三个模板参数KeyOfD(一个仿函数，用于获取 Key)的设计也是一种泛型编程的体现。
template<class K,class D,class KeyOfD> // 为了避免混淆，把第二个参数取名叫D(Data，它可能是Key，也可能是pair<K,V>)
class RBTree
{typedef RBTreeNode<D> Node;
public:typedef __RBTreeIterator<D, D&, D*> iterator;typedef __RBTreeIterator<D, const D&, const D*> const_iterator;RBTree() = default; // C++11加的一个关键字，强制编译器去生成一个默认的构造函数RBTree(const RBTree<K, D, KeyOfD>& t){_root = Copy(t._root); // 这里复用 insert 是不太好的，因为插入的顺序不同，最后得到的树的形状可能也会不同(尽管值都是一样的)} RBTree<K, D, KeyOfD>& operator=(RBTree<K, D, KeyOfD> t) // 注意，赋值要用传值，不能用引用，因为下面写的是现代写法{swap(_root, t._root);return *this;}~RBTree(){Destroy(_root); // 写一个Destroy()函数去递归析构_root = nullptr;}iterator begin() // 返回中序遍历的第一个{Node* leftMin = _root;while (leftMin && leftMin->_left) // 第一个判断是处理空树的情况{leftMin = leftMin->_left;}return iterator(leftMin);}iterator end() // 返回中序遍历的最后一个的下一个(按照自己写的这棵树的构造，这个end()会是nullptr，库里是用了一个哨兵位的头节点去充当这个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 // 返回中序遍历的最后一个的下一个(按照自己写的这棵树的构造，这个end()会是nullptr，库里是用了一个哨兵位的头节点去充当这个end()){return const_iterator(nullptr);}iterator Find(const K& key) // 第一个模板参数K的作用就是体现在这种地方 -- 查找的时候只需要 Key，是按照 Key 来查找的，并不需要 Value，如果没有第一个模板参数 K，那么这里的 Find() 就要写两份，一份的参数就是 K，另一份的参数是 pair<K, V>。{KeyOfD kod;Node* cur = _root;while (cur){if (kod(cur->_data) < key){cur = cur->_right;}else if (kod(cur->_data) > key){cur = cur->_left;}else{return iterator(cur);}}return end();}// 红黑树的插入和AVL树的插入是差不多的，都要遵循着二叉搜索树的规则插入，只不过AVL还可能需要调整平衡因子，而红黑树还可能需要调整颜色// 注：新插入的结点，默认为红色(可能违法红黑树的性质3)，默认为黑色的话，必然会违反红黑树的性质4。pair<iterator,bool> Insert(const D& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK; //根结点是黑色return make_pair(iterator(_root), true);}KeyOfD kod; // RBTree是不知道这个传过来的D是Key还是pair<K,V>，所以需要在map和set中加一个仿函数用于获取D类型的data的keyNode* parent = nullptr;Node* cur = _root; while (cur){parent = cur;if (kod(cur->_data) < kod(data)){cur = cur->_right;}else if (kod(cur->_data) > kod(data)){cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data); // 新增结点默认为红色Node* newnode = cur; // 保存一下最初的cur用于最下面的返回值，不然下面的颜色调整，调整两下，cur都不知道变成哪个节点了if (kod(parent->_data) > kod(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent; // 因为新节点的默认颜色是红色。// 因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；// 但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：// 约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点// 情况一：cur为红，p为红，g为黑，u存在且为红(还需要继续向上调整，因为调整一次之后这颗(子)树的根结点还是红色)// 解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。//		    (如果g本身就是这整棵树的根结点，那么g可以就保持为黑色，不用变红)//          (不过模拟实现的过程还是直接就不管三七二十一先把g变红了再说，如果最后发现g就是整棵树的根，再把g变为黑)// 情况二：cur为红，p为红，g为黑，u不存在/u存在且为黑(无需继续向上调整，因为调整一次之后这颗(子)树的根结点已经是黑色了) // 此时又有两种情况：// 情况一(单旋)：若p为g的左孩子，cur为p的左孩子，则进行右单旋转；//			     相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转；//         所以：单旋要先将p变为黑，g变为红。// 情况二(双旋)：若p为g的左孩子，cur为p的右孩子，则进行左右双旋；//		 	     相反，p为g的右孩子，cur为p的左孩子，则进行右左双旋；//		   注意：双旋这里会先对p进行一个单旋，单旋完之后p就变到了cur的位置，cur变到了p的位置//         所以：双旋要先将cur变为黑，g变为红。// 补充：如果 u结点 不存在，则 cur结点 一定是新插入的结点，//	     因为如果 cur结点 不是新插入结点，//       则 cur结点 和 p结点 中一定有一个结点的颜色是黑色，这就会导致不满足性质4：每条路径黑色结点个数相同。//		 如果 u结点 存在且为黑，则 cur结点 原来的颜色一定是黑色的，//		 现在看到 cur结点 为红色的原因是因为 cur结点 的子树在调整的过程中将 cur结点 的颜色由黑色改为了红色。while (parent && parent->_col == RED) // 当新增结点的父亲存在且颜色也是红色的时候才需要进行调整{Node* g = parent->_parent;if (g->_left == parent){Node* u = g->_right;if (u && u->_col == RED) // 情况一{parent->_col = u->_col = BLACK;g->_col = RED;cur = g;parent = cur->_parent;}else // 情况二{if (cur == parent->_left) // 右单旋{parent->_col = BLACK;g->_col = RED;RotateR(g);}else // 左右双旋(因为红黑树没有平衡因子，所以这里的双旋没有什么其他的处理){cur->_col = BLACK;g->_col = RED;RotateL(parent);RotateR(g);}break;}}else{Node* u = g->_left;if (u && u->_col == RED) // 情况一{parent->_col = u->_col = BLACK;g->_col = RED;cur = g;parent = cur->_parent;}else // 情况二{if (cur == parent->_right) // 左单旋{parent->_col = BLACK;g->_col = RED;RotateL(g);}else // 右左双旋(因为红黑树没有平衡因子，所以这里的双旋没有什么其他的处理){cur->_col = BLACK;g->_col = RED;RotateR(parent);RotateL(g);}break;}}}// 注：这一部分调整可以看截图_root->_col = BLACK; // 不管上面的循环最终是调整到哪结束的(可能有调整到根，可能没有)，都把根的颜色始终变为黑return make_pair(iterator(newnode), true);}bool IsBalance(){if (_root->_col == RED) return false; // 检查根是否为黑int ReferenceValues = 0; // 参考值，记录第一次算出的任意一条路径的黑子数量 // 这个参考值也可以弄成全局变量(是真正的全局，不是在这个类里面定义)，但这样就需要你在每一次调用 IsBalance() 这个函数之前，把它置为0，才能保证该函数逻辑正确Node* cur = _root;while (cur){if (cur->_col == BLACK) ++ReferenceValues;cur = cur->_left; // 这里就记录一下最左路径的黑子数，记录其他路径的也行，随你。}return Check(_root, 0, ReferenceValues);}private:bool Check(Node* root, int BlackNum, const int ReferenceValues){if (root == nullptr){if (BlackNum != ReferenceValues){ std::cout << "存在黑子数不相等的路径" << std::endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){std::cout << "结点值为：" << KeyOfD()(root->_data) << "处存在连续的红色结点" << std::endl;return false; // 检查有没有连续的红色结点}if (root->_col == BLACK) ++BlackNum; // 记录黑子的数量 // BlackNum要定义成函数参数，不要是全局变量，且不能用传址/传引用，不然 回溯 的时候，就需要你手动“恢复现场”return Check(root->_left, BlackNum, ReferenceValues) && Check(root->_right, BlackNum, ReferenceValues);}void RotateR(Node* parent) //右单旋 {//要抬高左边，降低右边Node* subL = parent->_left;Node* subLR = subL->_right; //subL 的右子树 要给给 parent，当 parent 的左子树//subL的值 < subLR的值 < parent的值parent->_left = subLR; //将 subL 的右子树给给 parentif (subLR) //这边要注意 subLR 可能是 nullptrsubLR->_parent = parent;subL->_right = parent; //提高左边subL->_parent = parent->_parent; //要注意，要先把 parent 的 parent 给给 subLif (parent->_parent) //还要注意改 parent 的 parent  //因为 parent 可能就是根，那么 parent 的 parent 就是 nullptr，所以这里要 if 判断一下{if (parent->_parent->_left == parent){parent->_parent->_left = subL;}else{parent->_parent->_right = subL;}}else //如果原本的 parent 是根的话，就更新一下根{_root = subL;}parent->_parent = subL; //降低右边}void RotateL(Node* parent) //左单旋 {//要抬高右边，降低左边Node* subR = parent->_right;Node* subRL = subR->_left; //subR 的左子树 要给给 parent，当 parent 的右子树//parent的值 < subRL的值 < subR的值parent->_right = subRL; //将 subR 的右子树给给 parentif (subRL) //这边要注意 subRL 可能是 nullptrsubRL->_parent = parent;subR->_left = parent; //提高右边subR->_parent = parent->_parent; //要注意，要先把 parent 的 parent 给给 subRif (parent->_parent) //还要注意改 parent 的 parent  //因为 parent 可能就是根，那么 parent 的 parent 就是 nullptr，所以这里要 if 判断一下{if (parent->_parent->_left == parent){parent->_parent->_left = subR;}else{parent->_parent->_right = subR;}}else //如果原本的 parent 是根的话，就更新一下根{_root = subR;}parent->_parent = subR; //降低右边}// 前序拷贝Node* Copy(Node* root){if (root == nullptr) return nullptr;Node* newroot = new Node(root->_data);newroot->_col = root->_col; // 记得也要拷贝颜色Node* leftchild = Copy(root->_left);Node* rightchild = Copy(root->_right);// 父亲的指向也要记得拷贝，但要记得判断一下，左右孩子是有可能为空的if(leftchild) leftchild->_parent = newroot; if(rightchild) rightchild->_parent = newroot;newroot->_left = leftchild;newroot->_right = rightchild;return newroot;}// 后序析构void Destroy(Node* root){if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}private:Node* _root = nullptr;size_t _Size = 0; // 这个 _Size 根据实际情况，可加可不加
};//void Test_RBTree()
//{
//	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//	int a1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//	int a2[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//	RBTree<int, int> t;
//	for (auto& x : a2)
//	{
//		t.insert({ x,x });
//		std::cout << x << "->" << t.IsBalance() << std::endl;
//	}
//
//	//t.InOrder(); //这里有个问题，没法给 InOrder() 这个函数传参，因为 _root 是私有函数，你在这里调不动。
//	//那么该怎么解决呢？
//	//给个缺省值吗？ 这是不行的，给不了
//	//那该怎么办？
//	//三种方法：1、把这个测试函数定义成友元。(这个方法很不好，就一个测试函数又不是要经常用，定义成友元有点太没边界感了)
//	//          2、学Java，弄一个 Get() 函数，把 _root 拿出来。
//	//			 3、看上面的操作。(封装一下，套一层)
//}
//
//void Test_RBTree2()
//{
//	const int N = 1000000;
//	srand((unsigned int)time(nullptr));
//
//	std::vector<int> v(N);
//
//	RBTree<int, int> t;
//
//	for (int i = 0; i < N; ++i)
//	{
//		v[i] = rand() + i;
//	}
//
//	for (auto x : v)
//	{
//		t.insert({ x,x });
//	}
//	std::cout << "t.IsBalance():" << t.IsBalance() << std::endl;
//}