【C++实现红黑树】

文章目录

一、红黑树的概念及性质

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

如下：
在这里插入图片描述

性质：

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

为什么满足上面的条件就可以保证红黑树中最长路径节点个数不会超过最短路径节点个数的两倍？

首先要知道，一棵红黑树中最短的路径往往是全黑(或黑色远大于红色)，因为当节点越来越长，为了保持红黑树结构且保证每条路径黑色节点数量相同，就必须要增加红色节点。其次，最长路径颜色分布一般是一黑一红相间。

所以，假设每条路径中黑色节点的数量是N，那么N<=任意路径长度<=2N。
注意，这里的路径指的是从根节点到NIL的路线，所以路径个数等于NIL个数。

二、红黑树节点的定义

红黑树中每一个节点中内容与AVL树相似，但是又多了一个存储颜色的信息，如下：(还是采用键值对存储信息，可以先参照上一篇文章[C++实现AVL树])

enum Color
{
	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;//键值对存储数据
	Color _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:
	RBTree()
		:_root(nullptr)
	{}
private:
	Node* _root;
};

三、红黑树的插入

红黑树的插入操作与AVL树有类似的操作，只不过红黑树是根据颜色来控制节点，从而达到接近平衡的。

第一步，像二叉搜索树一样插入新节点：

比较简单，就不赘述了，直接粘贴代码：

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->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
	}

这里解释一下，为什么新增节点默认为红色！

当新增节点为黑色时，该节点所在路径的黑色节点数量就会+1，为了保证每条路径黑色节点数量相同，就需要改变每一条路径，得不偿失。而插入红色，只需要观察是否有连续的红色节点，如有，则进行部分节点(确定的几个节点)的颜色改动或旋转操作即可。

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

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

第三步，若红黑树性质破坏，则调整部分节点：

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

情况一: cur为红，p为红，g为黑，u存在且为红

例如：
在这里插入图片描述

注意，这里的抽象图可能表示一棵完整的树，也可能表示一棵树的子树。

解决方式：将p,u改为黑，g改为红。如果g为根节点，则在最后将g变为黑色；否则将g作为cur，继续向上调整。

上面的抽象图中，cur可能为新增节点，如下：
在这里插入图片描述

cur也可能不是新增节点，那么它原来一定是黑色，在子树向上调整的过程中变为了红色，如下：
在这里插入图片描述

以上是抽象图的两种具象图，抽象图可能有无数多种具象图，但是本质是一样的。

代码实现如下：

while (parent && parent->_col == RED)
{
	Node* grandfather = parent->_parent;
	if (parent == grandfather->_left)
	{
		Node* uncle = grandfather->_right;
		if (uncle && uncle->_col == RED)
		{
			//变色+向上调整
			parent->_col = uncle->_col = BLACK;
			grandfather->_col = RED;
			cur = grandfather;
			parent = cur->_parent;
		}
	}
}
//在循环中不管最终g是否为根节点，在循环外直接将根节点变为黑色
_root->_col = BLACK;

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

例如：
在这里插入图片描述

这时，u有两种情况：

  • 如果u节点不存在，则c一定是新增节点。因为如果c不是新增节点，那么c和p一定有一个颜色是黑色，否则不满足每条路径黑色节点数量相同的条件。
  • 如果u节点存在，则其一定是黑色的，那么c节点原来的颜色一定是黑色，在其子树调整过程中变为了红色。

由于这时候，已经不满足最长路径不超过最短路径两倍的条件了，所以要进行旋转。

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

如下：
在这里插入图片描述
在这里插入图片描述
这里就不粘贴代码了，最后会给出完整代码。

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

例如：
在这里插入图片描述

很明显针对这种不在同一侧的情况要进行双旋。

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，
p为g的右孩子，cur为p的左孩子，则针对p做右单旋转
则转换成了情况2
随后用情况2的处理方法继续调整即可。

如下：
在这里插入图片描述
代码后文给出。

四、红黑树的验证

红黑树的验证就是就是检查每一条路径中有没有连续的红色节点出现，以及每一条路径中黑色节点的个数是否相等，还有根节点是否为黑色。

那么只需要观察每个节点与其父节点是否都为红色、顺便检查根节点是否为黑色、再随便统计出其中某条路径的黑色节点总数，将其与其他路径相比即可。

代码如下：

bool IsBalance()
{
	if (_root && _root->_col == RED)
	{
		cout << "根节点不是黑色" << endl;
		return false;
	}
	// 最左路径黑色节点数量做基准值
	int banchmark = 0;
	Node* left = _root;
	while (left)
	{
		if (left->_col == BLACK)
			++banchmark;
		left = left->_left;
	}

	int blackNum = 0;
	return _IsBalance(_root, banchmark, blackNum);
}

bool _IsBalance(Node* root, int banchmark, int blackNum)
{
	if (root == nullptr)
	{
		if (banchmark != blackNum)
		{
			cout << "存在路径黑色节点的数量不相等" << endl;
			return false;
		}
		return true;
	}

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

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

	return _IsBalance(root->_left, banchmark, blackNum)
		&& _IsBalance(root->_right, banchmark, blackNum);
}

五、完整代码

#pragma once
#include <iostream>
#include <map>
#include <vector>
using namespace std;

enum Color
{
	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;//键值对存储数据
	Color _col;//颜色

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

template<class K, class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:_root(nullptr)
	{}

	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->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 控制平衡
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// 1、uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色+继续向上处理
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else // 2 + 3、uncle不存在/ 存在且为黑
				{
					if (cur == parent->_left)
					{
						// gpc在同一侧单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						// gpc不在同一侧双旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			else // parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					// 变色+继续向上处理
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else // 2 + 3、uncle不存在/ 存在且为黑
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;
		return true;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		Node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subR;
			else
				parentParent->_right = subR;
			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;
			else
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点不是黑色" << endl;
			return false;
		}
		// 最左路径黑色节点数量做基准值
		int banchmark = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
				++banchmark;
			left = left->_left;
		}

		int blackNum = 0;
		return _IsBalance(_root, banchmark, blackNum);
	}

	bool _IsBalance(Node* root, int banchmark, int blackNum)
	{
		if (root == nullptr)
		{
			if (banchmark != blackNum)
			{
				cout << "存在路径黑色节点的数量不相等" << endl;
				return false;
			}
			return true;
		}

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

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

		return _IsBalance(root->_left, banchmark, blackNum)
			&& _IsBalance(root->_right, banchmark, blackNum);
	}

private:
	Node* _root;
};

六、总结

其实红黑树看起来很复杂，但却比AVL树更好控制，它要求的不是绝对平衡，所以不用每次插入都观察平衡因子。通过红黑颜色达到的目的是不让一棵树的高度太大，是一种接近于平衡的状态。

另外，三种调整的方式其实关键之处都在于uncle节点是否存在及其颜色。在调整过程中的旋转处理也跟AVL树一样，而且不用控制平衡因子。

比较容易出错的点在于三种情况中，parent、grandfather和cur节点在不在同一侧，这一点关乎于是否要用到双旋以及单旋的方向，容易弄混，一定要谨慎！！！

本篇完！青山不改，绿水长流！

版权声明：本文为m0_62618590原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。