一文理解吸收《红黑树》的精华

前言

在前面的学习中，我们是先自己实现了一个平衡二叉树，然后我们就介绍了stl两个容器map和set，但是我们并没有立即实现，这是因为他们的底层是红黑树我们当时还没有了解到。本章承接上文的AVL树，我们将开启学习一种特殊且流传广泛的数据结构————红黑树。学完本文，我们就可以自主模拟实现map和set！！！

红黑树

🎈红黑树的概念

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

🀄红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 （不能存在连续的红色节点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

其中最重要的就是性质3和性质4，我们后面自主实现红黑树也是在一直在围绕这两个性质来实现的！

还有一点要注意的是，这里的叶子节点并不是6、22、27等节点，而是下面的NIL，时刻注意这个NIL节点它永远是黑色的！！！

我们可以对每一条路径上的黑色节点进行统计，会发现每条路径的黑色节点数都是一样的！！

下面我们就来介绍红黑树插入的过程和处理细节问题：

🚀红黑树的插入过程：

默认插入节点是红色的

首先，我们需要了解一个概念，我们在实现插入的过程时，默认插入的节点是**红色的！**这里我们一定要记住这点！

减少平衡调整的复杂性：插入一个红色节点不太可能立即破坏红黑树的平衡性质。因为红黑树的平衡要求之一是：从根到每个叶子节点的黑色节点数必须相同。如果新插入的节点是红色的，它不会增加路径中的黑色节点数，从而不会直接破坏这个平衡性质。

容易满足红黑树的性质：红黑树有几个重要性质，包括：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色。
• 红色节点不能有红色子节点（即不允许两个连续的红色节点）。
• 从任意节点到其每个叶子节点的路径上必须包含相同数量的黑色节点。

默认插入红色节点，违反红黑树性质的情况较少，因此在后续的调整中更容易修复。

简化了旋转和重新着色的操作：如果插入时默认节点是黑色，那么可能会破坏从根到叶子路径的黑色节点数量一致性，从而导致更多的复杂调整。插入红色节点后，仅在局部情况下会需要进行旋转和重新着色操作，更容易控制。

保持树的平衡性：通过插入红色节点，红黑树可以更好地保持相对平衡，保证查找、插入和删除操作的时间复杂度为 $O(logn)$。

关于叔叔节点

关系到红黑树的操作，影响最大的就是叔叔节点。可以这么说，对红黑树的操作，是通过叔叔节点的状态来判断要如何操作，我们先来看看什么是叔叔节点。

如上图的12节点就是对于cur是叔叔节点，接下来我们就可以先来分类讨论情况了！

叔叔节点为红色时

我们先创建一颗简单的红黑树，如下图所示：

在这里为了方便描述，我省略掉了黑色的叶子节点NIL，在这颗树的基础之上，我现在新增节点4，既然是新增那必然是红色节点，然后又要满足二叉平衡树的性质，小的去左边，大的去右边，那么最终会插入到6的左孩子处，如下图所示：

很明显这个时候就会违背红黑树的第3条性质，即不能有连续的两个红色节点，因此我们就要在此处做处理！

处理的方式也很简单：

1. 判断叔叔节点是否是红色
2. 如果是红色，则parent节点和uncle节点变为黑色
3. grandparent节点变为红色
4. 让cur去到grandparent的位置，继续向上判断。

因为我们是在一棵简单的红黑树上进行判断的，所以我们的grandparent就是根节点了，而根节点必须是黑色的，但是在这里我们不用进行过多的判断，我们在编写代码的时候，只要在最后时刻不管出现什么情况都让根节点变为黑色就行了！

叔叔节点为空/为黑色

单旋

如上图所示，叔叔节点是一个空节点，那么针对这种情况很明显该红黑树破坏了性质3，不能存在连续的两个红色节点。

1. 判断叔叔节点的颜色
2. 为黑色则需要进行翻转
3. 将parent颜色至黑色，grandparent颜色至红色

双旋

还有一种情况需要我们考虑，就是如下图所示：

在这里我们就需要旋转两次了！

以上是针对uncle在grandparent右边的情况，而uncle在grandparent左边的情况与此次上面大差不差。在这里我也不做赘述了，学习最重要的是思路，如果你真的理解了我讲解的这个，那么剩下我没讲的相信对你不成大问题。

关于循环条件

我们在叔叔节点为红色时的情况下，仅仅只需要进行对节点的颜色进行改变，然后再让cur指向grandparent的节点处就好，随后就是不断地向上调整遍历判断。那我们在这里会有疑惑？什么时候该停下来呢不做判断呢？

其实这个条件很好想，我们刚开始画图的时候就不难发现，当parent为空时或者parent为黑色节点时，就代表着当前已经平衡了！我们就可以停下来了！！！

总结：

以上就是红黑树的插入过程，在这里我只是对插入进行了讲解，而至于删除则难度较高，在这里我也不做赘述了，感兴趣的同学可以下来自己学习学习。
其实我们在学习完红黑树后，会发现其实这是要比AVL树简单好实现的！正是因为它好实现，并且维护平衡的效率较高，这才是为什么在许多地方我们都能见到红黑树的影子。下一章我们将会讲解map和set的封装，map和set的封装会比较麻烦，到时候我们会对那部分进行细致的讲解，但前提是我们需要好好熟悉熟悉红黑树的性质，同时还需要对前面讲解的list时迭代器部分再进行回顾。

本章的我会给出，本次代码由于是为封装map和set的铺垫，所以我会给出KV模型：

代码：

#define _CRT_SECURE_NO_WARNINGS  1
#include <iostream>

using namespace std;

enum Colour
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
		, _kv(kv)
	{}

	Colour _col;
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
};

template<class K, class V>
class RBTree
{
public:
	typedef RBTreeNode<K, V> Node;

	bool Insert(const pair<K, V>& kv)
	{
		// 判断“根节点”是否为空
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			if (kv.first < cur->_kv.first)
			{
				// 小的去左边
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_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;

		// parent的颜色是黑色也结束
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					// 继续向上更新
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					// 叔叔不存在，或者为黑
					if (cur == parent->_left)
					{
						//       g
						//    p     u
						//  c
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						//       g
						//    p     u
						//      c
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					// 继续向上更新
					cur = grandparent;
					parent = cur->_parent;
				}
				else
				{
					// 叔叔不存在，或者为黑
					if (cur == parent->_right)
					{
						//      g
						//   u     p
						//           c
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						//      g
						//   u     p
						//       c
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
					break;
				}
			}

		}
		_root->_col = BLACK;
		return true;
	}

	void InOrder()
	{
		return _InOrder(_root);
		cout << "\n";
	}

	bool IsBanlance()
	{
		if (_root->_col == RED)
		{
			return false;
		}

		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++refNum;
			}

			cur = cur->_left;
		}

		return _IsValidRBTRee(_root, 0, refNum);
	}


private:

	// 这里并没有熟练掌握
	// 明天继续练习
	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
	{
		if (pRoot == nullptr)
		{
			if (pathBlack != blackCount)
			{
				cout << "存在黑色节点的数量不相等的路径" << endl;
				return false;
			}

			return true;
		}
		if (pRoot->_col == RED && pRoot->_parent->_col == RED)
		{
			cout << pRoot->_kv.first << "存在连续的红色节点" << endl;
			return false;
		}
		if (pRoot->_col == BLACK)	 blackCount++;

		return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack)
			&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
	}


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

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		Node* ppNode = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_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;

		subR->_left = parent;
		Node* ppNode = parent->_parent;

		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = subR;
			}
			else
			{
				ppNode->_left = subR;
			}
			subR->_parent = ppNode;
		}
	}

	// 为了操作树简单起见：获取根节点
	Node*& GetRoot()
	{
		return _root;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr) return;

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	Node* _root = nullptr;
};