红黑树的介绍与实现

前言

前面我们介绍了AVL树，AVL树是一棵非常自律的树，有着严格的高度可控制！但是正它的自律给他带来了另一个问题，即虽然他的查找效率很高，但是插入和删除由于旋转而导致效率没有那么高。我们上一期的结尾说过经常修改的话就不太适合AVL树了，而红黑树更加适合！OK，本期就来介绍一下赫赫有名的红黑树！

本期内容介绍

什么是红黑树

红黑树的实现

红黑树的效率分析以及应用

什么是红黑树？

红黑树是1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的 " 红黑树 "。

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

OK，这就是一棵红黑树：

最长节点的路径就是一黑一红的交替，最短的就是两黑：

红黑树的性质

1、每个结点要么是红色，要么是黑色

2、根节点是黑色

3、如果一个结点是红色，则它的两个孩子结点是黑色

4、对于任意一个节点，从该结点到其所有的后代叶子结点的简单路径上，均包含相同的黑色结点

5、每个叶子结点就是黑色的（此处的叶子结点指的是空节点）

上面的这5条性质就是限制红黑树平衡的规则！其中4最重要的下来是3，基本所有的操作都是围着4进行的！！！

红黑树的实现

OK，上面介绍了红黑树是一种二叉搜索树，只不过是在每个结点添加了一个存储颜色的颜色位，所以它的大框架还是和搜索树一样的，所以我们就先搭一个框架出来！

enum Col//颜色
{
	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;//数据域
	Col _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)
		,_size(0)
	{}

private:
	Node* _root;//根节点
	size_t _size;//节点的数量
};

思考：新插入的节点应该是红色还是黑色？为什么？

新插入的节点一定是红色！

因为新插入的节点是红色可能违反性质3，但一定不违反性质4！

如果新插入的是黑色，一定违反性质4，也就是在部分子路径上增加了黑色节点。所以插入的新节点一定是红色，即使红色违反了性质3也是比较好控制的！

OK，这里依旧是采用的三叉链，原因是方便找父亲：

红黑树的插入

上面介绍了，红黑树的本质是一种二叉搜索树，所以先不管它的颜色和高度如何调节，先把搜索树的那一套给整出来：

bool Insert(const pair<K, V>& kv)
{
	Node* cur = _root;//当前节点
	Node* parent = nullptr;//插入位置的父亲

	//第一次插入
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;//根节点是黑色
		return true;
	}

	//寻找插入的位置
	while (cur)
	{
		if (cur->_kv.first < kv.first)//插入节点的key比当前节点的key大
		{
			parent = cur;
			cur = cur->_right;//去右边找
		}
		else if(cur->_kv.first > kv.first)//插入节点的key比当前节点的key小
		{
			parent = cur;
			cur = cur->_left;//去左边找
		}
		else
		{
			return false;//插入的节点存在
		}
	}

	//找到插入位置
	cur = new Node(kv);
	//链接
	if (parent->_kv.first > cur->_kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;

	//颜色和高度调整
	//....

	return true;
}

OK，还是先来验证一下当前的逻辑对不对，所以走个中序看看是不是有序即可：由于中序要根节点，而类外面是无法访问的，所以我们还是和以前一样搞成子函数或提供get和set方法；这里就搞成子函数了：

中序遍历

void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
		
	_InOrder(root->_left);
	cout << root->_kv.first << ":" << root->_kv.second << endl;
	_InOrder(root->_right);
}

OK，没问题，下面我们就来讨论一下红黑树的维持平衡的方式:变色和旋转！

红黑树的变色和旋转

由于新插入的节点一定是红色的，此时分为两种情况，1、父亲为黑  2、父亲为红

如果父亲为黑，不违反任何性质，插入结束；

如果父亲为红，看看叔叔，此时叔叔有三类情况：1、叔叔存在且为红  2、叔叔不存在  3、叔叔存在为黑

如果，叔叔存在且为红：变色（将父亲和叔叔变黑色，将爷爷变红色），继续更新

如果，叔叔不存在或存在且为黑，旋转 + 变色（如果孩子是父亲的左/右，先对孩子父亲进行左/右旋，在对爷爷进行左/右）

OK，这里看着可能会有些迷，看看下面的导图会很清楚：

OK，理解了上述的表达，下面我来画图解释一下：

parent是黑色插入结束

parent为红，叔叔存在且为红（变色）

父亲和叔叔变黑，爷爷变红，继续向上更新

这里只画了parent在爷爷的左边的情况，如果parent在爷爷的右边和这个是一样的！

parent为红，叔叔不存在会存在为黑（变色 + 旋转）

如果parent在爷爷的左，且cur在父亲的左，对爷爷进行右单旋；

如果parent在爷爷的左，且cur在父亲的右，先对parent左单旋，在对爷爷进行右单旋；

如果parent在爷爷的右，且cur在父亲的右，对爷爷进行左单旋；

如果parent在爷爷的右，且cur在父亲的左，先对parent右单旋，在对爷爷进行左单旋；

OK，废话不多说直接上代码：

bool Insert(const pair<K, V>& kv)
{
	Node* cur = _root;//当前节点
	Node* parent = nullptr;//插入位置的父亲

	//第一次插入
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_size++;//插入成功节点数+1
		_root->_col = BLACK;//根节点是黑色
		return true;
	}

	//寻找插入的位置
	while (cur)
	{
		if (cur->_kv.first < kv.first)//插入节点的key比当前节点的key大
		{
			parent = cur;
			cur = cur->_right;//去右边找
		}
		else if(cur->_kv.first > kv.first)//插入节点的key比当前节点的key小
		{
			parent = cur;
			cur = cur->_left;//去左边找
		}
		else
		{
			return false;//插入的节点存在
		}
	}

	//找到插入位置
	cur = new Node(kv);
	//链接
	if (parent->_kv.first > cur->_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)
			{
				grandfather->_col = RED;
				parent->_col = uncle->_col = BLACK;
				//继续向上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else//叔叔不存在或存在但为黑 -> 变色 + 旋转
			{
				if (cur == parent->_left)//cur在父亲的左
				{
					//		   g
					//	   p		u
					// c
					RotateR(grandfather);//旋转
					parent->_col = BLACK;//变色
					grandfather->_col = RED;
				}
				else//cur在父亲的右
				{
					//		  g
					//	  p		  u
					//        c
					RotateL(parent);//旋转
					RotateR(grandfather);
					cur->_col = BLACK;//变色
					grandfather->_col = RED;
				}

				break;//旋转后不需要再向上更新了
			}
		}
		else//parent在爷爷的右
		{
			Node* uncle = grandfather->_left;//叔叔在父亲的左
			//叔叔存在且为红 -> 变色
			if (uncle && uncle->_col == RED)
			{
				grandfather->_col = RED;
				parent->_col = uncle->_col = BLACK;
				//继续向上调整
				cur = grandfather;
				parent = cur->_parent;
			}
			else//叔叔不存在或存在但为黑 -> 变色 + 旋转
			{
				if (cur == parent->_left)//cur在父亲的左 
				{
					//		  g
					//	  u		   p
					//        c
					RotateR(parent);//旋转
					RotateL(grandfather);
					cur->_col = BLACK;//变色
					grandfather->_col = RED;
				}
				else
				{
					//		  g
					//	  u		   p
					//                 c
					RotateL(grandfather);//旋转
					parent->_col = BLACK;//变色
					grandfather->_col = RED;
				}

				break;//旋转后不需要再向上更新了
			}
		}
	}

	_root->_col = BLACK;//保证根节点永远是黑色
	_size++;//插入成功节点数+1

	return true;
}

旋转

红黑树的旋转没有，AVL的复杂，只有左右单旋且没有平衡因子！整体的逻辑和AVL一样的，这里不在详细介绍了！

void RotateR(Node* parent)
{
	Node* subL = parent->_left;//父亲的左
	Node* subLR = subL->_right;//左子树的右
	Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接

	parent->_left = subLR;//将左子树的右给父亲的做
	if (subLR)
		subLR->_parent = parent;

	subL->_right = parent;//parent做左子树的右
	parent->_parent = subL;

	if (parent == _root)//parent是根
	{
		_root = subL;//此时的新根就是subL
		ppNode = nullptr;
	}
	else//parent不是根
	{
		//将新的根连接到ppNode
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
		subL->_parent = ppNode;
	}
}

void RotateL(Node* parent)
{
	Node* subR = parent->_right;//父亲的右
	Node* subRL = subR->_left;//右子树的左
	Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接

	parent->_right = subRL;//将右子树的左连接到parent的右
	if (subRL)
		subRL->_parent = parent;

	subR->_left = parent;//parent连接到subR的左
	parent->_parent = subR;

	if (parent == _root)//parent是根
	{
		_root = subR;//此时的新根就是subR
		ppNode = nullptr;
	}
	else//parent不是根
	{
		//将新的根连接到ppNode
		if (ppNode->_left == parent)
		{
			ppNode->_left = subR;
		}
		else
		{
			ppNode->_right = subR;
		}
		subR->_parent = ppNode;
	}
}

OK，我们验证一下，判断一下是否是平衡的：

是否平衡

先获取任意一条路径的黑色节点，然后通过dfs进行检查每个结点是不是符合红黑树的规则！

如果出现连续的红色节点，不符合！判断方式：当出现红色节点时，检查其父节点是否是红色的，如果是则不符合！

如走到空了，检查该条路径的黑色节点和一开始求出的是否一致，不一致则不符合！

当前节点符合，去检查其左右！

bool IsBalance()
{
	if (_root && _root->_col == RED)
	{
		return false;//根为红，一定不是红黑树
	}

	int black = 0;//获取任意一条路径的黑色节点（这里是最左路）
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			black++;
		}

		cur = cur->_left;
	}

	return Check(_root, black, 0);
}

bool Check(Node* root, const int black, int num)
{
	if (root == nullptr)
	{
		//当走到叶子节点的时候和其他路径的黑色节点的个数不一样
		if (black != num)
		{
			return false;
		}

		return true;
	}

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

	//遇到黑色节点++
	if (root->_col == BLACK)
	{
		num++;
	}

	//当前节点符合红黑树，它的左右子树也要都符合
	return Check(root->_left, black, num) && Check(root->_right, black, num);
}

OK，验证一下：

OK，么有问题！下面把其他的接口补一下！

Size

由于我们提前记录了_size所以直接返回成员_size即可！

size_t Size()
{
	return _size;
}

Find

和以前的搜索树一样，大了去右边找，小了去左边找！

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < key)//插入节点的key比当前节点的key大
		{
			cur = cur->_right;//去右边找
		}
		else if (cur->_kv.first > key)//插入节点的key比当前节点的key小
		{
			cur = cur->_left;//去左边找
		}
		else
		{
			return cur;//找到了
		}
	}

	return nullptr;//没找到
}

再来一组随机的测试用例：插入1亿个随机值，看看时间和是否平衡（注意这里一亿个节点在32位debug下可能内存空间不够，可以把他改成64的release地址空间大一点）

void Test()
{
	const int N = 100000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}

	size_t begin2 = clock();
	RBTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	size_t end2 = clock();

	cout << "time :" << end2 - begin2 << endl;
	cout << t.IsBalance() << endl;
}

红黑树的删除：请参考这篇博客 ：红黑树的删除

全部源码

#pragma once

enum Col//颜色
{
	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;//数据域
	Col _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)
		,_size(0)
	{}

	bool Insert(const pair<K, V>& kv)
	{
		Node* cur = _root;//当前节点
		Node* parent = nullptr;//插入位置的父亲

		//第一次插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_size++;//插入成功节点数+1
			_root->_col = BLACK;//根节点是黑色
			return true;
		}

		//寻找插入的位置
		while (cur)
		{
			if (cur->_kv.first < kv.first)//插入节点的key比当前节点的key大
			{
				parent = cur;
				cur = cur->_right;//去右边找
			}
			else if(cur->_kv.first > kv.first)//插入节点的key比当前节点的key小
			{
				parent = cur;
				cur = cur->_left;//去左边找
			}
			else
			{
				return false;//插入的节点存在
			}
		}

		//找到插入位置
		cur = new Node(kv);
		//链接
		if (parent->_kv.first > cur->_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)
				{
					grandfather->_col = RED;
					parent->_col = uncle->_col = BLACK;
					//继续向上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else//叔叔不存在或存在但为黑 -> 变色 + 旋转
				{
					if (cur == parent->_left)//cur在父亲的左
					{
						//		   g
						//	   p		u
						// c
						RotateR(grandfather);//旋转
						parent->_col = BLACK;//变色
						grandfather->_col = RED;
					}
					else//cur在父亲的右
					{
						//		  g
						//	  p		  u
						//        c
						RotateL(parent);//旋转
						RotateR(grandfather);
						cur->_col = BLACK;//变色
						grandfather->_col = RED;
					}

					break;//旋转后不需要再向上更新了
				}
			}
			else//parent在爷爷的右
			{
				Node* uncle = grandfather->_left;//叔叔在父亲的左
				//叔叔存在且为红 -> 变色
				if (uncle && uncle->_col == RED)
				{
					grandfather->_col = RED;
					parent->_col = uncle->_col = BLACK;
					//继续向上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else//叔叔不存在或存在但为黑 -> 变色 + 旋转
				{
					if (cur == parent->_left)//cur在父亲的左 
					{
						//		  g
						//	  u		   p
						//        c
						RotateR(parent);//旋转
						RotateL(grandfather);
						cur->_col = BLACK;//变色
						grandfather->_col = RED;
					}
					else
					{
						//		  g
						//	  u		   p
						//                 c
						RotateL(grandfather);//旋转
						parent->_col = BLACK;//变色
						grandfather->_col = RED;
					}

					break;//旋转后不需要再向上更新了
				}
			}
		}

		_root->_col = BLACK;//保证根节点永远是黑色
		_size++;//插入成功节点数+1

		return true;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)//插入节点的key比当前节点的key大
			{
				cur = cur->_right;//去右边找
			}
			else if (cur->_kv.first > key)//插入节点的key比当前节点的key小
			{
				cur = cur->_left;//去左边找
			}
			else
			{
				return cur;//找到了
			}
		}

		return nullptr;//没找到
	}

	void InOrder()
	{
		return _InOrder(_root);
	}

	size_t Size()
	{
		return _size;
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			return false;//根为红，一定不是红黑树
		}

		int black = 0;//获取任意一条路径的黑色节点（这里是最左路）
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				black++;
			}

			cur = cur->_left;
		}

		return Check(_root, black, 0);
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		
		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}
	
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;//父亲的左
		Node* subLR = subL->_right;//左子树的右
		Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接

		parent->_left = subLR;//将左子树的右给父亲的做
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;//parent做左子树的右
		parent->_parent = subL;

		if (parent == _root)//parent是根
		{
			_root = subL;//此时的新根就是subL
			ppNode = nullptr;
		}
		else//parent不是根
		{
			//将新的根连接到ppNode
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;//父亲的右
		Node* subRL = subR->_left;//右子树的左
		Node* ppNode = parent->_parent;//parent的父节点,方便旋转后的链接

		parent->_right = subRL;//将右子树的左连接到parent的右
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;//parent连接到subR的左
		parent->_parent = subR;

		if (parent == _root)//parent是根
		{
			_root = subR;//此时的新根就是subR
			ppNode = nullptr;
		}
		else//parent不是根
		{
			//将新的根连接到ppNode
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}

	bool Check(Node* root, const int black, int num)
	{
		if (root == nullptr)
		{
			//当走到叶子节点的时候和其他路径的黑色节点的个数不一样
			if (black != num)
			{
				return false;
			}

			return true;
		}

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

		//遇到黑色节点++
		if (root->_col == BLACK)
		{
			num++;
		}

		//当前节点符合红黑树，它的左右子树也要都符合
		return Check(root->_left, black, num) && Check(root->_right, black, num);
	}


private:
	Node* _root;//根节点
	size_t _size;//节点的数量
};

红黑树的效率分析以及应用

红黑树和AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log_2 N)，红黑树不追 求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用

C++的STL库中的map/set/multimap/multiset底层都是红黑树实现的

一些Java的库；例如: TreeMap和TreeSet等

一些Linux的内核，例如：进程调度等

OK，本期分享就到这里，好兄弟，我们下期再见！

结束语：简单的事重复做，重复的是坚持做！