【数据结构】-----红黑树

目录

前言

一、what is it？

二、How achieve it？

 Ⅰ、结点类

Ⅱ、实现

插入

情况一：叔叔存在且为红色

 情况二：叔叔不存在或者叔叔为黑色

旋转

验证

 ①验证中序遍历

②验证是否满足红黑树的性质

Ⅲ、完整实现代码

三、AVL compare to Red BlackTree

---

前言

前面介绍了AVL树，它能够解决因单支树导致性能下降的问题，但是AVL树的旋转有些许的麻烦。当然，能解决因单支树导致性能下降不仅有AVL，还有一种数据结构，那就是下面介绍的红黑树。在实际运用比较多的红黑树！

一、what is it？

Ⅰ、概念

红黑树，是一种二叉搜索树，但是每个结点都有颜色，要么红色要么黑色。因此称之为红黑树。它是通过对任何一条从根到叶子的路径上结点着色方式的限制，以确保最长路径<=最短路径的2倍，因此能达到接近平衡的效果。

Ⅱ、性质

•  根节点是黑色
• 每个结点不是红色就是黑色
• 一个红色结点，其两个孩子结点必须是黑色(即不能有两个连续的红色结点)
• 对于每个结点，从该结点到其所有后代结点的路径上，黑色结点的数量必须相同(即每条路径上都存在相同数量的黑色结点)
• 空结点(NIL)都是黑色的

 问题：红黑树怎么保证结点最长路径<=最短路径*2？

实际上根据性质的第三、四点就可以推出。

因为每条路径上黑色结点数量必须相同，那最短路径必然是全黑结点(极端情况下)，最长路径必然是一黑一红交替（不一定存在）

因此，就能保证最长路径<=最短路径*2！

注意：这里的路径是从根结点到空结点NIL算做一条。

如下：

注意上图不是一棵红黑树，因为不满足每条路径上的黑色结点数量一致这一性质。从根到6的左子树这条路径上的黑色结点数量为1，其他路径都为2！

二、How achieve it？

在给出结点类之前，需要对颜色的存储做一些处理。这里为了代码的可读性，我们对颜色的存储可以采用枚举常量。

//枚举颜色
enum Color
{
	RED,
	BLACK
};

 Ⅰ、结点类

这里和AVL类似，就是少了个平衡因子，多了个颜色。

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
 
	pair<K, V> _kv;
	Color _co;
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_co(RED)//构造新结点必须是红色，根结点除外，根节点必须黑
	{}
};

这里需要注意一个问题：新增结点一定是红色，为何？实际上就是因为第四点性质比第三点性质更加的严格，永远不能动性质四。

• 若插入黑色结点，那必然违反性质四，即每条路径上的黑色结点数量就不一致了，每条路径都需要调整！
• 若插入红色结点，那可能违反性质三，若其父亲是黑色，就无需调整；其父亲为红，那就变色，代价较小，所以选择插入红色结点！

注意：根结点一定是黑色的 ！

Ⅱ、实现

插入

步骤：

1.首先依旧按照二叉搜索树的规则插入。小的放在左子树，大的放在右子树

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

因为新节点默认是红色的，所以：

• 新节点的父亲颜色如果是黑色，没有违反性质3，无需调整
• 新节点的父亲颜色如果是红色，那就需要调整，两种情况讨论

 如果新节点的父亲是红色，说明父亲结点不是根结点，那么就存在祖先，父亲的父亲，即爷爷结点，一定是黑的，不能有两个连续的红结点嘛，所以调整的两种情况主要取决于父亲的兄弟结点，即叔叔结点的颜色。

约定：cur为当前结点(一定红)，p为父节点(红)，g为爷爷结点(黑)，u为叔叔结点

情况一：叔叔存在且为红色

 这种情况的解决方案就是：将父亲和叔叔结点变黑，爷爷结点变红

• 若爷爷是根结点，调整完成后要变回黑色
• 若爷爷不是根，是子树，那就需要继续向上调整。调整逻辑也是一样父亲为黑或者空就停止，红就调整。

逻辑代码

//向上调整
cur = g;
parent = cur->_parent;

抽象图

形象图(举例)

可以看到，上述抽象图cur为红色并不是因为其本身就是红色，而是因为cur的子树在调整过程中，将cur结点的颜色有黑色变成红色。

注意：对于这种情况，插在左边右边都是一样的！！变色原理一样，比AVL简单！父亲和叔叔位置互换也一样

代码实现十分简单：

Node* u = g->_right;
//情况一:叔叔存在且为红，叔叔和父亲变红，爷爷g变黑
if (u && u->_co == RED)
{
	parent->_co = u->_co = BLACK;
	g->_co = RED;
 
	//向上调整
	cur = g;
	parent = cur->_parent;
}

 情况二：叔叔不存在或者叔叔为黑色

这种情况就需要旋转+变色，旋转的实现和AVL完全类似。变色规则：父亲变黑，爷爷变红温

①不存在

注意：不存在时cur一定是新增，若不是，那cur和p必定有一个黑色结点，这就不满足性质4了！

②存在且为黑

核心逻辑代码：

//    g
//  p   u
// c
//右单旋，p变黑，g变红
if (cur == parent->_left)
{
		RotaRTree(g);
		parent->_co = BLACK;
		g->_co = RED;
}
//    g
//  p   u
//    c
//左右双旋，先左再右。cur就变成了p的父亲
else
{
		RotaLTree(parent);//左单旋
		RotaRTree(g);//右单旋
		cur->_co = BLACK;
		g->_co = RED;
}

这里旋转代码和AVL树一样，就是将AVL树的平衡因子去掉而已！

插入实现完整代码

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_co = BLACK;//根结点一定为黑
			return true;
		}
		//找位置插入
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		cur->_co = RED;//新增结点一定为红色
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
 
		//插入后，开始调色
		//分情况调色
		while (parent && parent->_co == RED)//调到黑色或者空就停止
		{
			Node* g = parent->_parent;
			if (parent == g->_left)//父亲在左，叔叔在右
			{
				Node* u = g->_right;
				//情况一:叔叔存在且为红，叔叔和父亲变红，爷爷g变黑
				if (u && u->_co == RED)
				{
					parent->_co = u->_co = BLACK;
					g->_co = RED;
 
					//向上调整
					cur = g;
					parent = cur->_parent;
				}
				else//叔叔不存在或者存在且为黑
				{
					//    g
					//  p   u
					// c
					//右单旋，p变黑，g变红
					if (cur == parent->_left)
					{
						RotaRTree(g);
						parent->_co = BLACK;
						g->_co = RED;
					}
					//    g
					//  p   u
					//    c
					//左右双旋，先左再右。cur就变成了p的父亲
					else
					{
						RotaLTree(parent);//左单旋
						RotaRTree(g);//右单旋
						cur->_co = BLACK;
						g->_co = RED;
					}
					//不需要再调整，直接结束
					break;
				}
			}
			else//父亲在右，叔叔在左
			{
				Node* u = g->_left;
				if (u && u->_co == RED)//u存在且为红
				{
					parent->_co = u->_co = BLACK;
					g->_co = RED;
 
					cur = g;
					parent = cur->_parent;
				}
				else//叔叔不存在或者为黑
				{
					//    g
					//  u   p
					//        c
					//左单旋，p变黑，g变红
					if (cur == parent->_right)
					{
						parent->_co = BLACK;
						g->_co = RED;
						RotaLTree(g);
					}
					//    g
					//  u   p
					//    c
					//右左双旋，先右旋，在左旋
					else
					{
						RotaRTree(parent);//右
						RotaLTree(g);//左
						cur->_co = BLACK;
						g->_co = RED;
					}
					break;
				}
			}
		}
		_root->_co = BLACK;//始终保持根是黑色
		return true;
	}

旋转

不管是AVL树还是红黑树，二者需进行旋转形状都是一样，只是规则上的差异而各自进行特殊的处理罢了！

对于红黑树的旋转仅仅只需实现左旋和右旋即可，和AVL代码基本类似，只不过不需要控制平衡因子，情况没有AVL的复杂，十分的简单！这里直接给出实现代码，若有不解可以看看这篇文章AVL旋转！

//右旋
void RotaRTree(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* pparent = parent->_parent;
 
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	subL->_right = parent;
	parent->_parent = subL;
 
	if (parent == _root)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == pparent->_left)
			pparent->_left = subL;
		else
			pparent->_right = subL;
		subL->_parent = pparent;
	}
}
//左旋
void RotaLTree(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* pparent = parent->_parent;
 
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
	subR->_left = parent;
	parent->_parent = subR;
 
	if (parent == _root)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == pparent->_left)
			pparent->_left = subR;
		else
			pparent->_right = subR;
		subR->_parent = pparent;
	}
}

验证

 ①验证中序遍历

若中序遍历得到的是一个有序序列，说明为二叉搜索树。

中序遍历和二叉搜索树写法类似

public:
    void Inoder()
    {
	    _Inoder(_root);
	    cout << endl;
    }
private:
    Node *_root;//私有成员变量
	void _Inoder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inoder(root->_left);
		cout << root->kv.first<< " ";
		_Inoder(root->_right);
	}

②验证是否满足红黑树的性质

这里的难点是如何验证性质四，即如何判断每条路径上的黑色结点是否一致以及统计黑色结点数量？

统计黑色结点数

思路：实际统计黑色结点数量可以采用dfs，深度优先遍历，设置一个形参变量，一直递归到空结点为止，该形参变量代表的是从根结点到当前结点的路径上的黑色结点数量

判断每条路径上的黑色结点是否一致

思路：可以先去统计任意一条路径上的黑色结点的数量，以该路径黑色结点数量作为基准即可。若统计出有一条路径上黑色结点的数量和基准不 一致，那就出错咯！

实现代码：

	bool IsBalance()
	{
		//根为红就错误
		if (_root->_co == RED)
		{
			cout << "不符合根结点为黑这一规则" << endl;
			return false;
		}
		//先以一条路径为标志位，每条路径上的黑色结点的数和该标志位相比，不一样就不满足规则四
		int refnum = 0;//基准位
		Node* cur = _root;
		while (cur)
		{
			if (cur->_co == BLACK)
				refnum++;
			cur = cur->_left;//以最左路径上的黑色结点为基准
		}
		return _IsBalance(_root, 0, refnum);
	}
private:
	Node* _root = nullptr;
	bool _IsBalance(Node* root, int curblacknum, const int refnum)
	{
		if (root == nullptr)
		{
			if (curblacknum != refnum)
			{
				cout << "存在黑色结点不同的路径" << endl;
				return false;
			}
			return true;
		}
		if (root->_co == RED && root->_parent->_co == RED)
		{
			cout << "存在连续两个红色结点" << endl;
			return false;
		}
        //碰到黑色结点就++
		if (root->_co == BLACK)
		{
			++curblacknum;
		}
 
		return _IsBalance(root->_left, curblacknum, refnum) && _IsBalance(root->_right, curblacknum, refnum);
	}

Ⅲ、完整实现代码

#include <iostream>
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 _co;
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _co(RED)
	{}
};
 
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_co = BLACK;//根结点一定为黑
			return true;
		}
		//找位置插入
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		cur->_co = RED;//新增结点一定为红色
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
 
		//插入后，开始调色
		//分情况调色
		while (parent && parent->_co == RED)//调到黑色或者空就停止
		{
			Node* g = parent->_parent;
			if (parent == g->_left)//父亲在左，叔叔在右
			{
				Node* u = g->_right;
				//情况一:叔叔存在且为红，叔叔和父亲变红，爷爷g变黑
				if (u && u->_co == RED)
				{
					parent->_co = u->_co = BLACK;
					g->_co = RED;
 
					//向上调整
					cur = g;
					parent = cur->_parent;
				}
				else//叔叔不存在或者存在且为黑
				{
					//    g
					//  p   u
					// c
					//右单旋，p变黑，g变红
					if (cur == parent->_left)
					{
						RotaRTree(g);
						parent->_co = BLACK;
						g->_co = RED;
					}
					//    g
					//  p   u
					//    c
					//左右双旋，先左再右。cur就变成了p的父亲
					else
					{
						RotaLTree(parent);//左单旋
						RotaRTree(g);//右单旋
						cur->_co = BLACK;
						g->_co = RED;
					}
					//不需要再调整，直接结束
					break;
				}
			}
			else//父亲在右，叔叔在左
			{
				Node* u = g->_left;
				if (u && u->_co == RED)//u存在且为红
				{
					parent->_co = u->_co = BLACK;
					g->_co = RED;
 
					cur = g;
					parent = cur->_parent;
				}
				else//叔叔不存在或者为黑
				{
					//    g
					//  u   p
					//        c
					//左单旋，p变黑，g变红
					if (cur == parent->_right)
					{
						parent->_co = BLACK;
						g->_co = RED;
						RotaLTree(g);
					}
					//    g
					//  u   p
					//    c
					//右左双旋，先右旋，在左旋
					else
					{
						RotaRTree(parent);//右
						RotaLTree(g);//左
						cur->_co = BLACK;
						g->_co = RED;
					}
					break;
				}
			}
		}
		_root->_co = BLACK;//始终保持根是黑色
		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
 
	bool IsBalance()
	{
		//根为红就错误
		if (_root->_co == RED)
		{
			cout << "不符合根结点为黑这一规则" << endl;
			return false;
		}
		//先以一条路径为标志位，每条路径上的黑色结点的数和该标志位相比，不一样就不满足规则四
		int refnum = 0;//基准位
		Node* cur = _root;
		while (cur)
		{
			if (cur->_co == BLACK)
				refnum++;
			cur = cur->_left;
		}
		return _IsBalance(_root, 0, refnum);
	}
private:
	Node* _root = nullptr;
	bool _IsBalance(Node* root, int curblacknum, const int refnum)
	{
		if (root == nullptr)
		{
			if (curblacknum != refnum)
			{
				cout << "存在黑色结点不同的路径" << endl;
				return false;
			}
			return true;
		}
		if (root->_co == RED && root->_parent->_co == RED)
		{
			cout << "存在连续两个红色结点" << endl;
			return false;
		}
		if (root->_co == BLACK)
		{
			++curblacknum;
		}
 
		return _IsBalance(root->_left, curblacknum, refnum) && _IsBalance(root->_right, curblacknum, refnum);
	}
	//右旋
	void RotaRTree(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;
 
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		subL->_right = parent;
		parent->_parent = subL;
 
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == pparent->_left)
				pparent->_left = subL;
			else
				pparent->_right = subL;
			subL->_parent = pparent;
		}
	}
	//左旋
	void RotaLTree(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* pparent = parent->_parent;
 
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		subR->_left = parent;
		parent->_parent = subR;
 
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == pparent->_left)
				pparent->_left = subR;
			else
				pparent->_right = subR;
			subR->_parent = pparent;
		}
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}
 
};
 
void TestRBTree()
{
	RBTree<int, int> r;
	//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 ,8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto b : a)
	{
		r.Insert({ b,b });
	}
	r.InOrder();
	if (r.IsBalance())
	{
		std::cout << "十分的平衡" << std::endl;
	}
	else
	{
		std::cout << "歪了" << std::endl;
	}
}

三、AVL compare to Red BlackTree

红黑树和AVL树都是高效的平衡二叉树，都能够解决二叉搜索树的单支树的问题，增删改查的时间复杂度都是高度次，即O(logN)，但是二者的控制平衡的规则不同

• 红黑树只需保证最长路径<=最短路径*2即可
• AVL要严格控制平衡因子，即左右子树的高度差的绝对值不超过1

相对而言，红黑树降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优 ，而且红黑树实现起来简单，看代码就能看出来了，所以实际中运用红黑树更多！

红黑树一般多用于：

• C++STL库---map/set，mutil_map/mutil_set的底层实现(后续有文章)
• Java库
• Linux内核
• 其他一些库

---

 好了，兄弟们今天的内容就分享到这，如果对你有帮助，欢迎点赞+关注！你的支持永远是我的动力！