【数据结构高阶】红黑树

目录

一、红黑树的概念

二、红黑树的性质

2.1 红黑树与AVL树的比较

三、红黑树的实现

3.1 红黑树节点的定义

3.2 数据的插入

3.2.1 红黑树的调整思路

3.2.1.1?cur为红，f为红，g为黑，u存在且为红

3.2.1.2?cur为红，f为红，g为黑，u不存在/u存在且为黑

3.2.1.2.1 g、f、cur构成一条直线

3.2.1.2.2?g、f、cur构成一条折线

3.2.2 调整部分的代码实现

3.3 红黑树的验证

3.4 测试代码

四、红黑树实现完整代码

---

一、红黑树的概念

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

二、红黑树的性质

● 每个结点不是红色就是黑色

● 根节点是黑色的

● 如果一个节点是红色的，则它的两个孩子结点是黑色的（不允许出现连续的红色节点）

● 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（从根节点到每个叶子节点的空孩子路径上有相同数目的黑色节点）

● 每个叶子结点的空孩子节点都是黑色的

根据上述的五条性质，我们可以发现一个红黑树中如果有N个黑色节点，则根节点到任意一个叶子节点的距离：最短为㏒⑵N，最长为2㏒⑵N

2.1 红黑树与AVL树的比较

我们来看到下面的红黑树：

对于这棵红黑树，如果将其看成一个AVL树，是需要进行旋转的，但是在红黑树结构中却不需要

所以红黑树是近似平衡的，在搜索效率上会略逊AVL树一些，但是红黑树在结构上不要求绝对的平衡，这就造成插入相同的数据红黑树翻转的次数少于AVL树

实际使用中，在经常进行增删的场景下红黑树性能比AVL树更优，并且红黑树实现比较简单，所以实际运用中红黑树更多

三、红黑树的实现

3.1 红黑树节点的定义

enum Colour
{
	RED,
	BLACK
};

template<class Key, class Val>
struct RBTreeNode
{
	RBTreeNode<Key, Val>* _left;
	RBTreeNode<Key, Val>* _right;
	RBTreeNode<Key, Val>* _parent;//多一个指针指向其父节点,方便我们的后续操作
	pair<Key, Val> _kv;
	Colour _col;//颜色标识

	RBTreeNode(const pair<Key, Val>& kv)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_col(RED)//构造时,优先将节点的颜色置为红色
	{}
};

在这里提一下为什么要默认将节点的颜色置为红色：

在我们向红黑树中插入一个新节点时，如果将该节点置为黑色，就肯定会影响红黑树性质中的第四条：对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

例如：

我们现在在上面这棵树中，不管在哪个叶子节点的下方插入一个黑色的新增节点，从根节点到插入的节点的空孩子的路径上的黑色节点数目会变为4，而从根节点到其他叶子节点的空孩子的路径上的黑色节点数目会都为3

所以我们将新增节点的颜色置为红色就一定不会违反第四条红黑树性质，但是第三条呢？如果插入节点的父节点是红色的怎么办？

怎么办我们后面再说，反正总归比置为黑色一定会违反第四条性质好吧

3.2 数据的插入

由于红黑树也是平衡二叉搜索树的一种，我们在插入数据时也要找到合适的位置进行插入：

template<class Key, class Val>
class RBTree
{
	typedef RBTreeNode<Key, Val> Node;
public:
	bool Insert(const pair<Key,Val>& kv)
	{
		Node* cur = _root, * parent = nullptr;
		while (cur)//找到合适的位置
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(kv);
		cur->_parent = parent;
		//将插入的节点连接上二叉树
		if (parent == nullptr)
		{
			_root = cur;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}

private:
	Node* _root = nullptr;
};

插入到合适的位置之后，我们还要检查是否破坏了红黑树的结构（由于我们插入的是红色节点，所以只会出现两个红色节点连续的情况），如果出现了该情况，我们就要对其进行分类讨论并解决：

3.2.1 红黑树的调整思路

下面我们将出现异常情况的两个节点的那个子节点叫做cur，cur的父节点叫做father（简称f），father的父节点叫做grandfather（简称g），father的兄弟节点叫做uncle（简称u）

例如：

接下来，我们分类讨论：

3.2.1.1?cur为红，f为红，g为黑，u存在且为红

下面画出的情况表示的是抽象出的情况：A、B、C、D、E都是满足构成红黑树的子树

对于这种情况我们先将f和u节点变黑，再将g节点变红即可：

调整完后，要记得再向上检查g节点的父节点是否为红色哦~（如果g节点为整棵红黑树的根，最后要将其颜色置为黑）

3.2.1.2?cur为红，f为红，g为黑，u不存在/u存在且为黑

3.2.1.2.1 g、f、cur构成一条直线

对于这种情况：若f为g的左孩子，cur为f的左孩子，则进行右单旋：

再将f变黑，g变红：

相反， f为g的右孩子，cur为f的右孩子，则进行左单旋转：

再将f变黑，g变红：

3.2.1.2.2?g、f、cur构成一条折线

f为g的左孩子，cur为f的右孩子，则做左右双旋，旋转完后将cur节点颜色置黑、g节点颜色置红：

相反， f为g的右孩子，cur为f的左孩子，则做右左双旋，旋转完后将cur节点颜色置黑、g节点颜色置红：

对于旋转操作还不熟悉的同学可以看到这里：【数据结构高阶】AVL树

3.2.2 调整部分的代码实现

template<class Key, class Val>
class RBTree
{
	typedef RBTreeNode<Key, Val> Node;
public:

	bool Insert(const pair<Key, Val>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
	}
	Node* cur = _root, * parent = nullptr;
	while (cur)//找到合适的位置
	{
		if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			cout << "插入的值重复" << endl;
			return false;
		}
	}
	cur = new Node(kv);
	//将插入的节点连接上二叉树
	if (kv.first < parent->_kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;
	//开始调整
	while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点
	{
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				//继续向上更新
				cur = grandfather;
				parent = cur->_parent;
			}
			elsecur为红，p为红，g为黑，u不存在/u存在且为黑
			{
				if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线
				{
					//右单旋
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else//cur在p的右边,p在g的左边，构成一条折线
				{
					//左右双旋
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;//调整完跳出
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				//继续向上更新
				cur = grandfather;
				parent = cur->_parent;
			}
			elsecur为红，p为红，g为黑，u不存在/u存在且为黑
			{
				if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线
				{
					//左单旋
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else//cur在p的左边,p在g的右边，构成一条折线
				{
					//右左双旋
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;//调整完跳出
			}
		}
	}
	_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑
	return true;
}

private:
	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* pparent = parent->_parent;
		parent->_right = subRL;//更新parent的右节点
		if (subRL)//防止该节点为空
		{
			subRL->_parent = parent;//更新subRL的父节点
		}
		parent->_parent = subR;//更新parent的父节点
		subR->_left = parent;//subR的左子树置为parent
		subR->_parent = pparent;//更新subR的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subR;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
		}
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;
		parent->_left = subLR;//更新parent的左节点
		if (subLR)//防止该节点为空
		{
			subLR->_parent = parent;//更新subLR的父节点
		}
		parent->_parent = subL;//更新parent的父节点
		subL->_right = parent;//subL的右子树置为parent
		subL->_parent = pparent;//更新subL的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subL;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
	}

private:
	Node* _root = nullptr;
};

3.3 红黑树的验证

下面我们来写段代码来验证一课树是不是红黑树：

template<class Key, class Val>
class RBTree
{
	typedef RBTreeNode<Key, Val> Node;
public:

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点颜色是红色" << endl;
			return false;
		}

		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		// 连续红色节点
		return _Check(_root, 0, benchmark);
	}

private:
	bool _Check(Node* root, int blackNum, int benchmark)//计算每条路径上黑色节点的个数
	{
		if (root == nullptr)
		{
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色节点的数量不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

private:
	Node* _root = nullptr;
};

3.4 测试代码

void Test_RBTree()
{
	const size_t N = 50000;
	RBTree<int, int> t;
	for (size_t i = 0; i < N; ++i)
	{
		size_t x = rand() + i;
		t.Insert(make_pair(x, x));
	}
	t.InOrder();
	cout << t.IsBalance();
}

int main()
{
	Test_RBTree();
	return 0;
}

测试效果：

四、红黑树实现完整代码

#include<iostream>

using namespace std;

enum Colour
{
	RED,
	BLACK
};

template<class Key, class Val>
struct RBTreeNode
{
	RBTreeNode<Key, Val>* _left;
	RBTreeNode<Key, Val>* _right;
	RBTreeNode<Key, Val>* _parent;//多一个指针指向其父节点,方便我们的后续操作
	pair<Key, Val> _kv;
	Colour _col;//颜色标识

	RBTreeNode(const pair<Key, Val>& kv)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_col(RED)//默认构造时,优先将节点的颜色置为红色
	{}
};

template<class Key, class Val>
class RBTree
{
	typedef RBTreeNode<Key, Val> Node;
public:

	bool Insert(const pair<Key, Val>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
	}
	Node* cur = _root, * parent = nullptr;
	while (cur)//找到合适的位置
	{
		if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			cout << "插入的值重复" << endl;
			return false;
		}
	}
	cur = new Node(kv);
	//将插入的节点连接上二叉树
	if (kv.first < parent->_kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;
	//开始调整
	while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点
	{
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				//继续向上更新
				cur = grandfather;
				parent = cur->_parent;
			}
			elsecur为红，p为红，g为黑，u不存在/u存在且为黑
			{
				if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线
				{
					//右单旋
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else//cur在p的右边,p在g的左边，构成一条折线
				{
					//左右双旋
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;//调整完跳出
			}
		}
		else
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
			{
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				//继续向上更新
				cur = grandfather;
				parent = cur->_parent;
			}
			elsecur为红，p为红，g为黑，u不存在/u存在且为黑
			{
				if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线
				{
					//左单旋
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else//cur在p的左边,p在g的右边，构成一条折线
				{
					//右左双旋
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;//调整完跳出
			}
		}
	}
	_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑
	return true;
}
	void InOrder()//中序遍历
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点颜色是红色" << endl;
			return false;
		}

		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		// 连续红色节点
		return _Check(_root, 0, benchmark);
	}

private:
	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* pparent = parent->_parent;
		parent->_right = subRL;//更新parent的右节点
		if (subRL)//防止该节点为空
		{
			subRL->_parent = parent;//更新subRL的父节点
		}
		parent->_parent = subR;//更新parent的父节点
		subR->_left = parent;//subR的左子树置为parent
		subR->_parent = pparent;//更新subR的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subR;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
		}
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;
		parent->_left = subLR;//更新parent的左节点
		if (subLR)//防止该节点为空
		{
			subLR->_parent = parent;//更新subLR的父节点
		}
		parent->_parent = subL;//更新parent的父节点
		subL->_right = parent;//subL的右子树置为parent
		subL->_parent = pparent;//更新subL的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subL;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)//如果是空树就直接结束
		{
			return;
		}
		_InOrder(root->_left);//先递归遍历其左子树
		cout << root->_kv.first << " ";//再遍历其根节点
		_InOrder(root->_right);//最后递归遍历其右子树
	}

	bool _Check(Node* root, int blackNum, int benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色节点的数量不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

private:
	Node* _root = nullptr;
};