【数据结构】红黑树

目录

前言

一、红黑树概念

二、红黑树的性质

三、红黑树节点定义

四、红黑树的插入

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)https://gitee.com/yuhe-liang/cpp_advanced/tree/master/RBTree