数据结构之红黑树

文章目录一：红黑树基本概念（1）什么是红黑树（2）红黑树的性质（3）为什么要给空结点（NIL）上色？（4）为什么最长路径一定不超过最短路径的2倍？（5）红黑树效率一：红黑树基本概念（1）什么是红黑树红黑树在二叉搜索树基础上，增加了一个域来标识结点的颜色，可以是红色和黑色。通过对任何一条从根节点到叶子结点的简单路径上的各个结点的颜色的约束，红黑树可以确保没有一条路径能比其他路径长出2倍，也就是最长路

快乐江湖

476人浏览 · 2021-07-05 00:15:15

快乐江湖 · 2021-07-05 00:15:15 发布

文章目录

一：红黑树基本概念
二：红黑树的实现

一：红黑树基本概念

（1）什么是红黑树

红黑树在二叉搜索树基础上，增加了一个域来标识结点的颜色，可以是红色和黑色。

通过对任何一条从根节点到叶子结点的简单路径上的各个结点的颜色的约束，红黑树可以确保没有一条路径能比其他路径长出2倍，也就是最长路径比最短路径的长度最长不超过2倍
在这里插入图片描述
AVL树是一颗严格的平衡二叉树，而红黑树只是近似于平衡，并不是严格平衡

（2）红黑树的性质

一个树如果为红黑树，则满足以下性质

每个结点要么是红色要么是黑色
根节点是黑色
每个空结点（NIL）是黑色的
如果一个结点的是红色的，那么它的孩子是黑色的（这意味着红色的结点是不可能连续存在的）
对于每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点

（3）为什么要给空结点（NIL）上色？

其实空结点的存在是为了标识路径，因为没有空结点我们可能会忽略部分路径，比如上图中如果去除NIL，看起来就少了几条路径
在这里插入图片描述
而一旦少了路径，其实就会违背上面的第5条性质

同时为了方便处理红黑树代码的边界条件，以及出于节省空间的目的，我们会使用一个哨兵来代替NIL，所以指向NIL的指针都用指向哨兵的指针替换

在这里插入图片描述

（4）为什么最长路径一定不超过最短路径的2倍？

这个问题也是红黑树的核心问题，我们可以进行证明，证明如下

假设有一条最长路径为a₁,a₂,…,a_s，还有一条最短路径为b₁,b₂,…,b_t
由对于每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点可知这两条路径的黑色结点的数目相同；再由如果一个结点的是红色的，那么它的孩子是黑色的可知路径中不可能存在重复的连续的红色结点。因此这意味着在极端情况，最短路径b₁,b₂,…,b_t中黑色结点的数目就是t，也就是全黑，而如果要满足结论，那么就意味着在最长路径中最多只能有 $\left \lfloor \frac{s-1}{2}\right \rfloor$ 个红结点（一旦超出，则不满足结论），同时最长路径的结点数目理应大于最短路径的结点数目，所以黑色结点的数目最少也应该有 $\left \lceil \frac{s+1}{2}\right \rceil$ 个，因此

接着利用反证法，题目要让我们证明， $s\leq 2*t$ 。因此假设 $s > 2 * t$ ，这样就有 $t\geq \left \lceil \frac{s+1}{2}\right \rceil\geq \left \lceil \frac{2t+2}{2}\right \rceil=t+1$ ，显然矛盾，因此可得 $s\leq 2*t$

（5）红黑树效率

这里引入黑高(black-height) 的概念：从某个结点出发（不含这个结点）到达任意一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高，即为bh(x)。由此可知红黑树的黑高其实就是根节点的黑高

首先以任一结点x为根的子树至少包含 $2^{bh(x)}-1$ 个内部结点（内部结点就是除叶结点外的结点），同时至多有 $2^{2*bh(x)}-1$ 个内部结点（此时结点一半是红色，一半是黑色）。证明这一点需要使用到数学归纳法：加入x的高度为0，那么x必为叶结点，其以x为根节点的子树至少包含 $2^{bh(x)}-1=2^{0}-1=0$ 个结点，剩余归纳步骤，我们考虑一个高度为正且有两个子结点的内部结点x，每个子结点有黑高bh(x)(自身颜色为红)或bh(x)-1。由于x子结点的高度要比x本身的高度要低，所以可以利用归纳假设得出每个子结点至少有 $2^{bh(x)-1}$ 个内部结点的结论。于是，以x为根的子树至少包含 $2^{bh(x)}-1)+(2^{bh(x)}-1)=2^{bh(x)}-1$ 个内部结点，因此得证。

接着我们可以证明红黑树效率很高，结论为一颗有n内部结点的红黑树的高度至多为 $2\lg (n+1)$ 。证明如下：我们假设h为树的高度，由如果一个结点的是红色的，那么它的孩子是黑色的可知从根到叶结点（不含根节点）的任何一条简单路径都至少有一半的结点为黑色，因此根的黑高至少为 $\frac{h}{2}$ ，再根据“以任一结点x为根的子树至少包含 $2^{bh(x)}-1$ 个内部结点”，则有 $n\geq 2^{\frac{h}{2}}-1$ ，也即 $n+1\geq 2^{\frac{h}{2}}$ ，也即 $\lg (n+1)\geq \frac{h}{2}$ 或 $h\leq 2\lg(n+1)$

所以，像查找这类的操作可以在红黑树上以 $O(\lg n)$ 时间内执行，因为这些操作在一棵高度为h的二叉搜索树上的运行时间为 $O(\lg n)$ ,同时任何包含n个结点的红黑树又都是高度为 $O(\lg n)$ 的二叉搜索树

二：红黑树的实现

（1）红黑树的结点

红黑树的结点共有5个属性

	:_left(nullptr)//左孩子
	,_right(nullptr)//右孩子
	,_parent(nullptr)//父亲
	,_kv(kv)//结点内的值
	,_col(col)//颜色

其中颜色采用枚举完成

enum Color//结点颜色
{
	RED, BLACK
};

（2）插入

红黑树插入遇到的第一个问题就是，插入的结点应该是什么颜色？如果插入红色，一旦父亲结点是红色的，那么将会违法性质4，如果插入黑色又会影响性质5。这里，我们选择插入红色，因为如果插入了黑色，将会导致从根到插入节点下的叶的任何路径都会比到其他叶的路径多一个黑色节点，这意味着调整时要顾及其它路径，这是很麻烦的。

声明：以下示意图有可能是一颗完整的树，也有可能是子树

情况1：插入的结点为红色，父亲结点为黑色
这种情况并没有违反红黑树性质，因此不需要做处理，插入结束

情况2：插入的结点为红色，父亲结点为红色，祖父结点为黑色，叔叔结点为红色

在这里插入图片描述
在这种情况下，一次基本的调整为：

将父亲结点变为黑色（防止违反性质4）
此时新插入结点所在的这条路径由于父亲结点变为了黑色，所以相较于其他路径就多了一个黑色结点，因此立即把祖先结点变为红色（防止违反性质5）
祖先结点变为红色后，叔叔结点又不满足条件了，所以再把叔叔结点变为黑色（防止违法性质4）

这样一来，如果上面是一个子树的话，经过这样的变化，可以满足：通过祖先结点所在的路径的黑色结点的数量没有发生变化，也就没有违反性质5，而同时又能满足了性质4。如果叔叔结点就是根节点也无妨，调整完成后，直接改为黑色即可。

在这里插入图片描述
如果上面的父亲结点是一个子树，那么修改之后父亲结点变为了红色，如果此时它的父亲结点还是红色的话，就要继续向上调整，也就是把g当成新的cur，大家看以发现这样的话其实也就回到了刚才的那种情况
在这里插入图片描述
情况3：插入的结点为红色，父亲结点为红色，祖父结点为黑色，叔叔结点不存在或者为黑色

如果叔叔结点不存在，那么cur结点一定是新增结点(如果它不是新增结点，那么cur和p中一定有一个是黑色的，这样的话就导致此路径的黑色结点数目比其他路径多了)
如果叔叔结点存在，那么它一定是黑色的（如果不是黑色的那就是情况1了）
这里cur结点之所以是红色，是因为cur的子树调整时将其改为了红色

如果是第2种情况，那么仅凭更改颜色是无法处理的
在这里插入图片描述
因为最长路径已经超过了最短路径2倍。因此解决的方法只能依靠旋转，像上面的那种情况中父亲结点为祖父结点的左孩子，cur结点为父亲结点的左孩子，所以进行右单旋转调整，让祖父结点作父亲结点的右孩子，并把父亲结点涂黑，祖父节点涂红

在这里插入图片描述
下面的图更为明显，经过旋转后，高度就降低了

情况4：插入的结点为红色，父亲结点为红色，祖父结点为黑色，叔叔结点不存在或者为黑色。区别情况2，插入的结点作为父亲结点的右孩子

在这种情况下需要进行双旋，首先对父亲进行左单旋转，此时就转换为了上面的情况3，依据情况3的描述继续处理即可
在这里插入图片描述
代码的实现如下，上图中展示的均是父亲结点在祖父结点左侧的情况，所以操作细节详细注释在代码中，对于父亲结点在祖父结点右侧的情况，与之相反。

下面是旋转的代码，关于平衡因子已经删除，具体旋转细节可以查看AVL树这篇文章
AVL

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;
	};
}

void RotateL(Node* parent)//左单旋转
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

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

	subR->_left = parent;

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

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

	subR->_parent = parentParent;
}

下面是插入的代码

pair<Node*,bool> Insert(const pair<K, V>& kv)
{
	//先按照二叉搜索树的方式插入
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;//根节点是黑色
		return pair(_root, true);
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (kv.first > cur->_kv.first)//插入的结点大于该结点，向右寻找
		{
			cur = cur->_right;
			if (cur == nullptr)//如果某次寻找中cur为空，表示找到插入位置
			{
				parent->_right = new Node(kv);//cur的父节点申请结点，默认红色
				cur = parent->_right;
				cur->_parent = parent;//然后把该结点的父节点指针指向父节点
			}
			parent = cur;
		}
		else if (kv.first < cur->_kv.first)
		{
			cur = cur->_left;
			if (cur == nullptr)
			{
				parent->_left = new Node(kv);
				cur = parent->_left;
				cur->_parent = parent;
			}
			parent = cur;
		}
		else//没有找到，返回false及相同的值的位置
		{
			return pair<cur, false>;
		}
	}
	Node* ret = cur;//保存cur，因为下面的调整过程，会改变cur

	while (parent && parent->_col == RED)//如果没有调整到根节点或者说父亲结点仍然为红色，则继续调整
	{
		Node* grandfather = parent->_parent;//祖父结点
		if (grandfather->_left == parent)//如果父亲结点位于祖父节点左面
		{
			Node* uncle = grandfather->_right;//叔叔结点（可能不存在，下面注意判空）

			//情况2：插入的结点为红色，父亲结点为红色，祖父结点为黑色，叔叔结点为红色
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;//先让父亲结点和叔叔结点变为黑色
				grandfather->_col = RED;//再让祖父结点变为红色

				//迭代处理
				cur = grandfather;
				parent = cur->_parent;

			}
			//情况3和4：插入的结点为红色，父亲结点为红色，祖父结点为黑色，叔叔结点不存在或者为黑色
			{
				//第一种：对祖父进行右单旋-插入的节点是父亲结点的左孩子，同时父亲结点是祖父节点的左孩子
				//				**grandfather**
				//			**parent**
				//	  **current**

				if (cur = parent->_left)
				{
					RotateR(grandfather);
					//旋转完成后parent到了祖父的位置，变色
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				
				//第二种：先对父亲进行左单旋，后对祖父进行右单旋-插入的结点是父亲结点的右孩子，同时父亲结点是祖父结点的左孩子
				//				**grandfather**
				//			**parent**
				//					**current**

				else
				{
					RotateL(parent);
					RotateR(grandfather);
					//变色
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				//对于旋转这类情况，旋转完成后立即跳出循环即可
				break;
			}
		}
		else//如果父亲结点位于祖父节点右面
		{
			Node* uncle = grandfather->_left;
			//情况2
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				cur = grandfather;
				parent = cur->_parent;
			}
			//情况3和4
			else
			{
				//**grandfather**
				//		**parent**
				//			**current**
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				//**grandfather**
				//		**parent**
				//	**current**
				else
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
	}
	
	_root->_col = BLACK;//以防万一，根节点一定是黑色
	return make_pair(ret, true);
}

（3）判断是否为一棵红黑树

可以看得出来，一个树要想成为红黑树，需要满足非常多的条件，所以如何判断一棵树是否为红黑树就显得额外重要

红黑树必须满足下面的性质

每个结点要么是红色要么是黑色
根节点是黑色
每个空结点（NIL）是黑色的
如果一个结点的是红色的，那么它的孩子是黑色的（这意味着红色的结点是不可能连续存在的）
对于每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点

对于“根节点是黑色”这一条规则很好判断

if (_root && _root->_col = RED)
{
	cout << "错误：根节点是黑色" << endl;
	return false;
}

对于“不应该存在连续的红色结点”这条规则，判断时只需要进行递归即可，如果某一时刻当前结点是红色同时父亲结点也是红色话，那么就违反了规则

bool _checkIf_continuous_red_node(Node* root)
{
	if (root == nullptr)
	{
		return true;
	}
	if (root->_col == RED)//不应该存在连续的红色结点
	{
		Node* parent = root->_parent;
		if (parent->_col == RED)
		{
			cout << "错误：出现了连续的红色结点" << endl;
			return false;
		}
	}
	return _checkIf_continuous_red_node(root->_left) && _checkIf_continuous_red_node(root->_right);
}

对于“所有路径上的黑色结点数目相同”这条规则，也采用递归的方式判断，blacknum变量采用传值方式传递，每次遇到黑色结点，blacknum++，如果遇到空，说明该路径走完，与standardnum（这是最左面路径的黑色结点数目，作为比较）比较，不相等的话说明违反规则

bool _checkIf_same_black_node(Node* root, int blackNum, int standardnum)
{
	if (root == nullptr)
	{
		//如果走到了空，blacknum保存的就是当前路径上黑色结点的数目
		return standardnum == blackNum;//进行比较，如果不相同说明违反规则
	}
	if (root->_col == BLACK)
	{
		blackNum++;
	}
	return _checkIf_same_black_node(root->_left, blackNum, standardnum) && _checkIf_same_black_node(root->_right, blackNum, standardnum);
}

综上，具体判断过程如下

bool isBalance()
{
	if (_root && _root->_col = RED)
	{
		cout << "错误：根节点是黑色" << endl;
		return false;
	}
	int standardnum = 0;//求出一条路径上的黑色结点数目，用于比较
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			++standardnum;
		}
		cur = cur->_left;
	}
	int blacknum = 0;
	return _checkIf_continuous_red_node(_root) && _checkIf_same_black_node(_root, blacknum, standardnum);
}