【C++进阶06】红黑树图文详解及C++模拟实现红黑树

一、红黑树的概念及性质

1.1 红黑树的概念

AVL树用平衡因子让树达到高度平衡
红黑树可以认为是AVL树的改良
通过给每个节点标记颜色让树接近平衡
以减少树在插入节点的旋转
在每个结点新增一个存储位表示结点颜色
可以是Red或Black
通过对任何一条从根到叶子的路径上
各个结点着色方式的限制
红黑树确保没有一条路径会比其他路径长出
俩倍，因而是接近平衡的

1.2 红黑树的性质

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

为啥满足上面性质的红黑树就能保证
其最长路径节点个数不会超过最短路径
节点个数的两倍？

由性质3可得出不能出现连续红色节点
由性质4可得出每条路径有相同黑色节点数量

极限情况下
最短路径：全黑
最长路径：一黑一红

由此可得出
最长路径不会超过最短路径的两倍

1.3 为什么更常用红黑树而不是AVL树？

AVL树： 是一颗高度平衡的二叉树
查找效率：$O(logN)$
但是这样的效率是在插入元素时
经常性的旋转换来的

红黑树： 是一颗接近平衡的二叉树
假设全部黑节点有N个
整棵树的节点数量：[N, 2N]之间
最短路径长度：$O(logN)$
最长路径长度：$O(2logN)$
查找效率：$O(2logN)$

10亿数据AVL树最多查找30次
红黑树最多也就查找60次
对于cpu的运行速度来说几乎可以忽略不计
但红黑树的规则相对于AVL树没那么严格
在插入元素时，不会经常旋转
所以综合而言红黑树更胜一筹

如图： 对于AVL树必定旋转
红黑树则不用

二、红黑树模拟实现的基本框架

2.1 红黑树节点的定义

跟AVL树一样
只是AVL树采用平衡因子
让树达到平衡
而红黑树对节点进行颜色标记
让树达到平衡
定义一个枚举表示节点颜色

enum colour
{
	RED,
	BLACK,
};

template <class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent; // 三叉链
	pair<K, V> _kv;
	colour _col;

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

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

2.2 红黑树的插入

还是和AVL树一样

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		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->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}

		// new的节点的parent还指向空
		cur->_parent = parent;

		// 插入黑色节点还是红色节点？

		return true;
	}

插入走到这里如果是AVL树
此时需要更新平衡因子

红黑树采用的是标记节点颜色
让树达到平衡
需要考虑的是插入什么颜色的节点？

1. 插入黑色节点
   会违反规则4，影响到每条路径
2. 插入红色节点
   如果插入节点的父节点也是红色节点
   则会违反规则3影响当前局部节点

很明显插入红色节点更划算
所有插入的节点都默认是红色
如果违反红黑树的规则，再进行调整

三、对插入节点调整的解析

如果插入节点的父节点为黑
则无需处理
如果为红，则分为三种情况

情况一：

cur为红，p为红，g为黑，u存在且为红

cur为当前节点，p为父节点
g为祖父节点，u为叔叔节点

把p和u变黑，g变红

如果grandfather的parent也为红
把grandfather改为cur
继续按刚才的步骤往后迭代

如果grandfather为根节点
把grandfather改为黑色
颜色调整结束

情况二：

cur为红，p为红，g为黑
u不存在或u存在且为黑

此树可能是完整树也可能是子树
u节点不存在

p为g的左孩子，cur为p的左孩子
则进行右单旋转
相反
p为g的右孩子，cur为p的右孩子
则进行左单旋转
p、g变色–p变黑，g变红

下图则是u节点存在的情况

c为下面4种情况的
任意一种包含一个黑节点的红黑树
d和e可能是空或者一个红节点

插入新节点，更新完后
继续往后更新
就是情况二的u存在的情况

情况三：

cur为红，p为红，g为黑
u不存在或u存在且为黑

跟情况二完全类似
只是情况三为双旋
情况二是单旋

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

则转换成了情况2
此图为u不存在
u存在参考情况二

四、红黑树插入代码的全部实现

详解都在代码注释
各位友友们请耐心看完

bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	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->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}

	// new的节点的parent还指向空
	cur->_parent = parent;

	// 如果新插入节点破坏了红黑树规则
	// 则更新节点颜色
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		if (grandfather->_left == parent)
		{
			Node* uncle = grandfather->_right;
			// 情况1：u存在且为红，变色处理，并继续往上处理
			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else // 情况2+3：u不存在或者u存在且为黑，旋转+处理
			{
				// 如果插入节点在父节点的左，c、p、g呈一条斜线
				//     g
				//   p   u
				// c
				if (parent->_left == cur)
				{
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED; 
				}
				else
				{
					// 插入节点在父节点的右，c、p、g呈一条折线
					//      g
					//   p      u
					//     c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					// parent->_col = RED; // 父亲本就是红，变一下双重保险
					grandfather->_col = RED;
				}

				break;
			}
		}
		else // (grandfather->_right == parent)
		{
			Node* uncle = grandfather->_left;
			// 情况1：u存在且为红，变色处理，并继续往上处理
			if (uncle && uncle->_col == RED)
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else // 情况2+3：u不存在或者u存在且为黑，旋转+处理
			{
				//   g
				// u    p
				//         c
				if (parent->_right == cur)
				{
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				else
				{
					//   g
					// u     p
					//     c
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
	}

	_root->_col = BLACK; // 做个双保险，无论那种情况把根都变成黑的
	return true;
}

????????
本篇博客完，感谢阅读🌹
如有错误之处可评论指出
博主会耐心听取每条意见
????????