C++ 红黑树模拟实现

创建两个文件，一个头文件 RBTree.hpp，一个源文件 test.cpp。

【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件 RBTree.hpp 中】

1. RBTree.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义。
2. test.cpp：存放 main 函数，以及测试代码。

包含头文件

• iostream：用于输入输出
• cmath：提供数学函数

类的成员变量和红黑树节点的定义

红黑树类的成员变量只有一个，就是指向红黑树的根节点的指针。

红黑树的节点类：

为什么红黑树新插入的节点一定是红色的？其实就是维护成本的问题：

1. 如果新插入的节点为黑色：因为插入之前，这棵树一定是红黑树，所以他的每一条路径上的黑色节点个数都相同。但是因为你新插入了一个黑色的，这一条路径就会比其他路径多一个黑色节点，为了保持红黑树的规则（每一条路径上的黑色节点个数都相同），就得想办法让每一条路径也都增加一个黑色节点，维护成本太高了。
2. 如果新插入的节点为红色：
   • ① 新插入的节点的父亲为黑色，就可以直接结束了，因为满足红黑树的所有规则。
   • ② 就算新插入的节点的父亲为红色，调整的情况也只有两种，维护成本更低。

构造函数和拷贝构造

构造函数没什么好说的，默认构造就行了。

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 树的插入过程可以分为两步：

1. 先按照二叉搜索树的方式插入新节点
2. 再调整颜色，维护红黑树的规则

第一步：按照二叉搜索树的方式插入新节点

插入的具体过程如下：

1. 树为空，则直接新增节点，赋值给二叉搜索树的成员变量_root 指针
2. 树不空，则按照查找（find）的逻辑找到新节点应该插入的位置
3. 树不空，如果树中已经有了一个节点的 key 值与要插入的节点的 key 相同，就插入失败

这个过程一直进行，直到找到与传入的 key 相等的节点或者到达空节点为止。

把上述过程转成代码：

第二步：调整颜色，维护红黑树的规则

颜色调整分以下 3 种情况：

1. 新插入的节点（cur）的父亲节点（parent）颜色为黑
2. 新插入的节点（cur）的父亲节点（parent）颜色为红，且叔叔（uncle）节点不为空且为红
3. 新插入的节点（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); }

完整代码示例

（此处省略完整代码，参考上文各部分实现整合）