超详细红黑树的模拟实现

前言

有人说设计出AVL树的的人是个大牛，那写红黑树（RBTree）的人就是天才！
上一篇文章，我们已经学习了AVL树，牛牛个人认为AVL树已经够优秀了，那让我们一起探究一下，为什么红黑树比AVL树的结构还要优秀吧！

一、红黑树的介绍

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

红黑树，是一种自平衡的二叉查找树，它的性质比较复杂，但却非常重要，常用于C++中的STL库中的set、map等容器。红黑树的节点有两种颜色：红色（red）和黑色（black）。它具有如下五个性质：

1. 每个节点是红色或者黑色的。
2. 根节点是黑色的。
3. 每个叶子节点（这里特指最下面的空节点）是黑色的。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。（即：每条路径上不能出现连续的红结点）
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

由于红色结点的父亲必须是黑色结点，并且每条路径上的黑色结点的个数也必须相同，所以得到了红黑树最长路径中节点个数不会超过最短路径节点个数的两倍

这也就决定了，红黑树的高度是log（n）级别的。
例如，下面这个就是红黑树

二、手撕红黑树

2.1 框架结构分析

2.11 结点颜色

红黑树较于AVL树，不在使用平衡因子，而是增设了颜色变量，这里我们可以枚举出这两种颜色，方便使用。

	enum Colour	//枚举出颜色{RED,		//红色BLACK		//黑色};

2.12 结点类

同AVL树一样，红黑树也是三叉链

	//结点类template<class K, class V>struct RBTreeNode{//指针域RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;	//数据域Colour _Col;RBTreeNode(const pair<K, V>& kv)//构造函数:_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _Col(RED)				//注意这里，默认新构造的结点是红色的{}};

2.13 红黑树结构

	//红黑树的结构template<class K, class V>class RBTree{typedef RBTreeNode<K, V> Node;public:// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false//此版本红黑树对于重复元素，插入失败bool Insert(const pair<K, V>& kv);// 搜索红黑树中是否存在值为data的节点。//存在返回该节点的地址，不存在则返回nullptrNode* Find(const pair<K, V>& data);// 获取红黑树最左侧节点Node* LeftMost();// 获取红黑树最右侧节点Node* RightMost();//（这里的玩法大家应该不陌生了）	int Height();//计算红黑树的高度bool IsValidRBTRee();// 检测红黑树是否为有效的红黑树private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack);int Height(Node* root);// 左单旋void RotateL(Node* pParent);// 右单旋void RotateR(Node* pParent);// 为了操作树简单起见：获取根节点Node*& GetRoot();private:Node* _root = nullptr;};

2.2 接口实现

2.21 插入接口（重点）

本篇主要讲解的部分就是红黑树的插入操作。

函数名 ：	insert
返回值	插入成功，返回true；插入失败，返回false
形参	键值对

//插入函数
template<class K, class V>
bool RBTree<K, V>::Insert(const pair<K, V>& kv) {
}

（1）.如果是第一次插入，则插入的是根节点，则需要特殊处理，因为要给根节点root赋值。

在结点类中我们提到，在创建的新节点我们给与了默认颜色为RED（红色），而红黑树的根节点必须是BLACK（黑色）的，这里一定要记得修改一下颜色。

//第一次插入if (_root == nullptr) {_root = new Node(kv);_root->_Col = BLACK;		//注意根节点一定是黑色的，默认构造的新节点是红色的，所以这里要改一下。return true;}

(2) 寻找插入位置
红黑树也是二叉搜索树，学到这里，相信友友们在AVL树和二叉搜索树学习阶段，已经知道如何寻找插入位置。

	//寻找插入位置while (cur) {parent = cur;if (_root->_kv.first > kv.first) {cur = cur->_left;		//插入的值当前结点的值小，往左走}else if (_root->_kv.first < kv.first) {cur = cur->_right;		//插入的值当前结点的值大，往右走}else {return false;	//本篇实现的红黑树，对于重复值，插入失败}}//判断插入在左边还是右边cur = new Node(kv);if (kv.first < parent->_kv.first) {				//插入在左边parent->_left = cur;}else {									//插入在右边parent->_right = cur;}cur->_parent = parent;					//保证三叉链的关系

3.看uncle（叔叔）

叔叔（uncle）？这里我将当前结点的父亲（parent）的兄弟称为叔叔结点。

示例：

当我们新增一个结点时，默认新节点的颜色为RED，如果它的父亲结点是黑色的，则不需要做任何调整，直接插入成功！

当父亲结点是红色的时候，则与新增结点一起，会构成连续的红色结点，此时需要调整。

调整规则主要看uncle叔叔结点。

情况1： 父亲是爷爷的左，cur结点是父亲的左。 （左左）

👻情况：叔叔存在且为红
🔑调整方案： 变色+向上更新（图片为博主原创，请勿随意转发使用）

👻情况：叔叔不存在，或者存在且为黑
🔑调整方案： 右旋+变色

（图片为博主原创，请勿随意转发使用）

情况2： 父亲是爷爷的左，cur结点是父亲的右。 （左右）

👻情况：叔叔存在且为红
🔑调整方案： 变色+向上更新
（图片为博主原创，请勿随意转发使用）

👻情况：叔叔不存在，或者存在且为黑
🔑调整方案： 左右双旋+变色

示例图：

（图片为博主原创，请勿随意转发使用）

情况3： 父亲是爷爷的右，cur结点是父亲的左。 （右左）

👻情况：叔叔存在且为红
🔑调整方案： 变色+向上更新
这里不画图了，牛牛画累了。

👻情况：叔叔不存在，或者存在且为黑
🔑调整方案： 右左双旋+变色

（图片为博主原创，请勿随意转发使用）

情况4： 父亲是爷爷的右，cur结点是父亲的左。 （右右）

👻情况：叔叔存在且为红
🔑调整方案： 变色+向上更新
（图片为博主原创，请勿随意转发使用）

👻情况：叔叔不存在，或者存在且为黑
🔑调整方案： 左旋+变色
（图片为博主原创，请勿随意转发使用）

总结：
红黑树的插入主要看uncle
分为两种情况：
（1）uncle存在且为红
调整方案： 变色+继续向上调整
（2）uncle不存在或者uncle存在且为黑
调整方案： 旋转+变色

至于如何旋转，因为红黑树没有采用平衡因子的方式，所以我们采用判断grandfather与parent 和 parent与cur的关系结构来决定。
下图是具体调整总结：

总代码：

bool Insert(const T& kv) {if (_root == nullptr) {_root = new Node(kv);_root->_Col = BLACK;		//注意根节点一定是黑色的，默认构造的新节点是红色的，所以这里要改一下。return true;}Node* cur = _root, * parent = nullptr;//寻找插入位置while (cur) {parent = cur;if (_root->_kv.first > kv.first) {cur = cur->_left;}else if (_root->_kv.first < kv.first) {cur = cur->_right;}else {return false;}}//判断插入在左边还是右边cur = new Node(kv);if (kv.first < parent->_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) {//变色uncle->_Col=parent->_Col = BLACK;grandfather->_Col = RED;//继续向上更新cur = grandfather;parent = grandfather->_parent;}else {									//叔叔不存在或者 存在且为黑if (cur == parent->_left) {			//			g//		p//cRotateR(grandfather);grandfather->_Col = RED;parent->_Col = BLACK;}else {//		g//	p//		cRotateL(parent);RotateR(grandfather);cur->_Col = BLACK;grandfather->_Col = RED;}break;	//此时最顶端的结点已经变成黑色了，不需要继续向上更新了。}}else {		// 如果父亲是爷爷的右孩子Node* uncle = grandfather->_left;		//那么叔叔就是爷爷的左孩子//叔叔存在且为红if (uncle && uncle->_Col == RED) {//变色uncle->_Col = parent->_Col = BLACK;grandfather->_Col = RED;//继续向上更新cur = grandfather;parent = grandfather->_parent;}else {									//叔叔不存在或者 存在且为黑if (cur == parent->_left) {//	g//		p//	c//注意旋转时的传参RotateR(parent);RotateL(grandfather);grandfather->_Col = RED;cur->_Col = BLACK;}else {//	g//		p//			cRotateL(grandfather);		//注意旋转时的传参parent->_Col = BLACK;grandfather->_Col = RED;}break;	//此时最顶端的结点已经变成黑色了，不需要继续向上更新了。}}}_root->_Col = BLACK;		//最后根节点一定是黑的return true;}

2.22 最左侧结点（LeftMost）

对于二叉搜索树，如果我们按中序遍历，则可以得到一个有序序列。
中序遍历的首个结点： 最左侧结点
中序遍历的最后结点： 最右侧结点

	// 获取红黑树最左侧节点template<class K, class V>typename RBTree<K, V>::Node* RBTree<K, V>::LeftMost() {Node* left_most = _root;while (left_most->left) {left_most = left_most->left;}return left_most;}

2.23 最右侧结点（RightMost）

	// 获取红黑树最右侧节点template<class K, class V>typename RBTree<K, V>::Node* RBTree<K, V>::RightMost() {Node* right_most = _root;while (right_most->right) {right_most = right_most->left;}return right_most;}

2.24 检测函数（次重点）

在实现红黑树时，也许我们会遇到各种问题，好不容易跑通代码后，我们缺无法判断自己实现的红黑树是否正确，是否符合红黑树的规则。

此时，我们可以设计一个检测函数，检测实现的红黑树是否平衡。

1. 空树也是红黑树
2. 根节点必须是红黑树
3. 我们可以设置一个“基准值”，基准值为红黑树一条路径中的黑色结点的个数。
4. 遍历每条红黑树的路径，判断红黑树结点的个数，是否与基准值相等。
5. 除此之外，出现连续两个红色结点则返回false。

// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
template<class K, class V>
bool  RBTree<K, V>::IsValidRBTRee() {if (_root == nullptr)	//空树也是红黑树return true;if (_root->_Col != BLACK)	//根节点必须是红黑树{return false;}// 基准值int pathBlack = 0;Node* cur = _root;while (cur){if (cur->_Col == BLACK)++pathBlack;cur = cur->_left;}_IsValidRBTRee(_root, 0, pathBlack);
}template<class K, class V>
bool RBTree<K, V>::_IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {if (pRoot == nullptr){if (blackCount != pathBlack)		//一条路径走到底，也就是走到叶子结点以后，判断这条路径上的黑色结点个数（blackCount）是否与 设定的黑色结点个数相同（pathBlack）return false;return true;}if (pRoot->_Col == BLACK){++blackCount;}if (pRoot->_Col == RED && pRoot->_parent && pRoot->_parent->_Col == RED){cout << _root->_kv.first << "出现连续红色节点" << endl;return false;}//递归访问左右子树return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack)&& _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
}

2.25 获取根节点

	template<class K, class V>typename RBTree<K, V>::Node*& RBTree<K, V>::GetRoot() {return _root;}

2.25 获取红黑树的高度

	template<class K, class V>int RBTree<K, V>::Height(){return Height(_root);}template<class K, class V>int RBTree<K, V>::Height(typename RBTree<K, V>::Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);	//计算左子树的高度int rightHeight = Height(root->_right);	//计算右子树的高度return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}

2.26 find函数

template<class K, class T,>
typename RBTree<class K, class T, class Of_T>::Node* RBTree<class K, class T, class Of_T>::Find(const T& data) {Node* cur = _root;while (cur){if (data > cur->_data){cur = cur->_right;}else if (data < cur->_data){cur = cur->_left;}else return cur;}return nullptr;  // 找不到目标元素时返回nullptr
}

三、结语：

看完本篇文章，我们不难知道，对于插入操作，无论是红黑树还是avl树，要维持对应的“平衡”，会进行沿路径的更新，其中涉及大量的旋转操作，而红黑树较于avl树那种严格的高度差在-1到1之间，红黑树的平衡条件相对宽松，这也就大大减少了的为了维持平衡的大量旋转操作，而且还能保证效率在log（N），这也就是为啥说红黑树较于avl树更加优秀。
你赞同这个观点吗？

后续牛牛会模拟实现map和set，会在那篇文章封装红黑树，对红黑树进行改造，增加迭代器等功能。帮助友友们更加深入理解map和set容器。