【C++】红黑树

MarkDown输出x的平方和log以2为底的方法：
1、x²——英文输入法，输入x 加 ^ 加 2 加 ^
2、log₂N——英文输入法，输入log 加 ~ 加 2 加 ~ 加 N

---

1、红黑树概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的

也就是说：红黑树中，最长的路径不超过最短路径的2倍

下面是红黑树的样例：

2、红黑树的性质

通过上面红黑树的概念加图片我们可以得到几个红黑树的性质（参考上面图片来观察）：

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

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

最长路径：一黑一红相间的路径
最短路径：一条路径节点全黑

这样一看，最长的路径节点个数不会超过最短路径节点个数的两倍

极端情况下的近似平衡：

最优情况：左右平衡。路径全黑或者每一条路径都是一黑一红相间的路径。满二叉树
最差情况：左右不平衡。左子树全黑，右子树一黑一红

全黑路径长度是h
2^h -1 + 红节点 = N（这里红节点远小于黑节点）
最短路径：log₂N
最长路径：2*log₂N

如果N是10亿，那么最短路径为30，最长路径为60，对于计算机来说30和60是在同一个量级的，所以差别并不大

所以：红黑树并没有AVL树那么严格，看起来就没有AVL树那么平衡，查找的效率也就没有AVL树那么高效（对比于AVL树来说）
但是AVL树高效的查找，是依赖于AVL严格的平衡，严格的平衡是通过不断旋转得到的，而旋转消耗是比较大的。而红黑树不那么平衡就表明红黑树没有AVL那么多次的旋转操作，消耗也就比较小了

3、红黑树的实现

3-1、红黑树节点的定义

enum colors
{
	RED,
	BLOCK,
};
template <class K, class V>
class RBTreeNode
{
public:
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;//左节点
	RBTreeNode<K, V>* _right;//右节点
	RBTreeNode<K, V>* _parent;//父节点

	colors _col;

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

3-2、红黑树的插入

红黑树的插入和AVL树的插入前面大差不差，就算少了平衡因子，多了颜色

template <class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//前面与AVL树一样
		{
			_root = new Node(kv);
			_root->_col = BLOCK;//根节点是黑色的
			return true;
		}
		Node* parent = nullptr;//parent是cur的父节点
		Node* cur = _root;//cur往下走
		while (cur)
		{
			if (cur->_kv.first > kv.first)//我比你小，往左找
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)//我比你大，往右找
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;//不存在找到，因为AVL树不允许有重复值
			}
		}
		走到这里就表示找到我们要插入kv值的正确位置了
		cur = new Node(kv);

		cur->_col = RED;//这里插入一个节点，颜色设置为红色！！！
		//插入一个节点，设置为红色。我们就违背了红黑树规则3（红黑树的性质那里）
		//插入一个节点，设置为黑色。我们就违背了红黑树规则4
		// 
		//但是，我们可以仔细观察，发现违背规则3然后对红黑树进行修改，比违背规则4进行修改简单的多！！！
		//而且插入设置为红色不一定破环了规则3，就算违背规则3破坏的是一条路径，
		//而规则4是整棵树的全部路径。所以这里设置节点为红色比较容易控制

		if (parent->_kv.first < kv.first)//如果new的节点比父节点大，那么父节点的右指针指向new节点
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else//如果new的节点比父节点小，那么父节点的左指针指向new节点
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//....开始插入了
		return true;
	}
private:
	Node* _root = nullptr;
};

我们先来看看下面的插入操作有哪些情况：

检测新节点插入后，红黑树的性质是否造到破坏

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：
约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

3-2-1、情况一

情况一: cur为红，p为红，g为黑，u存在且为红
这里g一定为黑，因为如果g为红，那么p为红的时候我们就要对p进行修改了，而cur是我们新增的红，
所以我们这个时候破坏了规则，开始对cur，p，g和u节点进行变色

cur和p均为红，违反了性质三，此处能否将p直接改为黑？

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

我们再来看看abcde（abcde可能有这无数层，这里我们就只是举个样例）：
1、abcde为空：

这个时候就和上面的处理情况一样了

2、abcde不为空

a、b为红：

c、d、e情况（后面还可能带着节点）：

这个时候在a、b下面新增节点：

这个时候就也变得和上面情况一样的，直接将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

情况一变情况一

当然，我们把g当成cur向上调整，或者新插入红节点，并不就一定是上面的情况，比如cur为，u不为红。这个时候我们就要继续找其他的处理方法了！

3-2-2、情况二

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

1、u不存在，那么cur就算新增节点

这个时候：

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

2、u存在且u为黑，cur不是新增
这个时候cur不是新增节点了，因为p为红，u为黑，路径的黑节点数据个数不一样了！

情况一变情况二
这个时候就算上面的情况1了，我们进行处理：

注意：u存在且为黑，那么p和cur一定是由情况一变过来，p和cur为红的，因为如果开始p和cur为红，路径的黑节点数据个数不一样了

这个时候，我们就和处理abcde都不存在的方法一样了，p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转p、g变色–p变黑，g变红

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

3-2-3、情况三

情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑

1、u不存在，cur是新增

如果cur新增在p左边，那么就变成了情况二
如果新增在p的右变，这个时候就要进行双旋
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
这个时候就旋转成为了情况二

在进行第二次旋转

2、u存在且为黑，cur不是新增

情况一变情况三

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

二次旋转

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，则转换成了情况2

针对每种情况进行相应的处理即可

以上就是我们对红黑树的插入情况的分析，就算从AVL树的旋转加调整平衡因子，变成了旋转加变色

继续上面的代码：

while (parent && parent->_col == RED)//父亲颜色为黑就不需要处理了，颜色为红就要处理
		{
			Node* gf = parent->_parent;//
			if (parent == gf->_left)
			{
				Node* uncle = gf->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLOCK;
					gf->_col = RED;
					cur = gf;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						//新增cur在父亲的左，右单旋
						RotateR(gf);
						parent->_col = BLOCK;
						gf->_col = RED;
					}
					else
					{
						//情况三，双旋
						RotateL(parent);
						RotateR(gf);
						cur->_col = BLOCK;
						gf->_col = RED;
					}
					break;//这里要break，因为这一层已经处理完了，上面有问题是上面的事，与这一层无关
				}
			}
			else
			{
				Node* uncle = gf->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLOCK;
					gf->_col = RED;

					cur = gf;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(gf);
						parent->_col = BLOCK;
						gf->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(gf);
						cur->_col = BLOCK;
						gf->_col = RED;
					}

					break;
				}
			}
		}
		_root->_col = BLOCK;

动态图

这里展示一下动态构建红黑树的演示图：
1、升序插入构建红黑树

2、降序插入构建红黑树

3、随机插入构建红黑树

4、右旋转

5、左旋转

4、红黑树的验证

这里我们不能直接比较最长路径和最短路径的差值，要缺点红黑树的规则全部正确才能证明该树是红黑树

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

bool Check(Node* root, int blackNum, const int ref)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (blackNum != ref)
			{
				cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续红色节点" << endl;
			return false;
		}
		if (root->_col == BLOCK)
		{
			++blackNum;
		}
		return Check(root->_left, blackNum, ref) && Check(root->_right, blackNum, ref);
	}
	bool IsBalance()判断是否为红黑树，这里的IsBalance不是递归函数
	{
		if (_root == nullptr)//这里不需要递归，所以就使用_root，不用传参
			return true;
		if (_root->_col != BLOCK)//这里判断的是整棵树的根，不是每一个根都要为黑，
								//所以我们要再写一个函数来处理
			return false;

		int ref = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLOCK)
				++ref;
			left = left->_left;
		}
		return Check(_root, 0, ref);
	}

5、红黑树的删除

与AVL树一样，我们不需要对红黑树的删除有深入的理解
所以红黑树的删除本节不做讲解，有兴趣的同学可参考：《算法导论》或者《STL源码剖析》
博客园地址

6、 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log_2 N log2​N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多

7、红黑树的应用

1. C++ STL库 – map/set、mutil_map/mutil_set
2. Java 库
3. linux内核
4. 其他一些库

8、红黑树代码

#pragma once
#include <assert.h>
#include <time.h>
using namespace std;
enum colors
{
	RED,
	BLOCK,
};
template <class K, class V>
class RBTreeNode
{
public:
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;//左节点
	RBTreeNode<K, V>* _right;//右节点
	RBTreeNode<K, V>* _parent;//父节点

	colors _col;

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

template <class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//前面与AVL树一样
		{
			_root = new Node(kv);
			_root->_col = BLOCK;//根节点是黑色的
			return true;
		}
		Node* parent = nullptr;//parent是cur的父节点
		Node* cur = _root;//cur往下走
		while (cur)
		{
			if (cur->_kv.first > kv.first)//我比你小，往左找
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)//我比你大，往右找
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;//不存在找到，因为AVL树不允许有重复值
			}
		}
		走到这里就表示找到我们要插入kv值的正确位置了
		cur = new Node(kv);

		cur->_col = RED;//这里插入一个节点，颜色设置为红色！！！
		//插入一个节点，设置为红色。我们就违背了红黑树规则3（红黑树的性质那里）
		//插入一个节点，设置为黑色。我们就违背了红黑树规则4
		// 
		//但是，我们可以仔细观察，发现违背规则3然后对红黑树进行修改，比违背规则4进行修改简单的多！！！
		//而且插入设置为红色不一定破环了规则3，就算违背规则3破坏的是一条路径，
		//而规则4是整棵树的全部路径。所以这里设置节点为红色比较容易控制

		if (parent->_kv.first < kv.first)//如果new的节点比父节点大，那么父节点的右指针指向new节点
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else//如果new的节点比父节点小，那么父节点的左指针指向new节点
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		while (parent && parent->_col == RED)//父亲颜色为黑就不需要处理了，颜色为红就要处理
		{
			Node* gf = parent->_parent;//
			if (parent == gf->_left)
			{
				Node* uncle = gf->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLOCK;
					gf->_col = RED;
					cur = gf;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						//新增cur在父亲的左，右单旋
						RotateR(gf);
						parent->_col = BLOCK;
						gf->_col = RED;
					}
					else
					{
						//情况三，双旋
						RotateL(parent);
						RotateR(gf);
						cur->_col = BLOCK;
						gf->_col = RED;
					}
					break;//这里要break，因为这一层已经处理完了，上面有问题是上面的事，与这一层无关
				}
			}
			else
			{
				Node* uncle = gf->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLOCK;
					gf->_col = RED;

					cur = gf;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(gf);
						parent->_col = BLOCK;
						gf->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(gf);
						cur->_col = BLOCK;
						gf->_col = RED;
					}

					break;
				}
			}
		}
		_root->_col = BLOCK;
		return true;
	}
	void RotateL(Node* parent)
	{
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		parent->_right = subrl;
		if (subrl)//上面的节点不可能为空，但是这里的subrl可能为空
		{
			subrl->_parent = parent;
		}
		Node* ppnode = parent->_parent;
		subr->_left = parent;
		parent->_parent = subr;
		if (ppnode == nullptr)//如果
		{
			_root = subr;
			_root->_parent = nullptr;//这里要置空
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subr;
			}
			else
			{
				ppnode->_right = subr;
			}
			subr->_parent = ppnode;
		}
	}
	void RotateR(Node* parent)
	{
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		parent->_left = sublr;
		if (sublr)
		{
			sublr->_parent = parent;
		}
		Node* ppnode = parent->_parent;
		subl->_right = parent;
		parent->_parent = subl;
		if (ppnode == nullptr)
		{
			_root = subl;
			subl->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subl;
			}
			else
			{
				ppnode->_right = subl;
			}
			subl->_parent = ppnode;
		}
	}
	void Inorder()//中序遍历
	{
		_Inorder(_root);
	}
	void _Inorder(Node* root)//中序遍历
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_Inorder(root->_right);
	}

	bool Check(Node* root, int blackNum, const int ref)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (blackNum != ref)
			{
				cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续红色节点" << endl;
			return false;
		}
		if (root->_col == BLOCK)
		{
			++blackNum;
		}
		return Check(root->_left, blackNum, ref) && Check(root->_right, blackNum, ref);
	}
	bool IsBalance()判断是否为红黑树，这里的IsBalance不是递归函数
	{
		if (_root == nullptr)//这里不需要递归，所以就使用_root，不用传参
			return true;
		if (_root->_col != BLOCK)//这里判断的是整棵树的根，不是每一个根都要为黑，
								//所以我们要再写一个函数来处理
			return false;

		int ref = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLOCK)
				++ref;
			left = left->_left;
		}
		return Check(_root, 0, ref);
	}
private:
	Node* _root = nullptr;
};