【C++高阶(四)】红黑树深度剖析–手撕红黑树!

💓博主CSDN主页:杭电码农-NEO💓
 
⏩专栏分类:C++从入门到精通⏪
 
🚚代码仓库:NEO的学习日记🚚
 
🌹关注我🫵带你学习C++
  🔝🔝

红黑树

• 1. 前言
• 2. 红黑树的概念以及性质
• 3. 红黑树为什么更实用?
• 4. 红黑树模拟实现代码框架
• 5. 红黑树的插入操作初步分析
• 6. 红黑树的插入操作详解(一)
• 7. 红黑树的插入操作详解(二)
• 8. 红黑树的插入代码实现
• 9. 总结以及拓展

1. 前言

如果说发明AVL树的人是天才,那么
发明红黑树的人可以称为天才中的
精英!为什么AVL树这么强大但是没啥
人用呢?就是因为红黑树比你还好!

本章重点:

本篇文章着重讲解红黑树的概念以及
性质,以及为了维护红黑树这种性质而
做的限制条件.最后模拟实现红黑树的
插入,带大家熟悉变色和旋转规则!

2. 红黑树的概念以及性质

红黑树的概念:

• 首先红黑树是一颗二叉搜索树
• 每个节点都有颜色,红色或黑色
• 最长路径最多是最短路径的二倍

红黑树的性质:

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的
   则它的两个孩子结点是黑色的
4. 每条路径上的黑色节点数相同
5. 每个叶子结点都是黑色的
   (此处的叶子结点指的是空结点)

为啥满足了以上性质的红黑树就一定
能做到最长路径最多是最短路径的二倍?
下面我画一个极限情况来分析一下!

3. 红黑树为什么更实用?

现在将AVL数和红黑树做一个对比:

• AVL树阐析:

AVL树是一颗高度平衡二叉树,
它的高度差不能大于1,所以AVL
树的查找是妥妥的O(logn),但是
由于AVL树严格的标准,使得在使用
AVL树时会经常旋转,反而增加了时间!

• 红黑树阐析:

红黑树是一颗接近平衡的二叉树
它最长路径最多是最短路径的二倍
所以查找的效率是:logn~2logn,
然而2logn和logn是一个量级的,
并且红黑树的规则没有这么严格,
不会涉及到更多旋转和变色!

综上所述,红黑树的效率虽然比
AVL树差一点,但是总体来说红黑树胜!

4. 红黑树模拟实现代码框架

首先,每个节点都要存一个颜色,
这里我们使用枚举enum来实现
并且和AVL一样也是三叉链!
请看代码:

enum Colour
{
	RED,
    BLACK
};
template<class K,class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		,_col(RED)
	{}
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv; 
	Colour _col;
};

template<class K, class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
private:
	Node* _root = nullptr;
};

有了代码框架后,现在来看看插入

5. 红黑树的插入操作初步分析

和AVL树很相似,红黑树的插入
也是分为两步走:

1. 按照二叉搜索树的规则插入值
2. 插入后根据颜色或高度做旋转或变色

众所周知啊,第一步很简单
甚至可以将之前的代码抄过来:

bool insert(const pair<K, V>& kv)//第一步:按照二叉搜索树的方式插入值
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	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->_right = cur;
	else
		parent->_left = cur;
	//此时new出来的节点的parent还指向空
	cur->_parent = parent;
	///前面的过程和AVL树一致
}

走到这步后,有个问题,新插入的节点
是选择插入红色还是黑色?

对于这个问题,我们要思考两个点,
一是如果插入的是黑色节点,我们
可能会打破哪个规则?如果是插入
红色节点又可能会打破哪个规则?

• 插入黑色节点,打破规则四,很难办
因为每个路径检查起来很难!

• 插入红色节点,打破规则三,比打破
四要好一些,因为只用看父亲是否为红

综上所述,插入红色更优!
换句话说,你犯错肯定宁愿犯轻一点
的错误被妈妈打一顿,也不愿意犯很重
的错直接被家族除名了对吧[doge]

6. 红黑树的插入操作详解(一)

如果插入的节点的父亲是黑色节点,
那么正是我们想看见的,不用管它了!

那么如果插入的节点的父亲是红色呢?
很明显,这违反了规则三,有连续的红色
节点,所以此时需要做处理了!

先来看一个最简单的情况:

其实红黑树插入节点后的变色和
旋转规则主要是看叔叔,叔叔的情况
不同,那么对应的处理手段就不同,这里
只通过简单变色手段就可以满足规则了!
并且在上图中,将爷爷变成红色后可能会
出现问题,因为爷爷的父亲不知道是红色
还是黑色,所以要不断向上做判断

若不向上更新,可能会有这种情况:

7. 红黑树的插入操作详解(二)

当讲解完最简单的情况后,还剩下两种
情况,这两种情况内部又可细分出几种
情况,请同学们耐心学习!

情况二:cur为红.p为红.g为黑.u不存在/为黑
(并且cur和p都是左或右)

p为g的左孩子,cur为p的左孩子,则右单旋
p为g的右孩子,cur为p的右孩子,则左单旋
p,g变色—p变黑，g变红

情况三:cur为红.p为红.g为黑.u不存在/为黑
(并且若p是g的左,cur就是p的右)

p为g的左孩子,cur为p的右孩子,则做左单旋
p为g的右孩子,cur为p的左孩子,则做右单旋
则转换成了情况二

至此,红黑树的插入的所有情况都
讲解完毕,接下来就是代码实现了!

8. 红黑树的插入代码实现

在整个大情况分类中,可以归为两类
一是叔叔为红色,二是叔叔为黑色或者
叔叔不存在,我们围绕着这两个大方向写!

//走到这一步后,就已经找到cur和parent了!
while (parent && parent->_col == RED)//当parent为黑就不用往上更新了
{
	if (parent == _root)
	{
		_root->_col = BLACK;
		break;
	}
	Node* grandf = parent->_parent;
	assert(grandf);
	assert(grandf->_col == BLACK);
	Node* uncle = nullptr;
	if (parent == grandf->_left)//判断叔叔在par的左还是右
		uncle = grandf->_right;
	else uncle = grandf->_left;
	if (uncle == nullptr || uncle->_col == BLACK)//uncle为空或为黑有四种情况来变色＋旋转
	{
		if (parent == grandf->_left && cur == parent->_left)//左左->右旋＋变色
		{
			RotateR(grandf);
			parent->_col = BLACK;
			grandf->_col = RED;
			break;
		}
		else if (parent == grandf->_right && cur == parent->_right)//右右->左旋+变色
		{
			RotateL(grandf);
			parent->_col = BLACK;
			grandf->_col = RED;
			break;
		}
		else if (parent == grandf->_left && cur == parent->_right)//左右->先左旋再右旋再变色
		{
			RotateL(parent);
			RotateR(grandf);
			cur->_col = BLACK;
			grandf->_col = RED;
			break;
		}
		else if (parent == grandf->_right && cur == parent->_left)//右左->先右旋再左旋再变色
		{
			RotateR(parent);
			RotateL(grandf);
			cur->_col = BLACK;
			grandf->_col = RED;
			break;
		}
	}
	else if (uncle && uncle->_col == RED)//叔叔为红,直接变色,不旋转
	{
		parent->_col = BLACK;
		uncle->_col = BLACK;
		grandf->_col = RED;
		cur = grandf;
		parent = cur->_parent;//将parent更新后往上传!
	}
	_root->_col = BLACK;
}

可以发现一个问题,只要是叔叔的颜色
是黑色或叔叔不存在的情况下,执行完
旋转＋变色后都直接break了,这是因为
在这种情况下,父亲节点都被变成了黑色,
也就没必要继续往上了!并且在红黑树的
左旋和右旋中,代码其实和AVL树的旋转是
一模一样的,所以直接copy一份就行了!

若你不清楚旋转的代码,请看这篇文章:

AVL树模拟实现!

9. 总结以及拓展

AVL树和红黑树的代码实现都只讲解
了插入操作,因为删除操作太复杂了,
并且就算实现了删除操作也没有太大
的实际意义,所以只需要了解插入即可!

并不是需要你真正的会手撕!

拓展阅读:

红黑树的删除图解