C++笔记---红黑树的插入删除
大筒木老辈子 2024-10-19 15:35:03 阅读 86
1. 红黑树的概念
红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。 通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保对于任意一个结点，没有一条到NULL结点的路径会比其他到NULL结点的路径长度的两倍以上，因而是接近平衡的。
1.1 红黑树的规则
1. 每个结点不是红色就是黑色。
2. 根结点是黑色的。
3. 任意一条路径不会有连续的红色结点(也就是说，如果一个结点是红色的，则它的两个孩子结点必须是黑色的)。
4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点。
说明：《算法导论》等书籍上补充了一条每个叶子结点(NIL)都是黑色的规则。他这里所指的叶子结点不是传统的意义上的叶子结点，而是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道一下这个概念即可。
红黑树规则的理解
上面的规则乍一看上去会使人摸不着头脑，这些规则有什么用呢？
我们可以这样来理解上面的规则为什么这样来制定：
对于红黑树中的任意一颗子树的根结点，它到NULL结点的每一条路径都是由数量相同的黑色结点连接而成，而每个黑色结点的后面可以插入至多一个红色结点。
这样一来，最短的路径就是没有插入任何红色结点的路径，最长的路径就是在每个黑色结点之后都插入一个红色结点。
假设黑色结点的数量为n，则最短路径长度为n，最长路径长度为2n。
这样就保证了对于每一个结点来说，没有一条到NULL结点的路径会比其他到NULL结点的路径长度的两倍以上。
至于为什么根结点一定要是黑色，我们在具体实现插入删除的过程中会窥见其必要性。
1.2 红黑树的效率
相比于AVL树（C++笔记---AVL树的插入删除-CSDN博客），红黑树对平衡的控制不那么严格，在查找时的效率会较低一些。
假设N是红黑树中结点数量，h最短路径的长度，那么
，由此推出
，也就是意味着红黑树增删查改最坏也就是走最长路径
，那么时间复杂度还是
。
但是相对的，由于红黑树对平衡的控制不像AVL树那样精细，所以红黑树在插入删除的过程中调整和旋转的次数都相对较少，在大多数情况下，红黑树要比AVL树更优一些。
例如，STL标准库中的map和set均是由红黑树适配出的。
1.3 红黑树的基本代码框架
<code>// 枚举值表示颜色
enum Colour
{
RED,
BLACK
};
// 这里我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
// 这里更新控制平衡也要加入parent指针
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv, Colour col = RED)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(col)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree() = default;
RBTree(const RBTree& tree);
RBTree(const initializer_list<const pair<K, V>> li);
~RBTree();
RBTree& operator=(RBTree tree);
bool Insert(const pair<K, V>& kv);
bool Erase(const K& k);
void RotateR(Node* parent);
void RotateL(Node* parent);
Node* Find(const K& key);
void InOrder();
private:
Node* _root = nullptr;
};
本文中，我们主要讲解插入删除的逻辑，其他函数可以参考文末的完整代码。
除此之外，我们设计了一个成员函数isRBTree来帮助我们判断我们的红黑树是否合格：
public:
bool isRBTree()
{
if (_isRBTree(_root) == -1)
return false;
else
return true;
}
private:
int _isRBTree(Node* root)
{
int flag = 0;
if (root == nullptr)
return 0;
if (root->;_col == RED && root->_parent->_col == RED)
return -1;
if (root->_col == BLACK)
flag = 1;
int left = _isRBTree(root->_left);
int right = _isRBTree(root->_right);
if (left == right)
return left + flag;
else
return -1;
}
2. 红黑树的插入
新增结点我们一般设置为红色，若插入黑色结点，则必定导致规则4失效，需要对其余的每一条路径都进行检查调整，以确保每一条路径的黑色结点数一致，十分麻烦。
可忽略：
由于规则4的难维护性，我们在插入之后的调整过程中也是在不改变某一条路径的的黑色结点数的情况下进行的（或者所有路径同时发生变化）。
所有路径同时发生变化是指在调整过程中根结点被调整为了红色，而为了维护规则2，我们又会将其改回黑色（只有根结点可以在不调整其他结点的情况下直接变色）。
根结点每次变色，每条路径中的黑色结点数才会加一，可以说红黑树是依靠其根汲取营养生长起来的，简直是太形象了。
2.1 插入的大致过程
1. 按照搜索二叉树的规则进行插入。
2. 若插入之后，新增结点的父结点为黑色，则红黑树的规则未被破坏，插入成功。
3. 若插入之后，新增结点的父结点为红色，则规则3被破坏，需要进行调整。
4. 调整结束之后，将根结点置为黑色。
我们将新增结点记为c(cur)，其父结点记为p(parent)，parent的父结点记为g(grandfather)，parent的兄弟结点记为u(uncle)。
在第三点中我们谈到规则3被破坏，此时c为红，p为红，g必定为黑，而u不确定。
如果规则3被违反而进入了调整阶段，我们可以断言g必定存在，因为根结点为黑。
在此基础上，我们展开对u的讨论：红/黑/不存在。并以此确定调整方案。
下面我们以p为g的左孩子为例进行讨论，p为g的右孩子的情况可类比得出。
2.2 u为红：直接变色
由于c，p破坏了规则3，所以要将二者之一变为黑色。
如果将c变为黑色则与直接插入黑色结点没有区别，所以p一定要变成黑色。
为了保证gpc路径上的黑色结点数不变，需要将g变为红色；又为了保证gu路径黑色结点数不变，需要将u变为黑色。
总结来说，p必须要变成黑色，为了使p变成黑色且路径上的黑色结点数不变，我们让黑色向下移动一层，分散到两条分路径上。
正因为u为红色，我们才可以进行这样的移动。
当然，如果c是新增结点的话，根据规则4，u必定为红色（或者不存在）；但如果c不是新增结点，则可能是黑色。
向上调整：
g变为红色，若g的父结点为红色，则规则3再次被破坏。
此时，我们将g当作新增结点c，继续向上调整，直到规则3不再被破坏。
图中矩形表示子树，h表示该子树中各路径黑色结点的个数。
可以看到，若c不是新增结点而是向上调整过程中更新的c，那么u必定存在，因为gp...路径中必定包含黑色结点。
2.3 u不存在或u为黑色：看c的位置
这类情况下，调整之后子树根结点都为黑色，无需向上调整。
2.3.1 pc在同一边：变色+单旋
pc在同一边指两个都是其父的左孩子或两个都是其父的右孩子。
我们前面指定了讨论p为g左孩子的情况，所以这里讨论的就是c为p左孩子的情况。
u不存在，说明c一定是新增结点，我们采用下面的方式来调整：
即，先让pg交换颜色，再以p为中心进行一次旋转。
u为黑色，说明c一定不是新增结点，我们采用下面的方式来调整：
依然是相同的操作方式，所以二者被归为一类。
2.3.2 c与p不在同一边：双旋+变色
同样，这里讨论的就是c为p右孩子的情况。
与AVL树类似，这种情况下无法使用单旋，我们也采用双旋的方式进行调整，同时改变关键结点的颜色以确保黑色结点数不变。
u不存在，说明c一定是新增结点，我们采用下面的方式来调整：
以p为中心进行一次单旋之后，就与上面的情况相同了。
u为黑色，说明c一定不是新增结点，我们采用下面的方式来调整：
依然是相同的操作方式，所以二者被归为一类。
2.4 红黑树插入代码实现
下面的代码不完全按照上面的分类讨论进行if-else的编写，而是将一些逻辑进行了精简合并。
例如，不双旋时颜色变化是统一的，所以在if-else之前统一变了一次色：
双旋的第一步处理之后可以按照单旋逻辑处理：
代码如下：
<code>bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->;_col = BLACK;
return true;
}
Node* cur = _root, *parent = nullptr;
while (cur)
{
parent = cur;
if (kv.first < cur->_kv.first)
cur = cur->_left;
else if (kv.first > cur->_kv.first)
cur = cur->_right;
else
return false;
}
cur = new Node(kv);
cur->_col = RED;
if (kv.first < parent->_kv.first)
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
while (parent && parent->_col == RED)
{
// 因为_root为黑色，所以parent为红色，grandfather一定存在且为黑色
Node* grandfather = parent->_parent;
// 不进行双旋时需变色
parent->_col = BLACK;
grandfather->_col = RED;
if (parent == grandfather->_left)// uncle在右子树
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)// uncle存在且为红，直接变色
{
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else// uncle不存在或为黑，变色加旋转
{
if (cur == parent->_right)
{
RotateL(parent);
if (uncle)
uncle->_col = RED;
parent->_col = RED;
cur->_col = BLACK;
}
RotateR(grandfather);
break;// 转后parent为子树根（黑），无需继续向上更新
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(parent);
if (uncle)
uncle->_col = RED;
parent->_col = RED;
cur->_col = BLACK;
}
RotateL(grandfather);
break;
}
}
}
_root->_col = BLACK;
return true;
}
3. 红黑树的删除
删除逻辑是博主大战了一个下午，4个小时呕心沥血的杰作，个人感觉十分有成就感。
希望大家多多支持，有错误或遗漏的地方欢迎在评论区指出。
3.1 删除的大致过程
1. 按照二叉搜索树的规则查找要删除的结点。
2. 如果要删除的结点有两个孩子，则用替换法更新要删除的结点。
3. 删除红色结点，任何规则都不会被破坏，直接删除。
4. 删除黑色结点一定会破坏规则4，分情况进行讨论。
删除逻辑中子树根结点调整前后都是黑色，所以不必担心根结点颜色被该的问题。
下面我们只考虑被删除的结点为黑色的情况，且被删除结点为其父的左孩子。
与插入时不同，黑色结点周围的结点是什么颜色完全无法确定，都需要讨论。
我们用d(delete)来代表要被删除的结点，p(parent)代表其父结点，b(brother)代表其兄弟结点。
3.2 d只有一个孩子：孩子上位替父
d只有一个孩子，则d的一边为空，其唯一的孩子一定为红色。
这时让孩子顶替d的位置，并变为黑色即可，太简单了就不画图了。
3.3 d无孩子：拜托老父亲和兄弟
自己的工作很重要，还没有孩子接替，那就只能找兄弟或老父亲帮帮忙了（旋转+变色）。
3.3.1 父亲为红色：变色
父亲为红色，兄弟一定为黑色，让父结点与兄弟结点的颜色交换即可。
这个过程可以理解为插入时直接变色的情况的逆过程：
即，将各个分路径上的黑色结点上归一到主路径上。
这样一来，要删除的结点就是一个红色结点了，可以直接删除（但没必要真把它变个颜色，直接删除即可）。
3.3.2 父亲为黑色，兄弟为红色：单旋+变色
此时，根据规则4可知，兄弟的两个孩子都必定为黑色，可以采取以下方式进行调整：
即，将兄弟变为红色，兄弟的内侧孩子变为红色，然后以p为中心进行单旋。
看到初始状态，思维敏捷的小伙伴的第一直觉肯定是采用双旋的方式调整。
但其实采用双旋调整之后规则4依然不满足，我最开始也是这样想的，但是被我写的isRBTree检查出来不合格了，所以调整为了这个方案。
3.3.3 父亲为黑色，兄弟为黑色：看兄弟的孩子
兄弟没有孩子：变色+向上调整
删掉d之后该子树下仅剩下两个黑色结点：
不变色则该子树无论如何调整，自身都不满足规则4；
改变兄弟结点的颜色则经过该子树的路径上的黑色结点数都减少1，整颗树不满足规则4。
虽然变色会导致整棵树不满足规则4，但是我们清楚地知道问题的发源处。
我们可以把兄弟变为红色，然后将这个双结点的简单子树当作被删除的结点（被删除的结点会导致其所在路径黑色结点数减少1，而改子树发生的变化同样导致了相同的问题），向上调整。
这也是唯一需要向上调整的情况。
兄弟有外侧孩子：变色+单旋
将兄弟的外侧孩子变为黑色，然后以p为中心进行一次旋转。
可以从图中看出，在b有外侧孩子的情况下，无论其是否有内侧孩子，都可以使用该种方式进行调整。
兄弟无外侧孩子，有内侧孩子：变色+双旋
将内侧孩子变为黑色，然后以b为中心进行一次旋转，再以p为中心进行一次旋转。
3.4 红黑树删除代码实现
<code>bool Erase(const K& k)
{
Node* del = Find(k);
if (del == nullptr)
return false;
// 两个孩子都有，更新要删除的结点
if (del->;_left && del->_right)
{
Node* replace = del->_right;
while (replace->_left) { replace = replace->_left; }
std::swap(del->_kv, replace->_kv);
del = replace;
}
// 接下来处理至少一个孩子为空
if (del == _root)
_root = nullptr;
else if (del->_left || del->_right || del->_col == RED)// 有一个孩子或为红色
{
Node* child = del->_left ? del->_left : del->_right;
if (child)
child->_parent = del->_parent;
if (del->_parent->_left == del)
del->_parent->_left = child;
else
del->_parent->_right = child;
if (del->_col == BLACK)
child->_col = BLACK;
}
else// 没有孩子且为黑色
{
Node* cur = del;// 可能会向上调整，用cur代替del，始终认为cur无孩子
while (1)
{
if (cur->_parent->_col == RED)// 父结点为红色，一定有黑色兄弟，直接删除+变色
{
cur->_parent->_col = BLACK;
if (cur->_parent->_left == cur)
{
cur->_parent->_left = nullptr;
cur->_parent->_right->_col = RED;
}
else
{
cur->_parent->_right = nullptr;
cur->_parent->_left->_col = RED;
}
}
else// 父结点为黑色，看情况单双旋或调整
{
Node* parent = cur->_parent;
if (parent->_left == cur)// 在左，右边是兄弟
{
Node* brother = parent->_right;
parent->_left = nullptr;
if (brother->_col == RED)// 红色兄弟，一定有两个黑孩子
{
brother->_col = BLACK;
brother->_left->_col = RED;
RotateL(parent);
}
else// 黑色兄弟，要么没孩子，要么有红孩子
{
if (brother->_left == nullptr && brother->_right == nullptr)// 兄弟没孩子，差一个调不了，向上调整
{
brother->_col = RED;
cur = parent;
continue;
}
else if (brother->_right)
{
brother->_right->_col = BLACK;
RotateL(parent);
}
else
{
brother->_left->_col = BLACK;
RotateR(brother);
RotateL(parent);
}
}
}
else// 在右，左边是兄弟
{
Node* brother = parent->_left;
parent->_right = nullptr;
if (brother->_col == RED)// 红色兄弟，一定有两个黑孩子
{
brother->_col = BLACK;
brother->_right->_col = RED;
RotateR(parent);
}
else// 黑色兄弟，要么没孩子，要么有红孩子
{
if (brother->_left == nullptr && brother->_right == nullptr)// 兄弟没孩子，差一个调不了，向上调整
{
brother->_col = RED;
cur = parent;
continue;
}
else if (brother->_left)
{
brother->_left->_col = BLACK;
RotateR(parent);
}
else
{
brother->_right->_col = BLACK;
RotateL(brother);
RotateR(parent);
}
}
}
}
break;
}
}
delete del;
return true;
}
4. 完整代码示例
#pragma once
// 枚举值表示颜色
enum Colour
{
RED,
BLACK
};
// 这里我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
// 这里更新控制平衡也要加入parent指针
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv, Colour col = RED)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(col)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree() = default;
RBTree(const RBTree& tree)
{
_root = Construct(tree._root);
}
RBTree(const initializer_list<const pair<K, V>>& li)
{
for (auto& e : li)
{
Insert(e);
}
}
~RBTree()
{
Destroy(_root);
_root = nullptr;
}
RBTree& operator=(RBTree tree)
{
std::swap(_root, tree._root);
return *this;
}
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* cur = _root, *parent = nullptr;
while (cur)
{
parent = cur;
if (kv.first < cur->_kv.first)
cur = cur->_left;
else if (kv.first > cur->_kv.first)
cur = cur->_right;
else
return false;
}
cur = new Node(kv);
cur->_col = RED;
if (kv.first < parent->_kv.first)
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
while (parent && parent->_col == RED)
{
// 因为_root为黑色，所以parent为红色，grandfather一定存在且为黑色
Node* grandfather = parent->_parent;
// 不进行双旋时需变色
parent->_col = BLACK;
grandfather->_col = RED;
if (parent == grandfather->_left)// uncle在右子树
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)// uncle存在且为红，直接变色
{
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else// uncle不存在或为黑，变色加旋转
{
if (cur == parent->_right)
{
RotateL(parent);
if (uncle)
uncle->_col = RED;
parent->_col = RED;
cur->_col = BLACK;
}
RotateR(grandfather);
break;// 转后parent为子树根（黑），无需继续向上更新
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(parent);
if (uncle)
uncle->_col = RED;
parent->_col = RED;
cur->_col = BLACK;
}
RotateL(grandfather);
break;
}
}
}
_root->_col = BLACK;
return true;
}
bool Erase(const K& k)
{
Node* del = Find(k);
if (del == nullptr)
return false;
// 两个孩子都有，更新要删除的结点
if (del->_left && del->_right)
{
Node* replace = del->_right;
while (replace->_left) { replace = replace->_left; }
std::swap(del->_kv, replace->_kv);
del = replace;
}
// 接下来处理至少一个孩子为空
if (del == _root)
_root = nullptr;
else if (del->_left || del->_right || del->_col == RED)// 有一个孩子或为红色
{
Node* child = del->_left ? del->_left : del->_right;
if (child)
child->_parent = del->_parent;
if (del->_parent->_left == del)
del->_parent->_left = child;
else
del->_parent->_right = child;
if (del->_col == BLACK)
child->_col = BLACK;
}
else// 没有孩子且为黑色
{
Node* cur = del;// 可能会向上调整，用cur代替del，始终认为cur无孩子
while (1)
{
if (cur->_parent->_col == RED)// 父结点为红色，一定有黑色兄弟，直接删除+变色
{
cur->_parent->_col = BLACK;
if (cur->_parent->_left == cur)
{
cur->_parent->_left = nullptr;
cur->_parent->_right->_col = RED;
}
else
{
cur->_parent->_right = nullptr;
cur->_parent->_left->_col = RED;
}
}
else// 父结点为黑色，看情况单双旋或调整
{
Node* parent = cur->_parent;
if (parent->_left == cur)// 在左，右边是兄弟
{
Node* brother = parent->_right;
parent->_left = nullptr;
if (brother->_col == RED)// 红色兄弟，一定有两个黑孩子
{
brother->_col = BLACK;
brother->_left->_col = RED;
RotateL(parent);
}
else// 黑色兄弟，要么没孩子，要么有红孩子
{
if (brother->_left == nullptr && brother->_right == nullptr)// 兄弟没孩子，差一个调不了，向上调整
{
brother->_col = RED;
cur = parent;
continue;
}
else if (brother->_right)
{
brother->_right->_col = BLACK;
RotateL(parent);
}
else
{
brother->_left->_col = BLACK;
RotateR(brother);
RotateL(parent);
}
}
}
else// 在右，左边是兄弟
{
Node* brother = parent->_left;
parent->_right = nullptr;
if (brother->_col == RED)// 红色兄弟，一定有两个黑孩子
{
brother->_col = BLACK;
brother->_right->_col = RED;
RotateR(parent);
}
else// 黑色兄弟，要么没孩子，要么有红孩子
{
if (brother->_left == nullptr && brother->_right == nullptr)// 兄弟没孩子，差一个调不了，向上调整
{
brother->_col = RED;
cur = parent;
continue;
}
else if (brother->_left)
{
brother->_left->_col = BLACK;
RotateR(parent);
}
else
{
brother->_right->_col = BLACK;
RotateL(brother);
RotateR(parent);
}
}
}
}
break;
}
}
delete del;
return true;
}
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* subR = cur->_right;
parent->_left = subR;
if (subR)
subR->_parent = parent;
cur->_right = parent;
cur->_parent = parent->_parent;
if (parent->_parent)
{
if (parent->_parent->_left == parent)
parent->_parent->_left = cur;
else
parent->_parent->_right = cur;
}
parent->_parent = cur;
if (parent == _root)
_root = cur;
}
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* subL = cur->_left;
parent->_right = subL;
if (subL)
subL->_parent = parent;
cur->_left = parent;
cur->_parent = parent->_parent;
if (parent->_parent)
{
if (parent->_parent->_left == parent)
parent->_parent->_left = cur;
else
parent->_parent->_right = cur;
}
parent->_parent = cur;
if (parent == _root)
_root = cur;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key == cur->_kv.first)
return cur;
else if (key < cur->_kv.first)
cur = cur->_left;
else
cur = cur->_right;
}
return nullptr;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool isRBTree()
{
if (_isRBTree(_root) == -1)
return false;
else
return true;
}
private:
Node* Construct(Node* root)
{
if (root == nullptr)
return nullptr;
Node* copy = new Node(root->_kv, root->_col);
copy->_left = Construct(root->_left);
copy->_left->_parent = copy;
copy->_right = Construct(root->_right);
copy->_right->_parent = copy;
return copy;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << " ";
_InOrder(root->_right);
}
int _isRBTree(Node* root)
{
int flag = 0;
if (root == nullptr)
return 0;
if (root->_col == RED && root->_parent->_col == RED)
return -1;
if (root->_col == BLACK)
flag = 1;
int left = _isRBTree(root->_left);
int right = _isRBTree(root->_right);
if (left == right)
return left + flag;
else
return -1;
}
private:
Node* _root = nullptr;
};
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。