数据结构：红黑树的模拟实现_红黑树模拟

作者：繁依Fanyi0 | 2024-05-19 16:23:56

踩

红黑树模拟

1、什么是红黑树？

1、cur为红，p为红，g为黑，cur存在且为红

2、cur为红，p为红，g为黑，u不存在/u存在且为黑

4、判断是否为红黑树

3、完整实现代码

1、什么是红黑树？

前面的文章我们讲解了AVL树，AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度。但是AVL树为了保持平衡要旋转来操作，在删除时有可能要一直旋转到根部，效率就会比较低下，如果数据的个数为静态的(即不会改变)，可以考虑AVL树，如果一个结构经常修改，那么红黑树是个不错的选择。

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在普通的二叉搜索树的基础上增加了一些额外的规则来确保树的高度差别不会太大，从而保持了较为稳定的性能。在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

红黑树的性质：

1、每个节点不是黑色就是红色。

2、根节点是黑色的。

3、如果一个节点是红色的，那么它的两个孩子是黑色的，也就是说，不可以有两个连续的红色节点。

4、对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点

个数的两倍？

因为不会有两个连续的红色节点，而每条路径上面的黑色节点数目都相同，所以所有节点的长度只会在：

N为每条路径黑色节点的个数，而红色节点最多也为N，所以所有路径的长度只会在N~2N内。

2、红黑树的相关操作与实现

红黑树与AVL树都是二叉搜索树，在插入操作时也使用了左旋与右旋，这些在AVL树的文章中也做过讲解，可以参考这篇文章：数据结构：AVL树

1、节点定义


enum Color
{
	RED,
	BLACK
};
template<class valuetype>
struct RBTreeNode
{
	RBTreeNode(const valuetype& data = valuetype(), Color color = RED)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _color(color)
	{
 
	}
 
	RBTreeNode<valuetype>* _left;
	RBTreeNode<valuetype>* _right;
	RBTreeNode<valuetype>* _parent;
	valuetype _data;
	Color _color;
 
 
};