【C++】红黑树的实现详解

        本篇来详细说一下红黑树。红⿊树是⼀棵⼆叉搜索树，AVL树是通过平衡因子控制树的平衡，红黑树就是通过颜色控制平衡，听起来比较抽象，但是这比AVL树学起来简单一点点。并且看这篇文之前我默认大家已经看过我写的AVL树的实现的博文：【C++】AVL树的概念及实现

 1.红黑树的概念

1.1 红黑树的规则

红⿊树的规则：

1. 每个结点不是红⾊就是⿊⾊。
2. 根结点必须是⿊⾊的。
3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点。（黑色节点的孩子可以是红的，也可以是黑的）
4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点。

 上图就是两颗红黑树，还有非常均衡的满二叉树红黑树，也有全黑的，都是符合规则的红黑树。

结合前面提到的4点规则，看着图理解。 

这里再强调一下路径怎么数。拿下面这颗树举例，这颗树的路径有9条，不是4条！不是算到叶子节点就完事了！

有的书上还会像下面这么画红黑树。

1.2 思考红⿊树如何确保最⻓路径不超过最短路径的2倍的？

• 由规则4可知，从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就是全是⿊⾊结点的路径，假设最短路径⻓度为bh(black height)。
• 由规则2和规则3可知，任意⼀条路径 不会有连续的红⾊ 结点，所以极端场景下， 最⻓ 的路径就是 ⼀⿊⼀红间隔 组成，那么最⻓路径的⻓度为 2*bh 。
• 综合红⿊树的4点规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为h，那么bh <= h <= 2*bh。

从这里就能看出来，红黑树那几个规则单看觉得莫名其妙，组合起来真是妙不可言。

1.3 红黑树的效率

假设N是红⿊树树中结点数量，h是 最短 路径的⻓度，那么− 1 <= N <  − 1，

由此推出 ，也就是意味着红⿊树增删查改 最坏 也就是⾛最⻓路径 2*log N  ，那么时间复杂度还是O(log N)。

红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜⾊约束，间接的实现了 近似平衡 ，他们效率都是 同⼀档次 的，但是相对⽽⾔，插⼊相同数量的结点 ，红⿊树 的 旋转次数是更少的 ，因为他对平衡的控制没那么严格。

 2.红黑树的实现

实现之前新建一个头文件RBTree.h，再新建一个源文件test.cpp。

2.1 红黑树的结构

在RBTree.h中实现。因为红黑树要表示颜色，所以我们用一个枚举。

// 枚举值表⽰颜⾊
enum Colour
{
	RED,
	BLACK
};

然后其他部分跟AVL树的结构差不多，就是把AVL树的平衡因子换成这个颜色。

template <class K, class V>
class 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)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	//相关实现

private:
	Node* _root = nullptr;
};

2.2 红黑树的插入

插⼊⼀个值先按⼆叉搜索树规则进⾏插⼊，插⼊后我们只需要观察是否符合红⿊树的4条规则。

插入时，新增节点应该是黑色还是红色？红色黑色都可以吗？并不是都可以。

• 如果是空树插⼊，新增结点是⿊⾊结点（根节点）。
• 如果是⾮空树插⼊，因为⾮空树插⼊，新增⿊⾊结点就破坏了规则4，规则4是很难维护的，所以新增结点必须红⾊结点。

分析一下为什么插入红色节点就可以。 

1. ⾮空树插⼊后，新增结点是红⾊结点，如果⽗亲结点是⿊⾊的，则没有违反任何规则，插⼊结束。
2. ⾮空树插⼊后，新增结点是红⾊结点，如果⽗亲结点是红⾊的，则违反规则3。此时要进⼀步分析，c是新增节点，为红⾊，p为红，g必为⿊，这三个颜⾊是固定的，关键的变化看u的情况。

 现在需要根据u分为以下⼏种情况分别处理。

2.2.1 只变色 不旋转

u存在且为红：

这是g的父亲节点为黑的情况，为黑更新就结束了，但是因为g是黑色，g的父节点（不为根节点的情况下）还可能是红色。如果是红色，就会又有连续红节点的情况。

此时我们需要继续向上更新，把此时的g当作新的c，一步一步更新。

上面是一些具体的例子，我们换成抽象图来看一下。

如果要继续向上更新的话，原来的g变成新的c过程也是一样的。

 u存在且为红的情况就说完了。

u不存在：

按照这种变色方式就会违反规则。

因为这导致如下绿色标记的路径上只有1个黑色节点，别的路径都是2个。（ 要切记路径是要走到nullptr）

这种情况下我们就要进行旋转了。

2.2.2 单旋+变色

u不存在：

可以进行一个单旋后再变色。

这样操作后，每条路径上的黑色节点就一样多了。

u存在但是为黑：

在这种情况下也需要进行单旋+变色。

此时c在这种情况下必须是存在且为黑，如果不为黑的话，不同路径上的黑色节点数就不相同。

但是我们新增的节点一定是红色，证明此时的c，也就是x节点，不是新增节点，这个黑色节点有可能是因为在a或b插入节点，让a和b的根也就是x节点变成了黑色，也有可能是本来就是黑色，反正他就是要为黑。

触发单旋+变色情况的话，就是让这个本来就是黑色的x节点，由于之前的变换由黑色变成了红色。

解决方法就是：以10为旋转中心进行右旋，然后让p变黑，g变红。

上面这种情况是u为g的右子树，并且c是p的左子树，如果u是g的左子树，我们就以g为旋转点进行左旋就好了。

这还有一个更细节的展开图。

前面说的都是会触发单旋的情况，因为g、p、c在一边，如果g、p、c不在同一边，就会触发双旋+变色的情况。

2.2.3 双旋+变色

u不存在：

u不存在的情况如图。

c为新增，我们可以选择对g这个节点进行左右双旋，也可以选择先对p节点进行左单旋，然后对g节点右单旋，结果都是一样的，这里主要体现在代码实现上。

u存在且为黑：

这里触发双旋+变色的情况和单旋那里一样，在u存在且为黑的条件下c必须也为黑，此时的c同样不是新增节点，理由同上。

 更详细的图可以看一下。

2.2.4 代码实现

在RBTree类中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->_left;
		}
		else if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else return false;
	}
	cur = new Node(kv);
	cur->_col = RED;  //新插入节点为红色
	if (cur->_kv.first < parent->_kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;
}

然后就是变色的逻辑，因为可能存在一直向上更新的情况，所以这里用了一个while。

bool insert(const pair<K, V>& kv)
{
	//...
    //上面是插入逻辑

	while (parent && parent->_col == RED) //循环控制
	{
		Node* grandfather = parent->_parent;//先定义祖父节点
	}
}

然后定义u节点，u节点可能是g节点的左，也可能在g的右，分情况定义。

bool insert(const pair<K, V>& kv)
{
	//...
    //上面是插入逻辑

	while (parent && parent->_col == RED) //循环控制
	{
		Node* grandfather = parent->_parent;//先定义祖父节点
        if (parent == grandfather->_left) //p为左，u为右
        {
        	Node* uncle = grandfather->_right;
        }
        else //p为右，u为左
        {
        	Node* uncle = grandfather->_left;
        }

	}
}

我们先看u为右的情况。

只变色不旋转

如果只需要变色，不用旋转，代码如下。

bool insert(const pair<K, V>& kv)
{
	//...
    //上面是插入逻辑

	while (parent && parent->_col == RED) //循环控制
	{
		Node* grandfather = parent->_parent;//先定义祖父节点
        if (parent == grandfather->_left) //p为左，u为右
        {
        	Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) //u存在且为红
            {
				parent->_col = BLACK; //u和p变黑
				uncle->_col = BLACK;
				grandfather->_col = RED;//g变红

				cur = grandfather; //继续向上更新
				parent = cur->_parent;
            }

        }
        else //p为右，u为左
        {
        	Node* uncle = grandfather->_left;
        }

	}
}

然后就是u不存在或者u存在且为黑的情况，这种情况需要用到旋转的代码。这里旋转的代码和AVL树的旋转代码大差不差，旋转相关的讲解也在【C++】AVL树的概念及实现（图文超详解），这里就直接用了。

左单旋和右单旋代码

void rotateR(Node* parent) //右单旋
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;
	if (subLR) //防止对空指针解引用
		subLR->_parent = parent;

	Node* pParent = parent->_parent; //先记录旋转前parent的父节点

	subL->_right = parent;
	parent->_parent = subL;
	if (pParent == nullptr) //旋转前parent为根节点
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else //旋转前parent不为根节点
	{
		subL->_parent = pParent;
		if (pParent->_left == parent)
		{
			pParent->_left = subL;
		}
		else
		{
			pParent->_right = subL;
		}
	}
}

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

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

	Node* pParent = parent->_parent; //记录parent的_parent
	subR->_left = parent;
	parent->_parent = subR;

	if (pParent == nullptr)//更新前的parent是整棵树根节点
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		subR->_parent = pParent;

		if (pParent->_left == parent)
			pParent->_left = subR;
		else
			pParent->_right = subR;
	}
}

这里的旋转和AVL树唯一不同的就是，这里不需要平衡因子。并且我这里实现的是单旋两次的方式，所以只需要单选代码就行了。

单旋+变色

bool insert(const pair<K, V>& kv)
{
	//...
    //上面是插入逻辑

	while (parent && parent->_col == RED) //循环控制
	{
		Node* grandfather = parent->_parent;//先定义祖父节点
        if (parent == grandfather->_left) //p为左，u为右
        {
        	Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) //u存在且为红
            {
				parent->_col = BLACK; //u和p变黑
				uncle->_col = BLACK;
				grandfather->_col = RED;//g变红

				cur = grandfather; //继续向上更新
				parent = cur->_parent;
            }
            else  //u不存在 或 u存在且为黑
            {
				if (cur == parent->_left) //单旋
				{
					rotateR(grandfather);//以g为旋转点右旋
					parent->_col = BLACK;  //变色
					grandfather->_col = RED;
				}
				
            }

        }
        else //p为右，u为左
        {
        	Node* uncle = grandfather->_left;
        }

	}
}

双旋+变色

else //u不存在 或 u存在且为黑
{
	if (cur == parent->_left) //单旋
	{
		rotateR(grandfather);//以g为旋转点右旋
		parent->_col = BLACK;  //变色
		grandfather->_col = RED;
	}
	else //双旋
	{
		rotateL(parent); //先对p左旋
		rotateR(grandfather);//再对g右旋
		//变色
		cur->_col = BLACK;
		grandfather->col = RED;
	}
    break;
}

到这里我们u为g右子树的情况就处理好了，然后我们来写u为g左子树的情况。

u为g左子树的情况

所有代码实现逻辑和u为右子树是一样的，只不过旋转的方向相反而已。

bool insert(const pair<K, V>& kv)
{
	//...
    //上面是插入逻辑

	while (parent && parent->_col == RED) //循环控制
	{
		Node* grandfather = parent->_parent;//先定义祖父节点
        if (parent == grandfather->_left) //p为左，u为右
        {
            //这里是u为右逻辑
            //...
        }
        else //p为右，u为左
        {
        	Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED) //u存在且为红
            {
				parent->_col = BLACK; //p和u变黑
				uncle->_col = BLACK;
				grandfather->_col = RED;//g变红

				cur = grandfather; //继续向上更新
				parent = cur->_parent;
            }
            else //u不存在 或 存在且为黑
            {
				if (cur == parent->_right) //单旋
				{
					rotateL(grandfather);//以g为中心左旋
					parent->_col = BLACK; //p变黑
					grandfather->_col = RED;//g变红
				}
				else //双旋
				{
					rotateR(parent);//先以p为中心右旋
					rotateL(grandfather);//再以g为中心左旋
					cur->_col = BLACK; //c变黑
					grandfather->_col = RED;//g变红
				}
				break;
            }
        }

	}
}

在最后加上这句代码。不管怎么变色，根都是黑色，直接加上这句也不用分情况讨论根节点情况了。最后返回true。

到这里插入的代码就写好了。

2.3 红黑树的查找  

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < key)
		{
			cur = cur->_right;
		}
		else if (cur->_kv.first > key)
		{
			cur = cur->_left;
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}

 下面给了有几个代码可进行验证。

在RBTree类中private实现。

bool Check(Node* root, int blackNum, const int refNum)
{
	if (root == nullptr)
	{
		// 前序遍历走到空时，意味着⼀条路径走完了
		//cout << blackNum << endl;
		if (refNum != blackNum)
		{
			cout << "存在黑色结点的数量不相等的路径" << endl;
			return false;
		}
		return true;
	}
	// 检查孩子不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲就方便多了
	if (root->_col == RED && root->_parent->_col == RED)
	{
		cout << root->_kv.first << "存在连续的红⾊结点" << endl;
		return false;
	}
	if (root->_col == BLACK)
	{
		blackNum++;
	}
	return Check(root->_left, blackNum, refNum)
		&& Check(root->_right, blackNum, refNum);
}

上面的代码是用一个形参 blackNum 记录当前路径的黑色节点数量，refNum是一个参考值，就是随便一条路径的黑色节点数量，refNum和blackNum进行对比，不一样就返回false。

所以我们要先计算出一条路径的黑色节点数量，然后调用Check这个函数。

在RBTree类中public实现。

bool IsBalance()
{
	if (_root == nullptr)
		return true;
	if (_root->_col == RED)
		return false;
	// 参考值
	int refNum = 0;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
		{
			++refNum;
		}
		cur = cur->_left;
	}
	return Check(_root, 0, refNum);
}

我们还要用到中序遍历。 

void Inoder() //中序遍历
{
	_Inorder(_root);
	cout << endl;
}

下面这个代码在RBTree类中private实现。

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

然后我们到test.cpp里测试，测试样例如下。

#include "RBTree.h" //包含头文件
int main()
{
	RBTree<int, int> t;
	// 常规的测试⽤例
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };

	// 特殊的带有双旋场景的测试⽤例
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.insert({ e, e });
	}
	t.Inoder();
	cout << t.IsBalance() << endl;
	return 0;
}

先测常规用例。

 再测特殊用例。

都通过了测试，这个红黑树就实现好了。

红黑树的删除部分在这里就不实现了，有兴趣的可参考：《算法导论》或者《STL源码剖析》中讲解。 

本次分享就到这里了，我们下篇再见~