C++中红黑树的实现

XiaoCCCCCCCCCCCCCCC

已于 2024-10-26 15:23:06 修改

阅读量1.3k

点赞数 35

分类专栏： C++ 文章标签：数据结构 c++ 算法开发语言 stl

于 2024-10-26 15:20:45 首次发布

本文链接：https://blog.csdn.net/CSQCSQCC/article/details/143250704

版权

1.红黑树的概念

1.1红黑树的规则

1.2红黑树如何确保最长路径不超过最短路径的2倍

2.2.2情况1：叔叔节点存在且为红 -- 变色

2.2.3情况2：叔叔节点存在且为黑或者不存在 -- 旋转 + 变色

2.2.3.1情况2-1：c插入在p的左边 -- 右单旋 + 变色

2.2.3.2情况2-2：c插入在p的右边 -- 左右双旋 + 变色

1.红黑树的概念

红黑树是一颗二叉树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦(空节点)的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。

1.1红黑树的规则

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

2.根节点是黑色的。

3.如果一个节点是红色的，则它的两个孩子节点必须是黑色的，也就是说任何一条路径不会有连续的红色节点。

4.对于任意一个节点，从该节点到其所有NULL节点的简单路径上，均包含相同数量的黑色节点。

说明：《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是⿊⾊的规则。他这⾥所指的叶⼦结点不是传统的意义上的叶⼦结点，⽽是我们说的空结点，有些书籍上也把NIL叫做外部结点。

这里先看看几颗红黑树：

1.2红黑树如何确保最长路径不超过最短路径的2倍

由规则4可知，从根到NULL节点的每条路径上都有相同数量的黑色节点，极端情况下，最短路径就是全为黑色节点的路径，假设最短路径长度为bh(black height)。

由规则2和规则3可知，任何一条路径不会有连续的红色节点，极端情况下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为2*bh。

综合红⿊树的4点规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= x <= 2*bh。

1.3红黑树的效率

假设N是红⿊树树中结点数量，h最短路径的⻓度，那么 $2^{h}-1 <= N <= 2^{2*h}-1$ 由此推出h ≈ logN ，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径 2 ∗ logN ，那么时间复杂度还是 $O(logN)$ 。

红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格。

2.红黑树的实现

2.1红黑树的结构

//枚举表示颜色
enum color
{
	RED,
	BLACK
};

//默认按key/value结构实现
template <class K, class V>
class RBTreeNode
{
	//这里更新控制平衡也要加入parent指针
	pair<K, V> _kv;
	RBTreeNode _left;
	RBTreeNode _right;
	RBTreeNode _parent;
	color _col;	//每个节点增加一个表示颜色的成员

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
	{}
};

template <class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	//...
private:
	Node _root = nullptr;
};

2.2红黑树的插入

2.2.1红黑树插入一个值的大概过程

1.插入一个值按二叉搜索树的规则进行插入(默认新插入的节点为红色)，插入后观察是否符合红黑树的4条规则。

2.如果是对空树进行插入，新增节点为根节点，将颜色改为黑色；如果是对非空树插入，新增节点必须为红色节点，如果为黑色节点则破环了规则4，规则4是很难维护的。

3.非空树插入后，新增结点必须红⾊结点，如果⽗亲结点是⿊⾊的，则没有违反任何规则，插⼊结束。

4.⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是红⾊的，则违反规则3。进⼀步分析，c是红⾊，p为红，g必为⿊，这三个颜⾊都固定了，关键的变化看u的情况，需要根据u分为以下⼏种情况分别处理。

说明：下图中假设我们把新增结点标识为c (cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为
g(grandfather)，p的兄弟标识为u(uncle)。

2.2.2情况1：叔叔节点存在且为红 -- 变色

c为红，p为红，g为⿊，u存在且为红，则将p和u变⿊，g变红。在把g当做新的c，继续往上更新。

分析：因为p和u都是红色，g是黑色，把p和u变黑，左右子树路径各增加一个黑色节点，g变红，相当于保持g所在子树的黑色节点数量不变，同时解决了c和p连续红色节点的问题。需要继续往上更新是因为g是红色，如果g的父亲也是红色，那么还需要继续处理；如果g的父亲是黑色，则处理结束；如果g的父亲就是整棵树的根，再把g变回黑色。

情况1只变⾊，不旋转。所以⽆论c是p的左还是右，p是g的左还是右，都是上⾯的变⾊处理⽅式。