目录

前言

一、红黑树概念

二、红黑树的性质

三、红黑树节点定义

四、红黑树的插入

1. 按照二叉搜索树的规则插入新节点

2. 根据红黑树的性质调整树​​​​​​​

附录:红黑树实现参考代码​​​​​​​


前言

AVL树虽然解决了有序数列插入时二叉树退化的问题,但因AVL树的高度差要求严格导致数据变动时树的旋转频繁,一定程度上降低了运行效率。

为了降低运行效率降低程度,就有了红黑树。


一、红黑树概念

红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

二、红黑树的性质

红黑树满足以下性质:

  • 每个结点不是红色就是黑色
  • 根节点是黑色的
  • 如果一个节点是红色的,则它的两个孩子结点是黑色的
  • 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
  • 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

三、红黑树节点定义

enum Color
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _parent;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	std::pair<K, V> _kv;
	Color _color;

	RBTreeNode(const std::pair<K, V>& kv = std::pair<K, V>(), Color color = RED)
		:_parent(nullptr)
		,_left(nullptr)
		,_right(nullptr)
		,_kv(kv)
		,_color(color)
	{}
};

四、红黑树的插入

红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:

1. 按照二叉搜索树的规则插入新节点

2. 根据红黑树的性质调整树

因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:

约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点

  • cur为红,p为红,g为黑,u存在且为红

直接将p、u节点变黑,g节点变红即可。

如果g的parent为红,则需要继续向上调整。

  • cur为红,p为红,g为黑,u不存在/u存在且为黑 

p为g的左孩子,cur为p的左孩子,则进行右单旋转;

相反, p为g的右孩子,cur为p的右孩子,则进行左单旋转

p、g变色--p变黑,g变红

  • cur为红,p为红,g为黑,u不存在/u存在且为黑

 p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;

相反, p为g的右孩子,cur为p的左孩子,则针对p做右单旋转

转换成了情况2

附录:红黑树实现参考代码

RBTree · 梁羽赫/cpp_advanced - 码云 - 开源中国 (gitee.com)icon-default.png?t=N7T8https://gitee.com/yuhe-liang/cpp_advanced/tree/master/RBTree

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部