目录
1.知识回顾
在C++ Contest专栏提到过红黑树,可回顾:
在C++ Develop专栏提到过AVL树,可回顾:
CD76.【C++ Dev】AVL的模拟实现(1) 以左单旋为切口,分析旋转规律
红黑树的性质:
1.前提是二叉搜索树
2.根结点以及叶子结点是黑色的★注意:这里的叶子结点不是常规意义上的叶子结点,而是指空结点
3.红色结点的左右孩子必须是黑色的,换句话说,任意一条路径中,不会存在连续的红色结点
4.任一结点到叶子结点的路径上,黑色结点的数量相同
满足了所有的性质,就满足了最长路径不超过最短路径的2倍
2.对比AVL树和红黑树
| AVL树 | 红黑树 | |
| 特点 | 左右子树的高度差的绝对值不超过1 | 最长路径不超过最短路径的2倍 |
| 插入N个结点后大致的高度 | logN(最多高度次) | 2*logN(按照最短路径和最长路径的关系来估计) |
| 效率上几乎没有差别 | ||
可以发现红黑树和AVL树在插入N个结点大致次数上的性能是同一个量级的,增删改查的时间复杂度都是
红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说在经常进行增删的结构中,红黑树的性能要优于AVL树
3.插入的模拟实现
重点关注红黑树的染色方法和旋转过程即可
结构
先写红黑树结点的结构,内部包含三叉链(左指针、右指针、父指针),存储的pair数据,结点的颜色
而结点的颜色可以使用枚举语法
enum color
{
RED,
BLACK
};
template<class K,class V>
class rbtree_node
{
public:
rbtree_node<K, V>* _left;
rbtree_node<K, V>* _right;
rbtree_node<K, V>* _parent;
pair<K, V> _pack;
color _col;
};注: 枚举语法参见67.【C语言】枚举类型文章
红黑树的结构(未写成员函数):
template<class K, class V>
class rbtree
{
typedef rbtree_node<K, V> node;
private:
node* _root;
};插入函数
因为红黑树符合二叉搜索树的性质,因此先借用CD77.【C++ Dev】AVL的模拟实现(2) 继续编写插入函数文章的插入函数,后续再修改
对于空的红黑树,一开始插入的结点必定为根结点
问题1: 根结点是什么颜色?
由红黑树的性质可知,根结点是黑色,因此:
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new node(kv);
_root->_col = BLACK;
return true;
}
//......
}问题2: 插入的结点优先考虑什么颜色?
红黑树中重要的性质是:
3.红色结点的左右孩子必须是黑色的,换句话说,任意一条路径中,不会存在连续的红色结点
4.任一结点到叶子结点的路径上,黑色结点的数量相同
会发现性质4非常苛刻,要求从任意结点出发,每条路径的黑色结点的数量相同,因此插入黑色结点可能要对树做较大的改动,比较麻烦,影响大
而插入红色结点的影响小,因为"红色结点的左右孩子必须是黑色的",只影响当前路径,不影响其他路径
插入结点的父结点是黑色
借用Sun_TTTT博主的图,如果父结点是黑色的,那么能顺利插入红结点,不用进行变色或者旋转的
综上所述,优先插入红色结点
那么有:先找到插入的位置,默认是红色结点
node* parent = nullptr;
node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new node(kv);
cur->_col = RED;
//......插入结点的父结点是红色
需要看叔叔结点uncle,一共就三种情况
parent、uncle和grandparent之间的关系:
1.如果uncle存在且为红色
在22的左侧插入新结点,如何修改结点的颜色?
上图违反了"不会存在连续的红色结点",那么parent和cur必须有一个要变黑
1.如果cur变黑
违反了"任一结点到叶子结点的路径上,黑色结点的数量相同"
13→17→25→27→NIL,一共3个黑色结点
13→17→15→插入的节点→NIL,一共4个黑色结点
2.如果parent变黑
此时必须把uncle变黑且把grandparent变红才能不违反"任一结点到叶子结点的路径上,黑色结点的数量相同",保持黑色结点的平衡,即局部的子树里面红黑结点的数量不变,且连续的红节点问题暂时解决了
解决方法: parent和uncle都变黑,grandparent变红
但仍然违反"不会存在连续的红色结点",需要继续向上调整
1. grandparent没有父结点,就是根,grandparent变黑即可,这样满足"根结点以及叶子结点是黑色的"
2. grandparent有父结点,父亲是黑色,相当于"插入结点的父结点是黑色"的情况,此时结束调整
3. grandparent有父结点,父亲是红色,和刚才是类似问题处理→更新4个指针的位置,继续调整
先移动指针:
cur先移动到grandparent的位置,那么就可以定位出parent、grandparent、uncle指向的节点
解决方法: parent和uncle都变黑,grandparent变红(即"反色":parent、uncle、grandparent变成与自身颜色相反的颜色)
发现grandparent没有父结点,就是根,那么grandparent变黑即可:
调整完的结果:每条路径都增加了一个黑色结点
2.如果uncle不存在
在22的右侧插入新结点
违反"不会存在连续的红色结点",而且单纯变色无法解决问题:
假设将parent变黑,grandparent变红:
违反"不会存在连续的红色结点",继续向上处理:
违反"任一结点到叶子结点的路径上,黑色结点的数量相同",所以单纯变色无法解决问题,需要旋转
25的左子树高于右子树,需要右旋来降低左子树高度,提升右子树高度
cur指向结点的值介于17~22之间,那么有:
违反"不会存在连续的红色结点",将22染成黑色,25染成红色后,满足红黑树的所有性质
3.如果uncle存在且为黑色
下图画框的4个位置任意插入结点,向上调整时,都为使uncle存在且为黑
例如以下这种情况:
第一次调整:如果uncle存在且为红色,更改颜色+调整4个指针后:
此时违反"不会存在连续的红色结点",单纯染色无法解决问题,需要旋转
以grandparent为旋转点进行左旋:
再变色:
会发现两次调整时parent指向的结点的颜色都要变黑,如果uncle无法和父亲一起变黑,就要考虑旋转
总结
1. uncle结点存在且为红,变色 + 继续往上更新(不需要旋转)
2. uncle结点不存在或uncle存在且为黑,先旋转再变色,然后结束调整
分析抽象图
先约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
情况1: cur为红,p为红,g为黑,u存在且为红
注:1. 上图看到的以g为根节点的树可能是一棵完整的树,也可能是一棵子树 2.不讨论a、b、c、d、e子树的高度,没有意义
出现连续的红节点(p和cur),需要变色(p和u都变黑,g变红) + 继续往上更新(不需要旋转)
特别提醒:如果g是根节点,将g变黑; 如果g不是根节点,继续调整,保持g为红不变
如果g是根节点,将g变黑
如果g不是根节点,继续向上调整,将g改成cur,剩下的g、p、u依次对应即可
情况2: cur为红,p为红,g为黑,u存在且为黑
同理,1. 上图看到的以g为根节点的树可能是一棵完整的树,也可能是一棵子树 2.不讨论a、b、c、d、e子树的高度,没有意义
出现连续的红节点(p和cur),需要变色(p变黑,g变红) + 旋转(四种方式),其实反过来也可以,但不需要继续往上更新
注: 1. u本身就为黑,不需要变色
2. 旋转的四种方式参见CC40.【C++ Cont】二叉搜索树和平衡二叉树文章
情况3: cur为红,p为红,g为黑,u不存在
操作方法和情况2一样,不再赘述
代码
出现连续的红节点(cur和parent都为红,前提是parent存在),需要调整
框架:
//条件不能颠倒顺序,因为短路运算
//不用判断cur->_col是否为RED,因为默认插入的结点为红色
while (parent && parent->_col == RED)
{
//调整
}写while循环的内部代码:
有了cur和parent,可以得出grandparent和uncle
if (parent == grandparent->_left)
{
node* uncle = grandparent->_right;
//......
}
else
{
node* uncle = grandparent->_left;
//......
}写入3种情况:
while (parent && parent->_col == RED)
{
node* grandparent = parent->_parent;
//讨论uncle是左节点还是右节点
if (parent == grandparent->_left)
{
node* uncle = grandparent->_right;
//uncle存在且为红
if (uncle && uncle->_col == RED)
{
//变色(parent和uncle都变黑, grandparent变红)
parent->_col = uncle->_col = BLACK;
//由于进入循环的条件满足parent不为空,因此grandparent一定不是根节点
grandparent->_col = RED;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
else//uncle不存在或存在且为黑
{
if (cur == parent->_left)
{
//旋转前示意图:
// ......
// grandparent
// / \
// parent uncle(可能不存在)
// /
// cur
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//cur == parent->_right
{
//旋转前示意图:
// ......
// grandparent
// / \
// parent uncle(可能不存在)
// \
// cur
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;//停止调整
}
}
else
{
node* uncle = grandparent->_left;
//uncle存在且为红
if (uncle && uncle->_col == RED)
{
//变色(parent和uncle都变黑, grandparent变红)
parent->_col = uncle->_col = BLACK;
//由于进入循环的条件满足parent不为空,因此grandparent一定不是根节点
grandparent->_col = RED;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
else//uncle不存在或存在且为黑
{
if (cur == parent->_right)
{
//旋转前示意图:
// ......
// grandparent
// / \
// parent uncle(可能不存在)
// /
// cur
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//cur == parent->_right
{
//旋转前示意图:
// ......
// grandparent
// / \
// uncle(可能不存在) parent
// \
// cur
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
//不用判断parent有没有父节点,统一将_root变为黑即可
_root->_col = BLACK;
}
}注: 其中RotateR和RotateL函数借用了CD76.【C++ Dev】AVL的模拟实现(1) 以左单旋为切口,分析旋转规律和CD77.【C++ Dev】AVL的模拟实现(2) 继续编写插入函数文章的代码
节点的构造函数:
rbtree_node(const pair<K, V>& kv)
:_pack(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}测试代码
#include "rbtree.h"
#include <utility>
int main()
{
rbtree<int, nullptr_t> rbt;
for (int i = 0; i < 10; i++)
rbt.insert(make_pair(i, nullptr));
}运行结果:退出代码为0
退出代码为0不代表插入没有问题,下篇文章将讲解如何判断二叉搜索树是否是红黑树
4.附: 红黑树的插入动图
以升序插入构建红黑树:
以降序插入构建红黑树:
随机插入构建红黑树:
5.其他说明
注: 红黑树的删除不做说明,可参考《算法导论》或者《STL源码剖析》
6.附:红黑树可视化网站
扫一扫
1218
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
