C++:红黑树_c++ 红黑树

红黑树的概念

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

 红黑树的性质

⭐1.每个节点不是红色就是黑色。

⭐2.根节点是黑色的。

⭐3.如果一个节点是红色的，则它的两个孩子结点是黑色的。也就意味着，红黑树没有连续的红色节点。

⭐4.对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。也就是说每条路径都有相同数量的黑色节点。

⭐5.每个叶子结点都是黑色的(此处的叶子结点指的是空结点。

从性质上分析红黑树的近似平衡

一颗红黑树最短的路径是这条路径全黑。最长是一红一黑相间路径。

对于近似平衡来说：

①最优情况就是左右平衡，此时每条路径都是全黑或者是一红一黑相间，形成满二叉树。

②差的情况就是左右越不平衡，情况就越差。比如左子树全黑，而右子树是一黑一红相间。假设左子树全黑的路径长度位h = logN，因为红黑树要求每条路径的黑色节点的数量是相同的，而右子树是一红一黑相间的，那就说明右子树的长度是左子树的两倍h = 2*logN，这是最差的情况了，再差点就不是红黑树了。

红黑树节点的定义

红黑树节点的定义，跟AVL树的区别就是红黑树不需要平衡因子，而加入了颜色红跟黑。在定义当中，构造函数初始化列表对颜色_col默认初始化为红色是因为权衡了上面所述红黑树性质中的性质3和性质4。

性质3是说明了红黑树没有连续的红色节点，性质4说明的是每条路径都有相同数量的黑色节点。我们在定义节点的时候，需要给节点的颜色初始化，要么是红色，要么是黑色。

如果我们选择了黑色，那么在插入新节点之前，我们是往红黑树插入的嘛，本身就是红黑树，再插入一个黑色节点的话，那么必定会破坏掉红黑树的规则，是一定被破坏掉的，那么就一定需要对这颗红黑树进行调整。

如果我们选择红色，那么有可能会破坏掉红黑树的规则，也可能不会造成破坏。因为新增的节点的父节点是黑色的，那么就不会造成影响，而父节点是红色的话，那就需要调整。

因此，综上所述，默认初始化为红色是比较好的选择。

//使用枚举
enum Colour
{
	RED,
	BLACK,
};
 
template<class K,class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;
 
	RBTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)  //跟AVL树一样，使用parent节点是为了旋转
		,_col(RED)  //默认是红色
	{}
};

红黑色的插入操作

红黑树是在二叉搜索树的基础上加入了平衡限制条件的树，因此红黑树的插入分为两步：

第一步：按照二叉搜索树的规则插入新节点。

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

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

本文约定好：cur为当前节点，p（parent）为父节点，g（grandther）为祖父节点，u(uncle)为叔叔节点。

①cur为红，p为红，g为黑，u存在且为红

这种情况是插入的节点cur是红色的（默认），cur的双亲节点和叔叔节点是红色的，祖先节点是黑色的。因为不能连续存在红色节点，那么就需要把颜色调整一下即可，不需要旋转。

调整的方法为：将p节点和u节点的颜色改成黑色，同时为了防止g不是一棵单独的树，先把它变成红色，再进行判断，如果是单独的树，那么就把g的颜色变回黑色，如果是一棵子树，那么就往上继续调整。

②cur为红，p为红，g为黑，u不存在/u存在且为黑

这种情况下是需要旋转+变色的。因为当cur为红色，p为红色，g为黑色，而u的情况是：

如果u不存在，cur肯定是新增的节点，因为在新增之前，p和g组成的树是一棵红黑树，在cur新增之后，不符合红黑树的性质。

这种情况下光凭变色是解决不了问题的，因为u为空说明有一条路径只有根节点，而另一条路径上会存在连续红，只凭变色，无论怎么变，都会导致各路径的黑色节点数量不相同，所以需要先根据p和cur的位置来决定旋转的方向而旋转，再变色。

如果u存在，则u是黑色，并且cur原本的颜色一定是黑色的，而现在cur的颜色是红色，那就肯定是第一种情况调整后，导致了现在的cur的颜色变了。

这种情况下就跟u不存在的情况一样，采用旋转+变色来解决问题。此时，u存在不存在已经没什么关系了（单独是看构造红黑树的情况来说）。

③cur为红，p为红，g为黑，u不存在/u存在且为黑

这种情况的颜色是跟情况二的一样，区别就是节点的位置不一样。

这种情况是跟第二中情况差不多，就是多了一步旋转，先左旋再右旋，或者先右旋再左旋。

整体代码如下：

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->_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);
		cur->_col = RED;//多写一步，防止写错代码。
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
 
		//创建完二叉搜索树
		//开始创建红黑树，使用颜色来判断是否需要调整
		//循环往上走，循环条件：当走到的parent不为空，并且parent是红色的
		//即我们列举是三种情况，parent都是红的，就需要重新调整
		//如果parent是黑色的，那就不需要了。直接就是一棵红黑树,不进入循环
		while (parent && parent->_col == RED)
		{
			//保存祖先节点，即g节点
			Node* grandfther = parent->_parent;
			//判断父节点是在祖先节点的哪边
			if (parent == grandfther->_left)
			{
				//父节点在左边，那么叔叔节点就在右边
				Node* uncle = grandfther->_right;
				//情况一：uncle存在且为红。改变颜色即可
				if (uncle && uncle->_col == RED)
				{
					//变色。
					parent->_col = uncle->_col = BLACK;
					grandfther->_col = RED;
 
					//往上走
					cur = grandfther;
					parent = cur->_parent;
				}
				else  //uncle不存在 或者 存在但是黑色
				{
					//情况二  p是g的左孩子，cur是p的左孩子，以g为轴右单旋
					if (cur == parent->_left)
					{
						//右单旋
						RotateR(grandfther);
						//变色  右单旋后，parent为根节点，变黑色。cur和g节点为红色
						parent->_col = BLACK;
						grandfther->_col = RED;
					}
					else  //情况三  p是g的左孩子，cur是p的右孩子.
					{
						//先以p为轴左旋转
						RotateL(parent);
						//变成情况二，再以g为轴右单旋
						RotateR(grandfther);
						//变色  cur变成根节点，为黑色。p和g是红色
						cur->_col = BLACK;
						grandfther->_col = RED;
 
					}
 
					break;
				}
			}
			else  //parent是在grandfther的右边
			{
				//叔叔节点就在祖先节点的左边
				Node* uncle = grandfther->_left;
				//情况一：uncle存在且为红。改变颜色即可
				if (uncle && uncle->_col == RED)
				{
					//变色。
					parent->_col = uncle->_col = BLACK;
					grandfther->_col = RED;
 
					//往上走
					cur = grandfther;
					parent = cur->_parent;
				}
				else  //uncle不存在 或者 存在但是黑色
				{
					//情况二  p是g的右孩子，cur是p的右孩子。
					if (cur == parent->_right)
					{
						//左单旋
						RotateL(grandfther);
						//变色  右单旋后，parent为根节点，变黑色。cur和g节点为红色
						parent->_col = BLACK;
						grandfther->_col = RED;
					}
					else  //情况三  p是g的右孩子，cur是p的左孩子.
					{
						//先以p为轴右旋转
						RotateR(parent);
						//变成情况二，再以g为轴左单旋
						RotateL(grandfther);
						//变色  cur变成根节点，为黑色。p和g是红色
						cur->_col = BLACK;
						grandfther->_col = RED;
 
					}
 
					break;
				}
			}
		}
		//最后将根节点置为黑
		_root->_col = BLACK;
		return true;
	}
 
	void RotateR(Node* parent)
	{
 
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		Node* ppNode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;
 
		if (ppNode == nullptr)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else  
		{
			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;	
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
 
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (ppNode == nullptr)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
 
	}
 
private:
		Node* _root = nullptr;
};

旋转请看：AVL树这篇文章有详细解析。红黑树的旋转直接复用AVL树的旋转的代码即可。

验证红黑树

红黑树的验证分两步：①通过中序遍历验证其是否满足二叉搜索树的性质。②验证是否满足红黑树的性质。

中序遍历：

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

验证红黑树的性质：

验证思路：

①首先判断根节点的颜色是否为黑色，如果不是黑色，那就直接否定false。这一步是在验证红黑树的性质之一：根的颜色是黑色的。

②接着随便选一条路径并统计这条路径上的黑色节点的数量。

③拿着统计好的结果，去遍历其它路径各自的黑色节点的数量是否与这个结果相等，但凡有一条结果不一样，直接false这一步是在验证红黑树的性质之一：每条路径上的黑色节点是数量是相等的。

④在验证③的过程中，如果发现当前节点与父节点都是红色的，直接false。这一步是验证红黑树的性质之一：不能出现连续的红色节点。

代码如下：

	//遍历其它路径
	bool Check(Node* root, int blackNum, const int ref)
	{
		//当走到空节点后，就可以对比数量
		if (root == nullptr)
		{
			//选择打印数量，看看结果对不对
			cout << blackNum << endl;
			//如果不相等，false
			if (blackNum != ref)
			{
				cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
				return false;
			}
 
			return true;
		}
 
		//判断当前节点跟它的父亲节点是否都是红的
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续红色节点" << endl;
			return false;
		}
 
		//如果节点是黑色的，++
		if (root->_col == BLACK)
		{
			++blackNum;
		}
 
		//通过递归，去遍历其它的路径
		return Check(root->_left, blackNum, ref)
			&& Check(root->_right, blackNum, ref);
	}
 
	bool IsBalance()
	{
		//首先看看是不是空树，空树也是红黑树
		if (_root == nullptr)
		{
			return true;
		}
 
		//判断根节点是否为黑色，不是黑色就false
		if (_root->_col != BLACK)
		{
			return false;
		}
 
		//统计某一条路径的黑色节点的数量
		int ref = 0;
		//这里选择最左边的路径
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				//当节点是黑色，就++一下
				++ref;
			}
 
			left = left->_left;
		}
 
		//去寻找别的路径上的黑色节点
		return Check(_root, 0, ref);
	}

红黑树与AVL树的对比

⭐相同点：红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log_2 N)。

⭐不同点：红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言降低了插入和旋转的次数。而AVL树是高度平衡的二叉搜索树，旋转的次数比红黑树的要频繁。

所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

也就是因为红黑树在修改操作方面的性能比AVL树好，因此红黑树都用在了C++的STL库(map/set、mutil_map/mutil_set)，Java库、Linux内核等等地方。