数据结构07：查找[C++][红黑二叉排序树RBT]

本文主要是介绍数据结构07：查找[C++][红黑二叉排序树RBT]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

图源：文心一言 | 提词：动漫风格红黑树少女#创意图#

考研笔记整理1.7w+字，但是删除操作的代码是有一点问题的{无法正确处理红色结点的删除}，其它功能可正常使用，请小伙伴注意~~🥝🥝

第1版：查资料、画导图、画配图~🧩🧩

参考用书：王道考研《2024年数据结构考研复习指导》

参考用书配套视频：7.3_4_红黑树的定义和性质_哔哩哔哩_bilibili

特别感谢： Chat GPT老师、文心一言老师~

📇目录

🦮思维导图

🧵基本概念

⏲️定义

⏲️性质

⌨️代码实现

🧵分段代码

🔯P0：调用库文件

🔯P1：定义树结点

🔯P2：结点旋转操作

🔯P3：插入修复函数

🔯P4：插入结点

🔯P0-P4附录：构造二叉树

🔯P5：寻找最小结点

🔯P6：结点替换

🔯P7：删除修复函数

🔯P8：结点删除 [代码与注释可能有误]

🔯P9：树的遍历

🔯P10：main函数

🧵完整代码

🔯P0：完整代码

🔯P1：执行结果

🔚结语

🦮思维导图

备注：

思维导图为整理王道教材第7章查找的所有内容；
本篇仅涉及到红黑树（RBT）的内容~ //前两篇博文收到了小伙伴的点赞、收藏、评论真的很开心，老泪纵横++，我又觉得我能肝博文了~~

🧵基本概念

⏲️定义

红黑二叉排序树，若树非空，满足下列特性：

是一棵朴素二叉排序树，简单概括就是“ 左子树 < 根结点 < 右子树 ”的二叉树。
在插入和删除结点时，要满足红黑树的性质：
结点颜色：黑色、红色；
根结点颜色：黑色；
叶节点颜色：此处为虚构的外部NULL结点，黑色；
分支结点颜色：
不存在两个相邻的红色结点，即红色结点的孩子与父亲都是黑色；
对于每个结点，到任意一个叶结点的简单路径上，黑色结点的数量相同。

机智的咸鱼老师freestyle：左根右、根叶黑、不红红、黑路同。{1表示朴素二叉树的排序性质、2表示根结点与叶子结点的颜色、3表示红色结点不相邻、4表示任意结点到叶结点简单路径上的黑色结点均相同}。

举个栗子，例如以下就是两棵简单的红黑树：

黑色高度：从某结点（不含该结点本身）到叶子结点简单路径中的黑结点总数。根据性质“黑路同”，每个结点，从该结点到任意叶子结点的黑高应该是完全相同的~

红黑树的适用范围

从图中我们可以看到，红黑树1是接近于平衡二叉树的时候，红黑树2相对于平衡二叉树略微有些失衡，但也可以基本保持树的宽度，也就是可以保证树的查询效率~

为什么会存在红黑树这种花里胡哨的树，大概是因为红黑树的二叉树兄弟们都过于偏科：

🌸朴素二叉排序树（BST）：数据结构07：查找[C++][朴素二叉排序树BST]，这棵二叉排序树兄弟，虽然插删结点的速度非常快，但是万一结点输入的顺序不理想，查询的速度就会非常之慢，最慢的时候可以和链表查询的速度一致~可能适合总是在插删但很少查询的情况~
🌸平衡二叉排序树（AVL）：数据结构07：查找[C++][平衡二叉排序树AVL]，这棵二叉排序树兄弟，虽然查询结点的效率非常高，但是每次插删结点几乎都会进行一个左旋右旋调整树的大动作，调整的频率非常之高且速度非常之慢~可能适合总是在查询但很少插删的情况~

所以遇到插删和查询的动作频率比较均衡的情况，朴素二叉树、平衡二叉树就显得有点力不从心，这种时候，就可以考虑红黑树这种，既可以保持宽树形，树形调整又没有那么频繁的树~~

红黑树的时间复杂度与平衡二叉树接近，为 O（log n）~

⏲️性质

性质1：从根到叶结点的最长路径不大于最短路径的2倍。

最短路径：全黑结点；最长路径：红黑相间。由于红色结点不能相邻的特性，黑色与红色结点仅能以接近1：1的比例交错出现，因此从根到叶结点的最长路径不大于最短路径的2倍。

性质2：有n个内部结点的红黑树的高度 h ≤ 2log (n+1)。

根据以上结论，根的黑高至少为 h/2，即 n ≥ 2^(h/2) - 1。

下面我们以上图中的红黑树1为例，说明如何创建及遍历一棵简单的红黑二叉排序树~

图源：文心一言 | 提词：动漫风格红黑树少女#创意图#

⌨️代码实现

🧵分段代码

🔯P0：调用库文件

输入输出流文件iostream{本代码用于输入与输出}；
动态数组的向量文件vector{本代码用于创建树结点的动态数组}；

#include <iostream>
#include <vector>

🔯P1：定义树结点

红黑树是一个家庭观念非常强的大家族，它的孩子结点属性会受到父结点、叔叔结点甚至是爷爷结点的影响~因此相比其它的二叉树伙伴，不仅多一个颜色属性，而且多一个父结点指针，以便于根据祖先的颜色改弦易调~

enum Color {    // 定义枚举类型：颜色RED,     // 红色结点BLACK    // 黑色结点
};struct RBNode {    // 红黑树结点结构int data;       // 数据域Color color;    // 结点颜色RBNode* parent;    //父结点指针RBNode* left;      //左孩子指针RBNode* right;     //右孩子指针RBNode(int val, Color c, RBNode* p, RBNode* l, RBNode* r)    //变量赋值: data(val), color(c), parent(p), left(l), right(r) {}
};

🔯P2：结点旋转操作

为了将红黑树的树形尽量调宽，红黑树平衡调整的基本操作是染色和旋转，旋转的操作如下——

左子树不平衡：当前结点移动到右子树的位置，在图中类似于右旋的操作~
右子树不平衡：当前结点移动到左子树的位置，在图中类似于左旋的操作~

如果我没有理解错的话，简单版本的左旋大概是这样的下图这样的{此处暂时不考虑染色}~

注意：括号内是平衡因子，计算公式=左子树高-右子树高~

相比平衡树AVL，实际上这个代码考虑了结点旋转时父指针的赋值，所以显得长很多，实际有效操作与平衡树AVL的旋转是类似的~

    void LeftRotate(RBNode* node) {          //左旋操作RBNode* rightChild = node->right;    //保存 node右孩子结点 为rightChildnode->right = rightChild->left;      //将node右孩子指针 指向 rightChild左孩子指针if (rightChild->left != nullptr) {      //如果rightChild的左指针不为空rightChild->left->parent = node;    //将rightChild的左指针的父指针指向node，作用为更新rightChild的右孩子的父指针}rightChild->parent = node->parent;    //将rightChild的父指针指向node的父指针if (node->parent == nullptr) {            //若node父指针为空，即node为根结点root = rightChild;                        //将根结点root赋值到rightChild} else if (node == node->parent->left) {  //若node属于父节点的左子树node->parent->left = rightChild;          //将rightChild结点挂在node父节点的左侧} else {                                  //若node属于父节点的左子树node->parent->right = rightChild;         //将rightChild结点挂在node父节点的右侧}rightChild->left = node;         //rightChild左指针指向nodenode->parent = rightChild;       //node父指针指向rightChild}

右旋是左旋的镜像操作，此处不再赘述~

    void RightRotate(RBNode* node) {          //右旋操作RBNode* leftChild = node->left;node->left = leftChild->right;if (leftChild->right != nullptr) {leftChild->right->parent = node;}leftChild->parent = node->parent;if (node->parent == nullptr) {root = leftChild;} else if (node == node->parent->left) {node->parent->left = leftChild;} else {node->parent->right = leftChild;}leftChild->right = node;node->parent = leftChild;}

🔯P3：插入修复函数

封装旋转的操作以后，此处我们正式介绍一下，当树形不满足红黑树性质时应该怎么调整~

为了维持红黑树的稳定性，我们通常将插入的结点首先涂红，并按照“左根右”{左子树<根结点<右子树}的数值插入到树中，然后在路径上不满足红黑树的“不红红” {红色结点不能相邻} 与“黑路同”{结点所在路径中黑色结点数量相同}性质时调整平衡~

综上，简单的红黑树插入结点z可以汇总为以下情况——

以逸待劳型：插入的结点z是红色，结点z的父节点是黑色：
不会破坏红黑树性质，不调整~
独孤求败型：插入的结点z是根结点：
根据红黑树的性质，根结点必须为黑色，将结点z染成黑色~
染色旋转型：插入的结点z是红色，结点z的父结点是红色，结点z的叔叔结点不存在或者不是红色 {此处操作和平衡树是相似的} ：
左左型：插入到结点左子树的左子树，导致不平衡，需要右旋，且更改结点z的父结点颜色{结点z的父结点由红色转黑色}，结点z的爷爷结点颜色{结点z的爷爷结点由黑色转红色}~
右右型：插入到结点右子树的右子树，导致不平衡，左左型的镜像操作；
左右型：插入到结点左子树的右子树，导致不平衡，需要先左旋后右旋；左旋之后的树变为左左型，后序操作右旋的完全相同。
右左型：插入到结点右子树的左子树，导致不平衡，左右型的镜像操作；
染色循环型：插入的结点z是红色，结点z的父结点是红色，结点z的叔叔结点存在且为红色：
结点z的爷爷结点由黑色染成红色，结点z的父结点与结点z的叔叔结点由红色染成黑色~现在，结点z的爷爷结点、结点z的父结点、结点z的叔叔结点、结点z这祖孙三代就能满足红黑树性质啦~
但是到这里还没有结束哦，因为结点z的爷爷结点由黑色染成红色了，有可能会影响上层的结点颜色，因此会把结点z的爷爷结点作为新的插入结点，开始向上循环处理~ {解释：原来人家结点z的太爷爷结点有可能也是红色、结点z的爷爷结点是黑色才能保持原来的红黑树满足要求；而经过调整，现在结点z的爷爷结点也是红色，如果相邻两代都是红色，就不能满足红黑树条件了}

染色旋转型：插入结点的叔叔结点不存在，左左型、左右型举栗——

染色循环型：插入结点的叔叔结点存在且为红色，左左型、左右型举栗{太爷爷结点有可能是黑色，也有可能是红色，此处按照红色假设}——

于是我们就有了这串代码~

    void InsertFixup(RBNode* node) {while (node != root && node->parent->color == RED) {    //满足{当前结点不是根结点，且父节点为红色}时，开始以下循环if (node->parent == node->parent->parent->left) {   //满足{当前父结点在爷爷结点的左侧}时，执行语句RBNode* uncle = node->parent->parent->right;    //定义叔叔结点为父结点的右兄弟if (uncle != nullptr && uncle->color == RED) {  //满足{叔叔结点不为空，且叔叔结点是红色时}{染色循环型}node->parent->color = BLACK;          //父亲结点涂黑uncle->color = BLACK;                 //叔叔结点涂黑node->parent->parent->color = RED;    //爷爷结点涂红node = node->parent->parent;          //将爷爷赋值为当前结点} else {                                  //满足{叔叔结点不是红色时}if (node == node->parent->right) {    //如果当前结点在父结点的右子树{左右型}node = node->parent;              //将当前结点指针移动到父结点位置LeftRotate(node);                 //当前结点左旋{调整到左左型}}node->parent->color = BLACK;          //父亲结点涂黑node->parent->parent->color = RED;    //爷爷结点涂红RightRotate(node->parent->parent);    //爷爷结点右旋}} else {                                             //满足{当前父结点在爷爷结点的右侧}时，执行语句RBNode* uncle = node->parent->parent->left;      //定义叔叔结点为父结点的左兄弟if (uncle != nullptr && uncle->color == RED) {   //满足{叔叔结点不为空，且叔叔结点是红色时}{染色循环型}node->parent->color = BLACK;          //父亲结点涂黑uncle->color = BLACK;                 //叔叔结点涂黑node->parent->parent->color = RED;    //爷爷结点涂红node = node->parent->parent;          //将爷爷赋值为当前结点} else {                                  //满足{叔叔结点不是红色时}if (node == node->parent->left) {     //如果当前结点在父结点的左子树{右左型}node = node->parent;              //将当前结点指针移动到父结点位置RightRotate(node);                //当前结点右旋{调整到右右型}}node->parent->color = BLACK;          //父亲结点涂黑node->parent->parent->color = RED;    //爷爷结点涂红LeftRotate(node->parent->parent);     //爷爷结点右旋}}}root->color = BLACK;    //根结点涂黑}

🔯P4：插入结点

采用循环的方式创建树~

查询插入结点的位置；
插入结点，通常为叶节点；
插入完成后，调用调整树形的函数。

    void Insert(int key) {    //传入数据keyRBNode* newNode = new RBNode(key, RED, nullptr, nullptr, nullptr);    //创建新的红色待插入结点{数据为key}RBNode* parent = nullptr;    //创建parent指针RBNode* current = root;      //创建current指针while (current != nullptr) {    //{当前结点不为空}时执行循环parent = current;           //将当前结点的父节点指针指向当前结点本身if (key < current->data) {    //key < 当前数据current = current->left;  //插入当前结点的左侧} else {                      //key > 当前数据current = current->right; //插入当前结点的右侧}}    //执行完循环后，可找到准备插入的位置newNode->parent = parent;    //将newnode的父指针指向parentif (parent == nullptr) {     //parent为空root = newNode;          //插入到根结点} else if (key < parent->data) {    //key < 当前数据parent->left = newNode;         //parent左指针指向newnode} else {                            //key > 当前数据parent->right = newNode;        //parent右指针指向newnode}InsertFixup(newNode);        //插入完成后，调用调整树形的函数}

🔯P0-P4附录：构造二叉树

代码在main中写入，实际操作就是把一个数组的内的元素分别执行插入结点的操作~

    RedBlackTree tree;// 插入节点std::vector<int> values = {15, 3, 7, 10, 9, 8};for (int value : values) {tree.Insert(value);}

具体的创建过程嗯...如果我没有理解错，大概是下图这样的~

检查一下，应该是满足了红黑树的4个特性：左根右、根叶黑、不红红、黑路同~

这棵树的输入与平衡树的案例输入是一致的，有兴趣的同学可以对比一下创建树的结果——

🌸平衡二叉排序树（AVL）：数据结构07：查找[C++][平衡二叉排序树AVL]

🔯P5：寻找最小结点

利用二叉排序树 “左子树<根结点<右子树” 的性质，采用递归方式一直向左寻找，就可以找到最小值结点~

    RBNode* Minimum(RBNode* node) {while (node->left != nullptr) {    //满足{结点左侧不为空}时node = node->left;             //向左查询}return node;    //返回最小结点}

🔯P6：结点替换

在红黑树中，结点替换是指将一个节点及其子树替换为另一个结点及其子树，保持树的平衡性和性质不变，这个是删除的基本操作~

    void Transplant(RBNode* u, RBNode* v) {    //结点u:移植的源结点；结点v:移植的目标结点if (u->parent == nullptr) {    //满足{结点u的父结点为空}时root = v;                  //根结点指针root指向结点v} else if (u == u->parent->left) {     //满足{结点u在父结点的左子树}时u->parent->left = v;               //将父结点的左指针指向结点v} else {                       //满足{结点u在父结点的右子树}时u->parent->right = v;      //将父结点的右指针指向结点v}if (v != nullptr) {            //满足{结点v不为空}时v->parent = u->parent;     //将结点v的父指针指向结点u的父指针}}

🔯P7：删除修复函数

与插入结点容易破坏“不红红”{红色结点相邻性质}相对，删除结点容易破坏“黑路同”{到叶结点简单路径上黑色结点数目一致}的性质~

尤其是在删除黑色结点之后，红黑树可能无法保证黑平衡特性，树的调整也可能分为以下类型 {删除操作我其实没有很理解，因此以下的总结可能有些问题} ：

李代桃僵型：删除的结点x是黑色，且结点x的兄弟结点是红色：
状况1：交换结点x的父结点与结点x的兄弟结点的颜色，并进行左旋操作，此时结点x的兄弟结点成为局部根结点，红黑树的性质不变，并且可以按照下面的情况处理~
环环相扣型：删除的结点x是黑色，且结点x的兄弟结点是黑色：
状况2：结点x的兄弟结点的左孩子结点与结点x的兄弟结点的右孩子结点是黑色{这...这是左侄子结点和右侄子结点？}，将结点x的兄弟结点染成红色；
状况3：结点x的兄弟结点的右孩子结点是黑色，则将结点x的兄弟结点的左孩子结点染成黑色，将结点x的兄弟结点染成红色，然后右旋；
状况4：将结点x的兄弟结点设置为父节点的颜色，将父节点的颜色染成黑色，结点x的兄弟结点的右孩子结点染成黑色，然后父结点进行左旋操作，移到根结点。

备注：此处觉得莫名其妙没有关系，可以看完删除函数的操作后再返回来看这个删除修复函数~

    void DeleteFixup(RBNode* node) {while (node != root && node->color == BLACK) {    //满足{结点不为根结点 且 结点颜色为黑色}时，执行循环if (node == node->parent->left) {             //若满足{结点在父结点的左子树}RBNode* sibling = node->parent->right;    //设置结点的右兄弟结点if (sibling->color == RED) {        //若满足{右兄弟是红色}sibling->color = BLACK;         //兄弟结点涂黑node->parent->color = RED;      //父亲结点涂红LeftRotate(node->parent);       //父亲结点左旋sibling = node->parent->right;  //重新定义兄弟结点}if (sibling->left->color == BLACK && sibling->right->color == BLACK) {    //若满足{兄弟结点的左右孩子都是黑色}sibling->color = RED;    //兄弟结点涂红node = node->parent;     //重新定义当前结点} else {if (sibling->right->color == BLACK) {    //若满足{兄弟结点的右孩子是黑色，但兄弟结点的左孩子不是黑色}sibling->left->color = BLACK;    //兄弟的左孩子结点涂黑sibling->color = RED;            //兄弟结点涂红RightRotate(sibling);            //兄弟结点右旋sibling = node->parent->right;}sibling->color = node->parent->color;    //兄弟结点染为父结点颜色node->parent->color = BLACK;             //父结点染黑sibling->right->color = BLACK;           //兄弟结点右孩子染黑LeftRotate(node->parent);                //父结点进行左旋操作node = root;                             //将局部根结点设为当前结点}} else {             //若满足{结点在父结点的右子树}，以下执行左子树的镜像操作RBNode* sibling = node->parent->left;if (sibling->color == RED) {sibling->color = BLACK;node->parent->color = RED;RightRotate(node->parent);sibling = node->parent->left;}if (sibling->right->color == BLACK && sibling->left->color == BLACK) {sibling->color = RED;node = node->parent;} else {if (sibling->left->color == BLACK) {sibling->right->color = BLACK;sibling->color = RED;LeftRotate(sibling);sibling = node->parent->left;}sibling->color = node->parent->color;node->parent->color = BLACK;sibling->left->color = BLACK;RightRotate(node->parent);node = root;}}}node->color = BLACK;    //结点的当前颜色涂黑}

🔯P8：结点删除 [代码与注释可能有误]

删除的情况，可分为以下4种情况考虑——

删除结点的基本操作：同朴素平衡二叉树BST的删除🌸[朴素二叉排序树BST]；然后，在删除结点以后，树的结构可能违反了红黑树的性质，因此我们需要按照结点颜色进行调整~
删除的结点是叶子结点：
结点x是红色：不会破坏红黑树性质，因此可以直接删除，不需要调整~
结点x是黑色：会破坏红黑树的性质，调用删除修复函数（DeleteFixup）调整树形和颜色~
删除的结点是具有单孩子的分支结点：
结点x是红色：这种情况不会出现，因为不满足红黑树”黑路同“的性质；
结点x是黑色：根据红黑树的性质，该结点x的孩子结点必为红色且只有1个，调用结点替换函数（Transplant）将结点x的孩子结点的值替换掉结点z的值，并删除子结点，，后序操作转化为删除红色叶子结点的操作~
删除的结点是具有双孩子的分支结点：
结点x是红色：寻找前驱或后继结点，并通过调用结点替换函数（Transplant）交换结点x与前驱、后继结点的值，后序操作转化为删除叶子结点的操作~
结点x是黑色：寻找前驱或后继结点，并通过调用结点替换函数（Transplant）交换结点x与前驱、后继结点的值，后序操作转化为删除叶子结点的操作~

删除的结点是叶子结点：

删除的结点是单孩子结点：

删除的结点是红色双孩子结点：

删除的结点是黑色双孩子结点：

注意：

如果删除的结点原始颜色也是黑色，就需要调用删除修复函数（DeleteFixup）调整树形和颜色~
我看到大佬的博文和参考书有说明双重黑节点的概念，应该是在删除黑色结点且其孩子结点也均是黑色时使用，维持稳定性，减少树形的调整~

    void Delete(int key) {RBNode* node = root;    //将根结点指针指向node变量while (node != nullptr) {            //{node不为空}时，查找结点if (key == node->data) {         //关键字 = 结点值break;                       //完成查找，跳出循环} else if (key < node->data) {   //关键字 < 结点值node = node->left;           //向左子树查询} else {                         //关键字 > 结点值node = node->right;          //向右子树查询}}if (node == nullptr) {               //{node找到空结点}，查找失败std::cout << "未找到目标结点\n"; //返回，未找到目标结点return;}Color originalColor = node->color;   //保存目标结点的颜色RBNode* successor = nullptr;         //创建successor，用途为保存目标结点的后继结点if (node->left == nullptr) {         //若{结点的左子树为空}successor = node->right;         //后继结点successor结点为当前的右孩子Transplant(node, successor);     //交换successor与node，完成删除} else if (node->right == nullptr) { //若{结点的右子树为空}successor = node->left;          //后继结点successor结点为当前的左孩子Transplant(node, successor);     //交换successor与node，完成删除} else {                                        //若{结点具有双孩子}RBNode* minimum = Minimum(node->right);     //创建minimum，其值为右子树的最小值originalColor = minimum->color;  //保存该结点的原始颜色successor = minimum->right;      //minimum的右子树作为后继结点if (minimum->parent == node) {        //若{右子树最小结点minimum的父结点为当前结点node}if (successor != nullptr) {       //且，若{successor结点不为空}successor->parent = minimum;  //将successor结点的父指针指向minimum结点}} else {                              //若{右子树最小结点minimum的父结点不是当前结点node}Transplant(minimum, successor);   //交换minimum与successorminimum->right = node->right;     //将node的右指针指向minimum的右指针minimum->right->parent = minimum; //将minimum的右孩子的父指针指向最小结点}Transplant(node, minimum);        //交换node与minimumminimum->left = node->left;       //minimum的左指针指向node的左指针minimum->left->parent = minimum;  //minimum的左孩子的父指针指向minimumminimum->color = node->color;     //将node的颜色赋值到minimum}if (originalColor == BLACK) {         //如果原来的结点是黑色DeleteFixup(successor);           //对于后继结点执行删除修复操作}delete node;                          //删除结点}

🔯P9：树的遍历

传入树的根结点内存地址，由于二叉树遵循：“左＜根＜右” 的原则，因此可以通过二叉树的中序遍历完成，此处采用递归方式完成~

    void InOrderTraversal(RBNode* node) {if (node != nullptr) {                //若{未遍历到空结点}，执行循环InOrderTraversal(node->left);     //递归遍历左子树std::cout << node->data << " ";   //输出当前结点的值InOrderTraversal(node->right);    //递归遍历右子树}}

敲黑板中序遍历这个已经写过很多次此处不再赘述了~ 🌸数据结构05：树与二叉树[C++]

🔯P10：main函数

main函数除了P0~P9的函数调用，就创建了1个插入结点的队列，以及示意性地增加删除结点的操作~

int main() {RedBlackTree tree;// 插入结点std::vector<int> values = {15, 3, 7, 10, 9, 8};for (int value : values) {tree.Insert(value);}// 输出结点std::cout << "输出结点: ";tree.InOrderTraversal();// 删除结点int target = 7;tree.Delete(target);// 输出结点std::cout << "输出结点: ";tree.InOrderTraversal();return 0;
}

🧵完整代码

🔯P0：完整代码

按照惯例，为了凑本文的字数，我这里贴一下整体的代码，删掉了细部注释~🫥🫥

//头文件
#include <iostream>
#include <vector>//定义结点颜色
enum Color {RED,BLACK
};//定义结点结构
struct RBNode {int data;Color color;RBNode* parent;RBNode* left;RBNode* right;RBNode(int val, Color c, RBNode* p, RBNode* l, RBNode* r): data(val), color(c), parent(p), left(l), right(r) {}
};//类：红黑树
class RedBlackTree {
private:RBNode* root;//结点左旋void LeftRotate(RBNode* node) {RBNode* rightChild = node->right;node->right = rightChild->left;if (rightChild->left != nullptr) {rightChild->left->parent = node;}rightChild->parent = node->parent;if (node->parent == nullptr) {root = rightChild;} else if (node == node->parent->left) {node->parent->left = rightChild;} else {node->parent->right = rightChild;}rightChild->left = node;node->parent = rightChild;}//结点右旋void RightRotate(RBNode* node) {RBNode* leftChild = node->left;node->left = leftChild->right;if (leftChild->right != nullptr) {leftChild->right->parent = node;}leftChild->parent = node->parent;if (node->parent == nullptr) {root = leftChild;} else if (node == node->parent->left) {node->parent->left = leftChild;} else {node->parent->right = leftChild;}leftChild->right = node;node->parent = leftChild;}//插入修复操作void InsertFixup(RBNode* node) {while (node != root && node->parent->color == RED) {if (node->parent == node->parent->parent->left) {RBNode* uncle = node->parent->parent->right;if (uncle != nullptr && uncle->color == RED) {node->parent->color = BLACK;uncle->color = BLACK;node->parent->parent->color = RED;node = node->parent->parent;} else {if (node == node->parent->right) {node = node->parent;LeftRotate(node);}node->parent->color = BLACK;node->parent->parent->color = RED;RightRotate(node->parent->parent);}} else {RBNode* uncle = node->parent->parent->left;if (uncle != nullptr && uncle->color == RED) {node->parent->color = BLACK;uncle->color = BLACK;node->parent->parent->color = RED;node = node->parent->parent;} else {if (node == node->parent->left) {node = node->parent;RightRotate(node);}node->parent->color = BLACK;node->parent->parent->color = RED;LeftRotate(node->parent->parent);}}}root->color = BLACK;}//寻找最小结点RBNode* Minimum(RBNode* node) {while (node->left != nullptr) {node = node->left;}return node;}//替换结点void Transplant(RBNode* u, RBNode* v) {if (u->parent == nullptr) {root = v;} else if (u == u->parent->left) {u->parent->left = v;} else {u->parent->right = v;}if (v != nullptr) {v->parent = u->parent;}}//删除修正操作void DeleteFixup(RBNode* node) {while (node != root && node->color == BLACK) {if (node == node->parent->left) {RBNode* sibling = node->parent->right;if (sibling->color == RED) {sibling->color = BLACK;node->parent->color = RED;LeftRotate(node->parent);sibling = node->parent->right;}if (sibling->left->color == BLACK && sibling->right->color == BLACK) {sibling->color = RED;node = node->parent;} else {if (sibling->right->color == BLACK) {sibling->left->color = BLACK;sibling->color = RED;RightRotate(sibling);sibling = node->parent->right;}sibling->color = node->parent->color;node->parent->color = BLACK;sibling->right->color = BLACK;LeftRotate(node->parent);node = root;}} else {RBNode* sibling = node->parent->left;if (sibling->color == RED) {sibling->color = BLACK;node->parent->color = RED;RightRotate(node->parent);sibling = node->parent->left;}if (sibling->right->color == BLACK && sibling->left->color == BLACK) {sibling->color = RED;node = node->parent;} else {if (sibling->left->color == BLACK) {sibling->right->color = BLACK;sibling->color = RED;LeftRotate(sibling);sibling = node->parent->left;}sibling->color = node->parent->color;node->parent->color = BLACK;sibling->left->color = BLACK;RightRotate(node->parent);node = root;}}}node->color = BLACK;}//执行中序遍历void InOrderTraversal(RBNode* node) {if (node != nullptr) {InOrderTraversal(node->left);std::cout << node->data << " ";InOrderTraversal(node->right);}}//公共类
public:RedBlackTree() : root(nullptr) {}//插入结点void Insert(int key) {RBNode* newNode = new RBNode(key, RED, nullptr, nullptr, nullptr);RBNode* parent = nullptr;RBNode* current = root;while (current != nullptr) {parent = current;if (key < current->data) {current = current->left;} else {current = current->right;}}newNode->parent = parent;if (parent == nullptr) {root = newNode;} else if (key < parent->data) {parent->left = newNode;} else {parent->right = newNode;}InsertFixup(newNode);}//删除结点void Delete(int key) {RBNode* node = root;while (node != nullptr) {if (key == node->data) {break;} else if (key < node->data) {node = node->left;} else {node = node->right;}}if (node == nullptr) {std::cout << "未找到目标结点\n";return;}Color originalColor = node->color;RBNode* successor = nullptr;if (node->left == nullptr) {successor = node->right;Transplant(node, successor);} else if (node->right == nullptr) {successor = node->left;Transplant(node, successor);} else {RBNode* minimum = Minimum(node->right);originalColor = minimum->color;successor = minimum->right;if (minimum->parent == node) {if (successor != nullptr) {successor->parent = minimum;}} else {Transplant(minimum, successor);minimum->right = node->right;minimum->right->parent = minimum;}Transplant(node, minimum);minimum->left = node->left;minimum->left->parent = minimum;minimum->color = node->color;}if (originalColor == BLACK) {DeleteFixup(successor);}delete node;}//传递中序遍历根结点void InOrderTraversal() {InOrderTraversal(root);std::cout << "\n";}
};int main() {RedBlackTree tree;std::vector<int> values = {15, 3, 7, 10, 9, 8};for (int value : values) {tree.Insert(value);}std::cout << "输出结点: ";tree.InOrderTraversal();int target = 7;tree.Delete(target);std::cout << "输出结点: ";tree.InOrderTraversal();return 0;
}

🔯P1：执行结果

运行结果如下图所示~

🔚结语

博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，督促博主优化内容，不限于以下内容~😶‍🌫️😶‍🌫️

有错误：这段注释南辕北辙，理解错误，需要更改~对了，这里介绍两个大佬的博文讲得还挺详细的，可以配合查看~
- 图解：红黑树删除篇（一文读懂） - 知乎 (zhihu.com)
- 理解红黑树并实现(python3)_liu_coding的博客-CSDN博客
难理解：这段代码雾里看花，需要更换排版、增加语法、逻辑注释或配图~
不简洁：这段代码瘠义肥辞，好像一座尸米山，需要更改逻辑；如果是C++语言，调用某库某语法还可以简化~
缺功能：这段代码败絮其中，能跑，然而不能用，想在实际运行或者通过考试需要增加功能~
跑不动：这个自己说明一下~简单红黑树的创建、遍历、删除黑色结点应该可以正常完成，删除红色结点代码经过测试确实跑不动，可能的原因：
- 没有很好地解决空指针赋值的问题{空指针应该默认为黑色，这里尝试修复失败了}~
- 删除红色结点的逻辑可能也有问题{如果仅采用后继结点替补当前的红色结点，可能会导致删除操作后树不满足性质；可能需要增加删除前驱、后继结点的判断}~
- 另外，此代码未涉及双重黑色结点的介绍，如果使用应该可以继续降低树形的调整幅度~