【数据结构与算法】红黑树的插入与删除详解
【数据结构与算法】红黑树的插入与删除详解
Ⅰ. 前言
我们这里只实现红黑树的插入和删除，了解他们的底层即可，而后面我们在介绍 map 以及 set 的模拟实现的时候，我们就会进一步将红黑树进行改造！
Ⅱ. 红黑树的概念
红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是 接近平衡 的。（接近平衡不代表是平衡的，而 AVL 树则是严格平衡的）
Ⅲ. 红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 每个叶子结点都是黑色的 ( 此处的叶子结点指的是空结点 )
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
❓ 思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
💡 解答： 因为由性质三可以知道，红黑树没有连续的红色节点，且性质四中每条路径上包含相同数量的黑色节点。那么假设现在每条路径上有 n 个黑色节点，那么我们会发现：
1、如果不存在红色节点的话，那么这棵树的高度就是
。
2、如果存在红色节点的话，且一黑一红布局的情况下，由于没有红色的连续节点，所以这棵树的高度就是
。 所以可以看出红黑树的高度范围是 【
，
】，所以其最长路径中节点个数不会超过最短路径节点个数的两倍！
Ⅳ. 红黑树的节点定义
enum Color
{
BLACK,
RED
};
template <class K, class V>
struct RBTreeNode
{
RBTreeNode(const pair<K, V>& kv, Color col = RED)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(col)
{}
RBTreeNode<K, V>* _left; // 节点的左孩子
RBTreeNode<K, V>* _right; // 节点的右孩子
RBTreeNode<K, V>* _parent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
pair<K, V> _kv; // 节点的键值对
Color _col; // 节点的颜色
}; 后面我们在实现 map 和 set 的时候，我们会对节点定义进行一些改变，这些具体后面会讲！
❓ 思考：在节点的定义中，为什么要将节点的默认颜色给成红色的？
💡 解答：
这里插入黑色节点其实也是可以的，但是我们旋转插入颜色，是要根据具体情况，如果这里旋转插入黑色，那我们可能会违反性质四，也就是每条路径上黑色节点的数量，那么如果要调整的话，可能需要调节整棵树的路径的黑色节点，这就比较麻烦了！ 而如果我们旋转插入红色节点，那么我们可能违反的是性质三，也就是不能有连续红色节点，那么我们每次调整的时候其实只需要调整一棵子树之间的颜色即可，虽然最坏情况可能是要一直调整到根节点，但是相比于插入黑色节点的影响，插入红色节点是比较乐观的选择！
Ⅴ. 红黑树的结构
为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为根节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft 域指向红黑树中最小的节点，pRight 域指向红黑树中最大的节点！
但是我们后面模拟实现红黑树的时候是不带头节点的，其实都是一样的！
Ⅵ. 红黑树的插入Insert
红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：
- 按照二叉搜索树的规则插入新节点（这个去参考二叉搜索树中的解析）
- 检测新节点插入后，红黑树的性质是否造到破坏：
因为 新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质 （作为结束条件），则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
规则：cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点（注意这里叔叔节点是关键！）
💅 注意： 下面都已左为
p，右为u的情况举例子，而左为u，右为p也是一样的只是方向改变了而已！
- 情况一： 该树为 空树，直接插入根结点的位置，违反性质
1，把节点颜色有红改为黑 即可。 - 情况二： 插入节点
cur的父节点p为黑色，不违反任何性质，无需做任何修改 - 情况三：
cur为红，p为红，g为黑，u存在且为红色- 此时将
p和u都变成黑色，将g变为红色，然后把g作为新的cur，继续向上调整，直到出现 情况二 或者p不存在 的时候的时候结束。
在这里插入图片描述 - 此时将
- 情况四：
cur为红，p为红，g为黑，u不存在 /u为黑色，且cur为p的左子树- 方法： 这种情况其实就是需要旋转来进行高度调节的情况了，很明显这是一个右单旋
-
p为g的左孩子，cur为p的左孩子，则对g进行右单旋转； - 相反，
p为g的右孩子，cur为p的右孩子，则对g进行左单旋转 -
p、g变色 -->p变黑，g变红
在这里插入图片描述 - 情况五：
cur为红，p为红，g为黑，u不存在/u为黑色，且cur为p的右子树- 其实情况四和情况五都是属于同一种，只不过他们需要旋转的方式不太一样！
-
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转 - 相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，则转换成了情况四
在这里插入图片描述
🔺 注意： 在判断完所有的情况之后，要将根节点的颜色设为黑色，因为有些操作里面最后将根节点设为红色了，所以要改回来！
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLOCK; // 记得将根节点的颜色变成黑色
return true;
}
// 寻找要插入的位置
Node* cur = _root;
Node* parent = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
// 插入新节点并将新节点的颜色设为红色
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
// 控制平衡
while (parent && parent->_col == RED) // 当parent不存在或者parent的颜色为黑则不需要调整了
{
Node* grandparent = parent->_parent;
// 判断一下parent的位置
if (grandparent->_left == parent)
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED) // uncle存在且为红色的情况
{
// 调整颜色
parent->_col = uncle->_col = BLOCK;
grandparent->_col = RED;
// 继续向上调整
cur = grandparent;
parent = cur->_parent;
}
else // uncle不存在或者为黑色的情况
{
// 根据cur与parent的位置判断要如何旋转
if (parent->_left == cur)
{
// 右单旋
RotateR(grandparent);
// 调整颜色
grandparent->_col = RED;
parent->_col = BLOCK;
}
else
{
// 先左单旋，然后右单旋
RotateL(parent);
RotateR(grandparent);
// 调整颜色
cur->_col = BLOCK;
grandparent->_col = RED;
}
break; // 旋转完即可break
}
}
else
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED) // uncle存在且为红色的情况
{
// 调整颜色
parent->_col = uncle->_col = BLOCK;
grandparent->_col = RED;
// 继续向上调整
cur = grandparent;
parent = cur->_parent;
}
else // uncle不存在或者为黑色的情况
{
// 根据cur与parent的位置判断要如何旋转
if (parent->_left == cur)
{
// 先右单旋，然后左单旋
RotateR(parent);
RotateL(grandparent);
// 调整颜色
cur->_col = BLOCK;
grandparent->_col = RED;
}
else
{
// 左单旋
RotateL(grandparent);
// 调整颜色
parent->_col = BLOCK;
grandparent->_col = RED;
}
break; // 旋转完即可break
}
}
}
// 最后记得将根节点的颜色调为黑色
_root->_col = BLOCK;
return true;
}
// 具体的左右单旋参考AVL树中的讲解
void RotateL(Node* parent);
void RotateR(Node* parent);Ⅶ. 红黑树的删除Erase
这里先粘几篇比较不错的博客：
红黑树的删除和二叉搜索树类似，只不过需要加上颜色，经过变色和旋转满足红黑树的性质。
只不过红黑树的删除涉及了多种组合情况，其实分类出来的话也就六大种组合，一定要先有思路再去看代码，这样子不至于把自己绕晕！
红黑树中删除一个节点，遇到的各种情形就是其子节点的状态和颜色的组合，子节点状态共有3种：无子节点、有一个子节点、有两个子节点，颜色有红色和黑色两种，所以共会有6种组合。接下来我们逐一分析：
- 无子节点，删除节点可能为红色或者黑色。
- 如果为红色，直接进行删除即可。
- 如果为黑色，直接删除之后需要进行红黑树的平衡操作。（最复杂，涉及旋转，这个我们放到最后说）
- 有一个子节点：
- 删除的节点一定为黑色，子节点一定是红色（联系红黑树性质推测一下），只需要将子节点替换删除节点的位置，变黑即可。
- 有两个子节点：
- 与二叉搜索树一样，找到其后继节点放到要删除的节点的位置，然后将后继节点作为删除节点处理。
组合1：被删节点无子节点，且被删结点为红色
这种情况是比较好处理的，因为我们删除红色节点并不违反红黑树的性质，所以 直接删除 即可。
组合2：被删结点无子结点，且被删结点为黑色
这种情况是最复杂的，我们会将其发生的各种情况都列出来，作为新的子函数专门处理，但是注意的是子函数只负责用来旋转以及修改颜色，不删除节点，所以出了子函数后记得要手动删除一下！
else if (cur->_left == nullptr && cur->_right == nullptr) // 无叶子节点
{
// 组合1：若被删节点为红色，则直接删除
if (cur->_col == RED)
{
// 直接删除节点即可
if (cur->_parent->_left == cur)
{
cur->_parent->_left = nullptr;
}
else
{
cur->_parent->_right = nullptr;
}
delete cur;
}
else // 组合2：被删节点为黑色，调用子函数专门去处理组合2（后面会讲）
{
Erase_balanceTwo(cur);
if (cur->_parent->_left == cur)
{
cur->_parent->_left = nullptr;
}
else
{
cur->_parent->_right = nullptr;
}
delete cur;
}
}组合3：被删结点有一个子结点，且被删结点为红色（不存在）
这种情况是不存在的，因为如果被删节点是红色的话，则违反性质四；如果被删节点是黑色的话，则违反性质五！
组合4：被删结点有一个子结点，且被删结点为黑色
这种组合下，被删结点的子结点必然为红色，此时直接将被删节点删掉，用子节点代替被删节点的位置，并将 子节点着黑 即可。
else if (cur->_left == nullptr && cur->_right != nullptr) //左为空，右不为空
{
Node* right = cur->_right;
Node* parent = cur->_parent;
right->_parent = parent;
if (parent->_left == cur)
{
parent->_left = right;
}
else
{
parent->_right = right;
}
delete cur;
// 最后将right的颜色改为黑色
right->_col = BLACK;
}
else if (cur->_left != nullptr && cur->_right == nullptr) //左不为空，右为空
{
Node* left = cur->_left;
Node* parent = cur->_parent;
left->_parent = parent;
if (parent->_left == cur)
{
parent->_left = left;
}
else
{
parent->_right = left;
}
delete cur;
// 最后将left的颜色改为黑色
left->_col = BLACK;
}组合5&6：被删结点有两个子结点，且被删结点为黑色或红色
首先，红黑树有两个子节点的删除和二叉搜索树方法是一样的，通过寻找前驱节点或者后继节点来继续替换删除，这里选择的是后继节点 替换删除！
当被删结点 node 有两个子结点时，我们先找到这个被删结点的后继结点 successor，然后用 successor 替换 node 的值，不用改变颜色，此时转换为删除 node 的后继节点 successor。
- 图a情况：
- 若
successor为红色，则变成了组合1 - 若
successor为黑色，则变成了组合2
- 若
- 图b情况：
- 若
successor为红色，则变成了组合1（组合3是不可能的） - 若
successor为黑色，则变成了组合2或组合4
- 若
// 左右子树都存在的情况
// 先找到后继节点minRight
Node* minRight = cur->_right;
Node* minParent = cur;
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
cur->_kv = minRight->_kv;
// 图b情况
if (cur == minParent)
{
// 若为红色，则可直接删除该节点
if (minRight->_col == RED)
{
delete minRight;
minParent->_right = nullptr;
}
else // 若为黑色，则转化为组合2和组合4的问题
{
// 若存在右子树说明是组合4
if (minRight->_right != nullptr)
{
// 将右子树替换掉被删节点，删掉被删节点
Node* right = minRight->_right;
right->_parent = minParent;
minParent->_right = right;
delete minRight;
// 最后变色
right->_col = BLACK;
}
else // 若不存在右子树说明是组合2
{
Erase_balanceTwo(minRight);
minParent->_right = nullptr;
delete minRight;
}
}
}
else // 图a情况
{
// 若为红色，则可直接删除该节点
if (minRight->_col == RED)
{
delete minRight;
minParent->_left = nullptr;
}
else // 若为黑色，则转化为组合2或组合4的问题
{
// 若存在右子树说明是组合4
if (minRight->_right != nullptr)
{
// 将右子树替换掉被删节点，删掉被删节点
Node* right = minRight->_right;
right->_parent = minParent;
minParent->_left = right;
delete minRight;
// 最后变色
right->_col = BLACK;
}
else // 若不存在右子树说明是组合2
{
Erase_balanceTwo(minRight);
minParent->_left = nullptr;
delete minRight;
}
}
} 综上所述：组合5 6被转换为前面几种组合，我们真正要进行删除的只有组合1 2 4，对于组合 1 和 4，删除操作相当简单，这里不再多讲，接下来再逐一分析组合2可能的几种情形。
🔺 注意： 记得还要处理一下如果 被删节点是 _root 的情况！
// 被删节点是_root
if (cur == _root)
{
if (cur->_left == nullptr && cur->_right != nullptr)
{
_root = _root->_right;
_root->_col = BLACK;
}
else if (cur->_right == nullptr && cur->_left != nullptr)
{
_root = _root->_left;
_root->_col = BLACK;
}
else
{
_root = nullptr;
}
delete cur;
}细谈组合2：被删结点无子结点，且被删结点为黑色
我们先来约定一个结果，就是上面组合 2 中，我们把黑色的叶子节点删掉后，这里我们用一个黑色的 null 节点来代替那个位置，方便我们后续情况的理解：
注意这里这个 null 只是我们假想出来方便我们理解情况的！
情形一：brother/uncle 为黑色，且 brother/uncle 有一个与其方向一致的红色子结点 son
所谓方向一致，是指 uncle 为 parent 的左子结点，son 也为 uncle 的左子结点；或者 uncle 为 parent 的右子结点，son 也为 uncle 的右子结点。
这里以 brother 为右子树为例：
图©中，白色代表随便是黑或是红，方形结点存储的是一个游离的黑色权值。将 brother 和 father 旋转（是左旋还是右旋自己根据情景体会，下同），并重新上色后，变成了图(d)，将游离的黑色权值扔掉，此时不违背任何红黑树的性质，删除操作完成。
图©中的情形颠倒过来，也是一样的操作。
解决方法：
左旋 brother （若 brother 为左子树则右旋）
将 son 变成黑色、brother 变成 father 的颜色、father 变成黑色
删除节点
if (parent->_left == cur) // uncle为parent右子树
{
if ((uncle->_left && uncle->_left->_col == RED) || (uncle->_right && uncle->_right->_col == RED))
{
if (uncle->_right != nullptr) // 情形一
{
// 变色 +
uncle->_right->_col = BLACK;
uncle->_col = parent->_col;
parent->_col = BLACK;
RotateL(parent);
}
// .....
}
// .....
}
else // uncle为parent左子树
{
if ((uncle->_left && uncle->_left->_col == RED) || (uncle->_right && uncle->_right->_col == RED))
{
if (uncle->_left != nullptr) // 情形一
{
// 变色 + 右旋
uncle->_left ->_col = BLACK;
uncle->_col = parent->_col;
parent->_col = BLACK;
RotateR(parent);
}
// .....
}
// .....
}情形二：brother/uncle 为黑色，且 brother/uncle 有一个与其方向不一致的红色子结点 son
这里以 brother 为右子树为例：
图(e)中，将 son 和 brother 旋转，重新上色后，变成了图(f)，转化为情形一。
图(e)中的情形颠倒过来，也是一样的操作。
解决方法：
右旋 brother（若 brother 为左子树则左旋）
交换 brother 与 son 的颜色
回到情形一（重新调用子函数即可）
if (parent->_left == cur) // uncle为parent右子树
{
if ((uncle->_left && uncle->_left->_col == RED) || (uncle->_right && uncle->_right->_col == RED))
{
//.....
else //情形二
{
uncle->_left->_col = BLACK;
uncle->_col = RED;
RotateR(uncle);
Erase_balanceTwo(cur);
}
}
//.....
}
else // uncle为parent左子树
{
if ((uncle->_left && uncle->_left->_col == RED) || (uncle->_right && uncle->_right->_col == RED))
{
//.....
else // 情形二
{
uncle->_right->_col = BLACK;
uncle->_col = RED;
RotateL(uncle);
Erase_balanceTwo(cur);
}
}
//.....
}情形三：brother/uncle 为黑色，且 brother/uncle 无红色子结点
1、此时若 father 为红，则重新着色即可，删除操作完成。如图下图(g)和(h)
解决方法：
- 将
father颜色变成黑色 - 将
brother颜色变成红色
2、此时若 father 为黑，则重新着色，将游离的黑色权值存到 father（此时 father 的黑色权重为 2），将 father 作为新的结点进行情形判断，遇到情形一、情形二，则进行相应的调整，完成删除操作；如果没有，则结点一直上溯，直到根结点存储额外的黑色，此时将该额外的黑色扔掉，即完成了删除操作。
注意： 这里第二种情况有点不好理解，之所以要加一个游离的黑色是因为删除 node 后造成 node 子树和 brother 子树的黑节点个数不平衡，这里的操作实际是将 brother 子树中黑节点个数减少一个，而将 father 黑色权重设为 2，这样 father 左右两边的子树不用加游离的权值都是平衡的了。接下来将问题转移到了 father、father 的 father、father 的 brother 三个之间，这样向上递归，如果一直是这种情况，最终必定转化为 root 的左子节点或者右子节点权重为 2，同样的将 root 黑色权重设为 2，将另外一边的黑色权重减小 1，再将 root 的黑色权重扔掉一个，此时整棵树重回平衡，只是 root 到叶节点路径的黑节点少了一个。
解决方法：
将 brother 的颜色变成红色
以 father 为新的节点，继续调用子函数往上调整，直到遇到根节点或者遇到其他情况
//......
if(cur == _root)
return;
if (parent->_col == RED)
{
parent->_col = BLACK;
uncle->_col = RED;
}
else
{
uncle->_col = RED;
Erase_balanceTwo(parent);
}情形四：brother/uncle 为红色，则 parent/father 必为黑色。
这里以 brother 为右子树为例：
图(i)中，将 brother 和 father 旋转，重新上色后，变成了图(j)，新的 brother（原来的 son）变成了黑色，这样就成了情形一、二、三中的一种。如果将 son和 brother 旋转，无论怎么重新上色，都会破坏红黑树的性质4或5，例如图(k)。
图(i)中的情形颠倒过来，也是一样的操作。
解决方法：
对 father 左旋（若brother为左子树则对father右旋）
将 father 的颜色变成红色
将 brother 的颜色变成黑色
转化为其他三种情况去解决（重新调用子函数）
if (parent->_left == cur) // uncle为parent右子树
{
Node* uncle = parent->_right;
if (uncle->_col == RED) // 情形四
{
RotateL(parent);
parent->_col = RED;
uncle->_col = BLACK;
Erase_balanceTwo(cur); // 对x重新执行这个过程，此时一定是情形一 二 三中的一种
}
//......
}
else // uncle为parent左子树
{
Node* uncle = parent->_left;
if (uncle->_col == RED) // 情形四
{
RotateR(parent);
parent->_col = RED;
uncle->_col = BLACK;
Erase_balanceTwo(cur); // 对x重新执行这个过程，此时一定是情形一 二 三中的一种
}
//......
}删除的完整代码
bool Erase(const K& key)
{
if (_root == nullptr)
return false;
// 先找到要删除的节点
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
// 找到了节点就开始删除
if (cur->_left == nullptr || cur->_right == nullptr)
{
if (cur == _root)
{
if (cur->_left == nullptr && cur->_right != nullptr)
{
_root = _root->_right;
_root->_col = BLACK;
}
else if (cur->_right == nullptr && cur->_left != nullptr)
{
_root = _root->_left;
_root->_col = BLACK;
}
else
{
_root = nullptr;
}
delete cur;
}
else if (cur->_left == nullptr && cur->_right != nullptr)
{
Node* right = cur->_right;
Node* parent = cur->_parent;
right->_parent = parent;
if (parent->_left == cur)
{
parent->_left = right;
}
else
{
parent->_right = right;
}
delete cur;
// 最后将left的颜色改为黑色
right->_col = BLACK;
}
else if (cur->_left != nullptr && cur->_right == nullptr)
{
Node* left = cur->_left;
Node* parent = cur->_parent;
left->_parent = parent;
if (parent->_left == cur)
{
parent->_left = left;
}
else
{
parent->_right = left;
}
delete cur;
// 最后将left的颜色改为黑色
left->_col = BLACK;
}
else if (cur->_left == nullptr && cur->_right == nullptr) // 无叶子节点
{
if (cur->_col == RED)
{
// 直接删除节点即可
if (cur->_parent->_left == cur)
{
cur->_parent->_left = nullptr;
}
else
{
cur->_parent->_right = nullptr;
}
}
else
{
Erase_balanceTwo(cur);
if (cur->_parent->_left == cur)
{
cur->_parent->_left = nullptr;
}
else
{
cur->_parent->_right = nullptr;
}
}
delete cur;
}
}
else // 左右子树都存在的情况
{
Node* minRight = cur->_right;
Node* minParent = cur;
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
cur->_kv = minRight->_kv;
if (cur == minParent)
{
// 若为红色，则可直接删除该节点
if (minRight->_col == RED)
{
delete minRight;
minParent->_right = nullptr;
}
else // 若为黑色，则转化为组合2和组合4的问题
{
if (minRight->_right != nullptr)
{
Node* right = minRight->_right;
right->_parent = minParent;
minParent->_right = right;
delete minRight;
// 最后变色
right->_col = BLACK;
}
else
{
Erase_balanceTwo(minRight);
minParent->_right = nullptr;
delete minRight;
}
}
}
else
{
// 若为红色，则可直接删除该节点
if (minRight->_col == RED)
{
delete minRight;
minParent->_left = nullptr;
}
else // 若为黑色，则转化为组合2或组合4的问题
{
if (minRight->_right != nullptr)
{
Node* right = minRight->_right;
right->_parent = minParent;
minParent->_left = right;
delete minRight;
// 最后变色
right->_col = BLACK;
}
else
{
Erase_balanceTwo(minRight);
minParent->_left = nullptr;
delete minRight;
}
}
}
}
return true;
}
}
return false;
}
// 处理情况二的函数
void Erase_balanceTwo(Node* cur)
{
if (cur == _root)
return;
Node* parent = cur->_parent;
if (parent->_left == cur) // uncle为parent右子树
{
Node* uncle = parent->_right;
if (uncle->_col == RED)
{
RotateL(parent);
parent->_col = RED;
uncle->_col = BLACK;
Erase_balanceTwo(cur); // 对x重新执行这个过程，此时一定是情形一 二 三中的一种
}
else
{
if ((uncle->_left && uncle->_left->_col == RED) ||
(uncle->_right && uncle->_right->_col == RED))
{
if (uncle->_right != nullptr)
{
uncle->_right->_col = BLACK;
uncle->_col = parent->_col;
parent->_col = BLACK;
RotateL(parent);
}
else
{
uncle->_left->_col = BLACK;
uncle->_col = RED;
RotateR(uncle);
Erase_balanceTwo(cur);
}
}
else
{
if (cur == _root)
return;
if (parent->_col == RED)
{
parent->_col = BLACK;
uncle->_col = RED;
}
else
{
uncle->_col = RED;
Erase_balanceTwo(parent);
}
}
}
}
else // uncle为parent左子树
{
Node* uncle = parent->_left;
if (uncle->_col == RED)
{
RotateR(parent);
parent->_col = RED;
uncle->_col = BLACK;
Erase_balanceTwo(cur); // 对x重新执行这个过程，此时一定是情形一 二 三中的一种
}
else
{
if ((uncle->_left && uncle->_left->_col == RED) ||
(uncle->_right && uncle->_right->_col == RED))
{
if (uncle->_left != nullptr)
{
uncle->_left ->_col = BLACK;
uncle->_col = parent->_col;
parent->_col = BLACK;
RotateR(parent);
}
else
{
uncle->_right->_col = BLACK;
uncle->_col = RED;
RotateL(uncle);
Erase_balanceTwo(cur);
}
}
else
{
if (parent->_col == RED)
{
parent->_col = BLACK;
uncle->_col = RED;
}
else
{
uncle->_col = RED;
Erase_balanceTwo(parent);
}
}
}
}
}Ⅷ. 红黑树的验证
红黑树的检测分为两步：
- 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
- 检测其是否满足红黑树的性质
bool _CheckBlance(Node* root, int blackNum, int count)
{
// 走到nullptr之后，判断count和blackNum是否相等
if (root == nullptr)
{
if (count != blackNum)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}
return true;
}
// 检测当前节点与其双亲是否都为红色
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}
// 统计黑色节点的个数
if (root->_col == BLACK)
{
count++;
}
return _CheckBlance(root->_left, blackNum, count)
&& _CheckBlance(root->_right, blackNum, count);
}
bool CheckBlance()
{
// 空树也是红黑树
if (_root == nullptr)
{
return true;
}
// 检测根节点是否满足情况
if (_root->_col == RED)
{
cout << "根节点是红色的" << endl;
return false;
}
// 获取任意一条路径中黑色节点的个数
int blackNum = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
{
blackNum++;
}
left = left->_left;
}
// 检测是否满足红黑树的性质，count用来记录路径中黑色节点的个数
int count = 0;
return _CheckBlance(_root, blackNum, count);
}Ⅸ. AVL树和红黑树的比较
红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O(
) ，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
腾讯云开发者
