红黑树的简单介绍
定义
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，只能是 Red 或 Black。 通过对任何一条从根到空节点的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，即最长路径的长度最多是最短路径长度的两倍，这样的话就能保证红黑树是接近平衡的树。
红黑树的特性
红黑树通过以下特性来保持树的平衡，保证最长路径的长度最多是最短路径长度的两倍：
- 节点颜色：每个节点只能是红色或黑色。
- 根节点：树的根节点是黑色。
- 红色规则：如果一个节点是红色，则它的两个子节点都是黑色（也就是说，一条路径不能有两个连续的红色节点）。
- 黑色高度：从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
- 空节点：所有的空节点（NIL 节点，通常是叶子节点的子节点）都是黑色。
为什么满足上面的特性，红黑树就能保证最长路径的长度最多是最短路径长度的两倍呢？
其实很好理解：
- 特性 2：根节点是黑的
- 特性 4：每条路径的黑色节点个数是相同的
- 特性 5：所有的空节点（NIL 节点，通常是叶子节点的子节点）都是黑色
那么任何一个红黑树可能出现的最短路径就是只有黑色节点的路径，因为每条路径的黑色节点个数是相同的。 而任何一个红黑树可能出现的最长路径就是一黑一红交替的路径。
因为：
- 特性 1：每个节点只能是红色或黑色
- 特性 3：每一条路径都不可能出现连续的红色节点
- 特性 4：每条路径的黑色节点个数是相同的
所以最短路径和最长路径的黑色节点个数一样，最长也只能是黑红节点交替出现。因此可能的最短的路径是全黑节点，可能的最长路径是一黑一红交替出现的路径，红黑节点个数相同。如果全黑节点的路径长度为 h，那么一黑一红交替出现的路径长度最多只能是 2*h。
红黑树的应用
红黑树是一种高效的自平衡二叉搜索树，因其出色的性能和良好的平衡特性，在计算机科学中被广泛应用。以下是红黑树的一些主要应用场景：
- Java 和 C++ 中的集合和数据结构：
- 在 Java 中，红黑树被用于实现
TreeSet和TreeMap，分别提供有序集合和有序映射的功能。 - 在 C++ 中，红黑树是
std::set、std::multiset、std::map和std::multimap的底层数据结构。
- 在 Java 中，红黑树被用于实现
- 数据库索引：红黑树常用于数据库系统中，作为索引结构来提高数据查询和更新的效率。
- 操作系统的内存管理：在操作系统中，红黑树可用于管理内存分配。例如，在 Linux 的虚拟内存管理中，红黑树被用来维护页面分配的信息。
- 文件系统和文件管理：在文件系统中，红黑树可以用来存储文件元数据，比如文件名、大小和修改时间等信息，以便快速检索和排序。
- 网络协议和算法：在一些网络协议的实现中，红黑树可以用来管理连接状态或路由表。
- 图形渲染和游戏开发：在图形渲染和游戏开发中，红黑树可用于管理场景中的物体。
- 科学计算和数据分析：在科学计算和数据分析中，红黑树可以用于管理大量的有序数据。
准备工作
创建两个文件，一个头文件 RBTree.hpp，一个源文件 test.cpp。
【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件 RBTree.hpp 中】
- RBTree.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义。
- test.cpp：存放 main 函数，以及测试代码。
包含头文件
- iostream：用于输入输出
- cmath：提供数学函数
类的成员变量和红黑树节点的定义
红黑树类的成员变量只有一个，就是指向红黑树的根节点的指针。
红黑树的节点类：
为什么红黑树新插入的节点一定是红色的？其实就是维护成本的问题：
- 如果新插入的节点为黑色：因为插入之前，这棵树一定是红黑树，所以他的每一条路径上的黑色节点个数都相同。但是因为你新插入了一个黑色的，这一条路径就会比其他路径多一个黑色节点，为了保持红黑树的规则（每一条路径上的黑色节点个数都相同），就得想办法让每一条路径也都增加一个黑色节点，维护成本太高了。
- 如果新插入的节点为红色：
- ① 新插入的节点的父亲为黑色，就可以直接结束了，因为满足红黑树的所有规则。
- ② 就算新插入的节点的父亲为红色，调整的情况也只有两种，维护成本更低。
构造函数和拷贝构造
构造函数没什么好说的，默认构造就行了。
RBTree():_root(nullptr){ }
拷贝构造：因为节点都是从堆区 new 出来的，所以要深拷贝。 使用递归实现深拷贝：因为拷贝构造不能有多余的参数，但是递归函数又必须使用参数记录信息。
然后在拷贝构造里面调用一下这个函数就行了。
RBTree(const RBTree& obj){ _root =Copy(obj._root,nullptr);}
swap 和赋值运算符重载
交换两颗红黑树的本质就是交换两颗数的资源（数据），而它们的资源都是从堆区申请来的，然后用指针指向这些资源。 并不是把资源存储在了红黑树对象中，所以资源交换很简单，直接交换_root 指针的指向即可。
void Swap(RBTree& obj){ std::swap(_root, obj._root);}
赋值运算符重载
RBTree&operator=(RBTree obj){ this->Swap(obj);return*this;}
为什么上面的两句代码就可以完成深拷贝呢？这是因为使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去。赋值运算符的左操作数，this 再与传入的临时对象 obj 交换，就直接完成了拷贝。在函数结束之后，存储在栈区的 obj 再函数结束之后，obj 生命周期结束，obj 调用析构函数，把指向的从this 那里交换来的不需要的空间销毁。
析构函数
使用递归遍历，把所有从堆区申请的节点都释放掉：因为析构函数不能有多余的参数，但是递归函数又必须使用参数记录信息，所以再封装一个成员函数，专门用来递归释放。
然后在拷贝构造里面调用一下这个函数就行了。
~RBTree(){ Destroy(_root); _root =nullptr;}
find
具体流程：从根节点开始，将目标值（传入的 key）与当前节点的 key 进行比较。如果目标值小于当前节点值，则在左子树中继续查找；如果目标值大于当前节点值，则在右子树中继续查找。这个过程一直进行，直到找到与目标值或者到达空节点为止。
把上述过程转成代码：
insert【重要】
红黑树就是在二叉搜索树的基础上节点有了颜色，因此红黑树也可以看成是二叉搜索树。
那么 AVL 树的插入过程可以分为两步：
- 先按照二叉搜索树的方式插入新节点
- 再调整颜色，维护红黑树的规则
第一步：按照二叉搜索树的方式插入新节点
插入的具体过程如下：
- 树为空，则直接新增节点，赋值给二叉搜索树的成员变量_root 指针
- 树不空，则按照查找（find）的逻辑找到新节点应该插入的位置
- 树不空，如果树中已经有了一个节点的 key 值与要插入的节点的 key 相同，就插入失败
这个过程一直进行，直到找到与传入的 key 相等的节点或者到达空节点为止。
把上述过程转成代码：
第二步：调整颜色，维护红黑树的规则
颜色调整分以下 3 种情况：
- 新插入的节点（cur）的父亲节点（parent）颜色为黑
- 新插入的节点（cur）的父亲节点（parent）颜色为红，且叔叔（uncle）节点不为空且为红
- 新插入的节点（cur）的父亲节点（parent）颜色为红，且叔叔（uncle）节点为空或者为黑
情况一：新插入的节点的父亲节点颜色为黑
此时插入节点，并没有违反任何红黑树规则，所以不需要调整颜色/树的结构，直接结束插入就行。
情况二：新插入的节点的父亲节点颜色为红，且叔叔节点不为空且为红
（cur 为新插入的节点，g 是爷爷节点，u 是父亲的兄弟节点；a，b，c，d，e 是都是符合条件的红黑树） cur 的位置是不固定的，cur 也可以是上图的 c，d，e，cur 的 p，g，u 相应的改变即可。最主要看的是 cur 和它的 g，p，u 的颜色，是否满足情况一。
因为插入的节点的颜色为红色，而且它的父亲节点也是红色，那么它就违反了红黑树的第 3 条规则：同一路径不能出现连续的红色节点，所以必须进行调整。 因为叔叔节点不为空且为红，所以没有严重违反红黑树的规则，只需要对颜色进行调整即可。
所以调整方案是： ①把 p，u 都变黑，把 g 变红：这样就能让连续的红色节点去除，但是 g（爷爷接节点）变成红色了，g 的父亲节点也可能是红色，所以需要 ②再把 g 看作 cur 继续循环向上调整，再根据新的 c,p,u,g 节点的颜色，判断是情况一，情况二还是情况三。
具体实现代码：
情况三：新插入的节点的父亲节点颜色为红，且叔叔节点为空或者为黑
【此时 cur 的位置也是不固定的，cur 也可以是上图的 c，d，e，cur 的 p，g，u 相应的改变即可。最主要看的是 cur 和它的 g，p，u 的颜色，是否满足情况二】
因为插入的节点的颜色为红色，而且它的父亲节点也是红色，那么它就违反了红黑树的第 3 条规则：同一路径不能出现连续的红色节点，所以必须进行调整。 因为叔叔（uncle）节点为空或者为黑，所以严重违反红黑树的规则，需要调整红黑树的部分结构和调整颜色。
所以此时的调整方案是：先旋转 [根据 cur，p 和 g 的相对位置，进行左旋，右旋，双旋]，再变颜色。
①单旋：p 变黑，g 变红。因为单旋之后，p 就变成了 c，p，g 及其子树组成的这棵树的根节点。然后又因为 g 是黑色，所以他旋转下去的话，那么 c 那条路径就会比其他路径少一个黑色节点，所以需要把作为新的根节点的 p 变黑，这样 c 那条路径的黑色节点数量才会与其他路径上的相同。但是这样又会让 g 那条路径比其他的路径多一个黑色节点，所以再把 g 变红。
②双旋：c 变黑，g 变红。因为单旋之后，c 就变成了 c，p，g 及其子树组成的这棵树的根节点。然后的推导就与单旋的类似了。
具体代码实现：
empty
bool empty() const { return _root == nullptr; }
size
使用递归实现二叉搜索树的节点个数统计：因为我们经常使用的 stl 的容器的 size 都是没有参数的，但是递归函数又必须使用参数记录信息，所以再封装一个成员函数，专门用来递归。
然后再 size 里面调用一下就行了。
size_t size() const { return _size(_root); }
完整代码示例
（此处省略完整代码，参考上文各部分实现整合）
