红黑树的定义、特性及应用场景，详细讲解了基于 C++ 的红黑树节点结构、构造函数、拷贝构造、析构函数及核心插入操作（包括颜色调整与旋转）的实现逻辑，并对比了红黑树与 AVL 树的区别。内容涵盖节点颜色规则、插入后的三种调整情况（父黑、叔红、叔黑）、旋转操作及基本接口实现。
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，只能是 Red 或 Black。 通过对任何一条从根到空节点的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，即最长路径的长度最多是最短路径长度的两倍，这样的话就能保证红黑树是接近平衡的树。
红黑树通过以下特性来保持树的平衡，保证最长路径的长度最多是最短路径长度的两倍：
为什么满足上面的特性，红黑树就能保证最长路径的长度最多是最短路径长度的两倍呢？
其实很好理解：
那么任何一个红黑树可能出现的最短路径就是只有黑色节点的路径，因为每条路径的黑色节点个数是相同的。 而任何一个红黑树可能出现的最长路径就是一黑一红交替的路径。
因为：
所以最短路径和最长路径的黑色节点个数一样，最长也只能是黑红节点交替出现。因此可能的最短的路径是全黑节点，可能的最长路径是一黑一红交替出现的路径，红黑节点个数相同。如果全黑节点的路径长度为 h，那么一黑一红交替出现的路径长度最多只能是 2*h。
红黑树是一种高效的自平衡二叉搜索树，因其出色的性能和良好的平衡特性，在计算机科学中被广泛应用。以下是红黑树的一些主要应用场景：
TreeSet 和 TreeMap，分别提供有序集合和有序映射的功能。std::set、std::multiset、std::map 和 std::multimap 的底层数据结构。创建两个文件，一个头文件 RBTree.hpp，一个源文件 test.cpp。
【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件 RBTree.hpp 中】
红黑树类的成员变量只有一个，就是指向红黑树的根节点的指针。
红黑树的节点类：
为什么红黑树新插入的节点一定是红色的？其实就是维护成本的问题：
构造函数没什么好说的，默认构造就行了。
RBTree():_root(nullptr){ }
拷贝构造：因为节点都是从堆区 new 出来的，所以要深拷贝。 使用递归实现深拷贝：因为拷贝构造不能有多余的参数，但是递归函数又必须使用参数记录信息。
然后在拷贝构造里面调用一下这个函数就行了。
RBTree(const RBTree& obj){ _root =Copy(obj._root,nullptr);}
交换两颗红黑树的本质就是交换两颗数的资源（数据），而它们的资源都是从堆区申请来的，然后用指针指向这些资源。 并不是把资源存储在了红黑树对象中，所以资源交换很简单，直接交换_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;}
具体流程：从根节点开始，将目标值（传入的 key）与当前节点的 key 进行比较。如果目标值小于当前节点值，则在左子树中继续查找；如果目标值大于当前节点值，则在右子树中继续查找。这个过程一直进行，直到找到与目标值或者到达空节点为止。
把上述过程转成代码：
红黑树就是在二叉搜索树的基础上节点有了颜色，因此红黑树也可以看成是二叉搜索树。
那么 AVL 树的插入过程可以分为两步：
插入的具体过程如下：
这个过程一直进行，直到找到与传入的 key 相等的节点或者到达空节点为止。
把上述过程转成代码：
颜色调整分以下 3 种情况：
此时插入节点，并没有违反任何红黑树规则，所以不需要调整颜色/树的结构，直接结束插入就行。
（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 及其子树组成的这棵树的根节点。然后的推导就与单旋的类似了。
具体代码实现：
bool empty() const { return _root == nullptr; }
使用递归实现二叉搜索树的节点个数统计：因为我们经常使用的 stl 的容器的 size 都是没有参数的，但是递归函数又必须使用参数记录信息，所以再封装一个成员函数，专门用来递归。
然后再 size 里面调用一下就行了。
size_t size() const { return _size(_root); }
（此处省略完整代码，参考上文各部分实现整合）
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online