【红黑树】—— 我与C++的不解之缘（二十五）

前言

学习了avl树，现在来学习红黑树。

一、什么是红黑树

红黑树是一颗平衡二叉搜索树，它每一个节点增加了一个存储位表示节点的颜色，可以是红色或者黑色。

相比较于AVL树，红黑树也是一个自平衡二叉搜索树，但是它与AVL树控制平衡的方式不同；

• AVL是通过平衡因子来控制整个树的平衡
• 红黑树则是通过节点的颜色红/黑来控制整个树的平衡

这里红黑树通过对任何一条从根到叶子的路径上每一个节点的颜色的约束，从而确保最长路径不会超过最短路径的2倍，因此让整个树保证平衡。

红黑树的规则

红黑树遵循以下几条规则：

• 每一个节点的颜色不是RED/红色就是BLACE/黑色。
• 根节点的颜色为BLACK。
• 如果一个节点是红色的，那么它的孩子节点就一定是黑色的；也就是在任意一条路径中不会出现连续的红色节点。
• 对任何一个节点，从这个节点到其所有的NULL的简单路径上，均包含相同数量的黑色节点。

这里在《算法导论》和《STL源码剖析》书籍中，存在这样的一条定义每个叶子节点NIL都是黑色；

注意：这里说的并不是我们认为的叶子节点，而是NULL节点；

有了NIL节点我们就可以十分清楚的看出来所有的路径。

为什么红黑树能确保最长路径不超过最短路径的2倍

• 根据规则4，从根节点到NULL节点每条路径都存在相同数量的黑色节点；所以这里假设一下极端情况：最短路径下全是黑色节点，长度为bh，那么黑色节点的个数也是bh。
• 根据规则3，任何一条路径下不会存在连续的红色节点，那极端情况下，最长路径就是由一黑一红组成的，那最长路径的长度为2*bh，黑色节点个数是bh。
• 然而极端情况并不是在每一个红黑树中都存在的；假设从根节点到NULL的一条路径长度为h，那就存在bh <= h <= 2*bh。

红黑树的效率

对于红黑树，确实控制了平衡，但是它的查找效率如何呢？

这里假设红黑树的节点个数为n，h是最短路径的长度；那我们就可以得出红黑树最坏情况是走最长路径2h，时间复杂度也是O(log N)

虽然说红黑树相对于AVL树的效率较差一点，但是它的效率还是O(log N)

• AVL树通过高度来严格控制了整个树的平衡
• 而红黑树就通过了四条规则，控制树中节点的颜色来控制这个树的相对平衡。

二、红黑树的结构

说了这么多，现在来看一下红黑树的结构

红黑树首先是一个三叉链结构，还要存放pair<K,V>，和颜色Color

这里颜色使用枚举变量来表示

enum Color
{
	RED,
	BLACK,
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	pair<K, V> _kv;
	Color _col;

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

三、红黑树的插入

了解了红黑树节点的结果，现在来看红黑树的插入节点

插入一个值，我们需要按照二叉搜索树的结构来进行插入，插入之后来判断是否满足红黑树的规则

这里AVL在找到插入位置并插入节点后做的是更新平衡因子；

而红黑树则是进行循环操作（变色、旋转+变色1等），直到其父节点不存在（遍历到_root)或者父节点颜色为BLACK。

首先就是插入节点的颜色

• 如果是空树插入，新增节点为黑色；
• 那如果是非空树的插入节点，新增节点就必须是红色

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree() {};
	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//空树插入
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		//非空树插入
		Node* tail = _root;
		Node* parent = nullptr;
		while (tail)
		{
			if (kv.first > tail->_kv.first)
			{
				parent = tail;
				tail = tail->_right;
			}
			else if (kv.first < tail->_kv.first)
			{
				parent = tail;
				tail = tail->_left;
			}
			else
			{
				return false;
			}
		}
		Node* cur = new Node(kv);
		cur->_col = RED;//新插入节点一定是红色
		cur->_parent = parent;
		if (cur->_kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else if (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		//进行不满足规则的一系列处理
	}
private:
	Node* _root;
};

这里如果新增节点是黑色，那就一定破坏了规则四（因为插入之前是符合条件的红黑树）。

这里我们插入红色节点，其父节点为黑色就不需要做任何调整；

如果父节点是红色，这时违反了规则三，我们需要进一步分析

• 此时其父节点p为红色，其祖父节点g就一定为黑色；而叔节点uncle颜色并不确定

  这时c插入节点，p父节点，g祖父节点颜色都是固定的，这种情况下我们来看u叔节点

我们根据u节点的颜色可以分为三种情况

1. 情况一： 变色

在上述中，我们已经确定了c、p、g的颜色，现在我们现在唯一不能确定的就是u节点；

如果u节点存在，且u节点的颜色为红色，如下图所示

对于这种情况，u存在且为红色；通过观察我们可以发现：

g节点的黑色节点影响的路径是其左右子树p和u的路径，那我们将p和u变成黑色、g变成红色

变化之后可以发现，从g节点到NULL节点的路径上的黑色几点并没有发生变化。

这里有些问题：

1. 在上述图中，g的父节点为黑色，那如果g的父节点为红色呢？

这就好说了，将g赋值给c，继续执行循环即可。

2. 那现在存在一个问题，如果在向上变色的过程中，g为根节点怎么办？

这里在执行完循环过后，直接把_root的颜色修改为黑即可。（这样操作以后从根节点到任意NULL节点的简单路径中黑色节点的个数还是相等的）

3. 如果在执行向上变色的过程中遇到u不存在或者u存在但其颜色为黑怎么办？

接着往下看情况二：

2. 情况二：单选 + 变色

如果我们在向上执行变色的过程中，遇到了u不存在或者u存在但它的颜色为黑；

这时我们就不能只变色来解决问题了。

这种情况下，我们就需要进行一次单旋，再进行变色才能解决问题

根据上图可以看到，右单旋的条件是c = p->_left && u==g->_right

这里都是右单旋的问题，左单旋是以下情况，就不做分析了。

进行右单旋加变色的条件是c = p->_right && u==g->_left

3. 情况三： 双旋 + 变色

在上述过程中，只有单旋，那如果单旋解决不了问题呢？

如下图所示：

如果我们在p的这个位置插入（或者有g向上更新变化过来的c）

这时就不能就进行单旋了，就像AVL中平衡因中一样，如果进行了单旋就会发现把问题变得更加复杂了。

这是要进行左右双旋转

先以p节点进行一次左单旋，再以g节点进行一下右单旋。

当然，存在左右双旋的情况，也存在右左双旋的情况，如下图所示（这里就不推理了）

插入代码实现：

有了上述情况分析，现在来实现红黑树插入的代码：

	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//空树插入
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		//非空树插入
		Node* tail = _root;
		Node* parent = nullptr;
		while (tail)
		{
			if (kv.first > tail->_kv.first)
			{
				parent = tail;
				tail = tail->_right;
			}
			else if (kv.first < tail->_kv.first)
			{
				parent = tail;
				tail = tail->_left;
			}
			else
			{
				return false;
			}
		}
		Node* cur = new Node(kv);
		cur->_col = RED;//新插入节点一定是红色
		cur->_parent = parent;
		if (cur->_kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}
		else if (cur->_kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		//进行不满足规则的一系列处理
		while(parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if(parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//  g
				// p u
				if(uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if(cur == parent->_left)
					{
						//右单旋 + 变色
						RevoleR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
						break; 
					}
					else
					{
						//左右单旋 + 变色
						RevoleL(parent);
						RevoleR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
				}
			}
			else
			{
				//  g
				// u p
				Node* uncle = grandfather->_left;
				if(uncle && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if(cur == parent->_right)
					{
						//左单旋 + 变色
						RevoleL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
						break; 
					}
					else
					{
						//右左单旋 + 变色
						RevoleR(parent);
						RevoleL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
private:
	void RevoleR(Node* parent) //右单旋
	{
		Node* subl = parent->_left;
		Node* sublr = parent->_left->_right;

		parent->_left = sublr;
		if (sublr)
			sublr->_parent = parent;
		Node* ppNode = parent->_parent;
		parent->_parent = subl;
		subl->_parent = ppNode;
		if (ppNode == NULL)
		{
			_root = subl;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subl;
			}
			else if (parent->_right)
			{
				ppNode->_right = subl;
			}
		}
	}
	void RevoleL(Node* parent)//左单旋
	{
		Node* subr = parent->_right;
		Node* subrl = parent->_right->_left;
		
		parent->_right = subrl;
		if (subrl)
			subrl->_parent = parent;

		Node* ppNode = parent->_parent;
		parent->_parent = subr;
		subr->_left = parent;
		subr->_parent = ppNode;
		if (ppNode == NULL)
		{
			_root = subr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subr;
			}
			else if (parent == ppNode->_right)
			{
				ppNode->_right = subr;
			}
		}
	}

四、红黑树的查找

红黑树依旧是一个搜索二叉树，它的查找效率仍旧是log N；比AVL略微差一点。

	bool find(const K& key)
	{
		Node* tail = _root;
		while (tail)
		{
			if (key > tail->_kv.first)
			{
				tail = tail->_right;
			}
			else if (key < tail->_kv.first)
			{
				tail = tail->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

五、红黑树验证

说了这么多，现在来看一下如何验证一个树是不是红黑树。

首先去检查最长路经和最短路径是不可行的，因为如果满足最长路径不超过最短路径的2倍，但是颜色也可能不满足规则。

也也能存在问题；

所以我们需要去检查红黑树的四条规则

• 对于规则一，我们使用枚举常量，就保证了颜色不是黑色就是红色。
• 规则二，直接检查跟节点颜色即可。
• 规则三，使用前序遍历检查，遇到红色节点（可能不存在孩子节点，有可能存在一个/两个），非常不方便；这里可以反过来检查，遇到红色节点检查其父节点即可。
• 规则四，在遍历的过程中，用形参来记录根节点到当前节点的BLACK_num（黑色节点个数），前序遍历遇到黑色节点就++BLACK_num，遍历到空就计算出了一条路径的黑色节点个数，再将任一条路径黑色节点个数作为参考值，依次比较即可。

这里就不去测试了，在使用RBTree完成封装以后再一起去测试。

六、红黑树的删除

对于红黑树的删除，这里暂时不做讨论，等以后再深入研究。

感兴趣的可以参考书籍《算法导论》和《STL源码剖析》。

到这里本篇内容就结束了，希望对你有所帮助。

制作不易，感谢大佬的支持。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws