一、红黑树的概念及性质
1.1 红黑树的概念
AVL树用平衡因子让树达到高度平衡
红黑树可以认为是AVL树的改良
通过给每个节点标记颜色让树接近平衡
以减少树在插入节点的旋转
在每个结点新增一个存储位表示结点颜色
可以是Red或Black
通过对任何一条从根到叶子的路径上
各个结点着色方式的限制
红黑树确保没有一条路径会比其他路径长出
俩倍,因而是接近平衡的
1.2 红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
-
如果一个节点是红色的
则它的两个孩子结点是黑色的
-
对于每个结点
从该结点到其所有后代叶结点的简单路径上
均包含相同数目的黑色结点
- 每个叶子结点都是黑色的
(此处的叶子结点指的是空结点)
为啥满足上面性质的红黑树就能保证
其最长路径节点个数不会超过最短路径
节点个数的两倍?
由性质3可得出不能出现连续红色节点
由性质4可得出每条路径有相同黑色节点数量
极限情况下最短路径:
全黑最长路径:
一黑一红
由此可得出
最长路径不会超过最短路径的两倍
1.3 为什么更常用红黑树而不是AVL树?
AVL树: 是一颗高度平衡的二叉树
查找效率:
O
(
l
o
g
N
)
O(logN)
O(logN)
但是这样的效率是在插入元素时
经常性的旋转换来的
红黑树: 是一颗接近平衡的二叉树
假设全部黑节点有N个
整棵树的节点数量:[N, 2N]之间
最短路径长度:
O
(
l
o
g
N
)
O(logN)
O(logN)
最长路径长度:
O
(
2
l
o
g
N
)
O(2logN)
O(2logN)
查找效率:
O
(
2
l
o
g
N
)
O(2logN)
O(2logN)
10亿数据AVL树最多查找30次
红黑树最多也就查找60次
对于cpu的运行速度来说几乎可以忽略不计
但红黑树的规则相对于AVL树没那么严格
在插入元素时,不会经常旋转
所以综合而言红黑树更胜一筹
如图: 对于AVL树必定旋转
红黑树则不用
二、红黑树模拟实现的基本框架
2.1 红黑树节点的定义
跟AVL树一样
只是AVL树采用平衡因子
让树达到平衡
而红黑树对节点进行颜色标记
让树达到平衡
定义一个枚举表示节点颜色
enum colour
{
RED,
BLACK,
};
template <class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent; // 三叉链
pair<K, V> _kv;
colour _col;
RBTreeNode(const pair<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
template <class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};
2.2 红黑树的插入
还是和AVL树一样
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
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);
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
// new的节点的parent还指向空
cur->_parent = parent;
// 插入黑色节点还是红色节点?
return true;
}
插入走到这里如果是AVL树
此时需要更新平衡因子
红黑树采用的是标记节点颜色
让树达到平衡
需要考虑的是插入什么颜色的节点?
-
插入黑色节点
会违反规则4,影响到每条路径 -
插入红色节点
如果插入节点的父节点也是红色节点
则会违反规则3影响当前局部节点
很明显插入红色节点更划算
所有插入的节点都默认是红色
如果违反红黑树的规则,再进行调整
三、对插入节点调整的解析
如果插入节点的父节点为黑
则无需处理
如果为红,则分为三种情况
情况一:
cur为红,p为红,g为黑,u存在且为红
cur为当前节点,p为父节点
g为祖父节点,u为叔叔节点
把p和u变黑,g变红
如果grandfather的parent也为红
把grandfather改为cur
继续按刚才的步骤往后迭代
如果grandfather为根节点
把grandfather改为黑色
颜色调整结束
情况二:
cur为红,p为红,g为黑
u不存在或u存在且为黑
此树可能是完整树也可能是子树
u节点不存在
p为g的左孩子,cur为p的左孩子
则进行右单旋转
相反
p为g的右孩子,cur为p的右孩子
则进行左单旋转
p、g变色–p变黑,g变红
下图则是u节点存在的情况
c为下面4种情况的
任意一种包含一个黑节点的红黑树
d和e可能是空或者一个红节点
插入新节点,更新完后
继续往后更新
就是情况二的u存在的情况
情况三:
cur为红,p为红,g为黑
u不存在或u存在且为黑
跟情况二完全类似
只是情况三为双旋
情况二是单旋
p为g的左孩子,cur为p的右孩子
则针对p做左单旋转
相反
p为g的右孩子,cur为p的左孩子
则针对p做右单旋转
则转换成了情况2
此图为u不存在
u存在参考情况二
四、红黑树插入代码的全部实现
详解都在代码注释
各位友友们请耐心看完
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
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);
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
// new的节点的parent还指向空
cur->_parent = parent;
// 如果新插入节点破坏了红黑树规则
// 则更新节点颜色
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// 情况1:u存在且为红,变色处理,并继续往上处理
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else // 情况2+3:u不存在或者u存在且为黑,旋转+处理
{
// 如果插入节点在父节点的左,c、p、g呈一条斜线
// g
// p u
// c
if (parent->_left == cur)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 插入节点在父节点的右,c、p、g呈一条折线
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
// parent->_col = RED; // 父亲本就是红,变一下双重保险
grandfather->_col = RED;
}
break;
}
}
else // (grandfather->_right == parent)
{
Node* uncle = grandfather->_left;
// 情况1:u存在且为红,变色处理,并继续往上处理
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else // 情况2+3:u不存在或者u存在且为黑,旋转+处理
{
// g
// u p
// c
if (parent->_right == cur)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK; // 做个双保险,无论那种情况把根都变成黑的
return true;
}
五、红黑树全部代码模拟实现
gitee链接文章来源:https://www.toymoban.com/news/detail-812036.html
✨✨✨✨✨✨✨✨
本篇博客完,感谢阅读🌹
如有错误之处可评论指出
博主会耐心听取每条意见
✨✨✨✨✨✨✨✨文章来源地址https://www.toymoban.com/news/detail-812036.html
到了这里,关于【C++进阶06】红黑树图文详解及C++模拟实现红黑树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!