C++（初阶）（十九）—

红黑树

红黑树
- 概念
- 规则
- 实现
- - 结点
  - 插入
  - 变色
  - - 变色参考代码：
  - 查找
  - - 查找参考代码
  - 遍历
- 红黑树检查
- 完整代码

概念

红⿊树是⼀棵⼆叉搜索树。它的每个结点增加⼀个存储位来表示结点的颜⾊，可以是红色或者黑色（并不会出现第三种颜色）。

通过对结点颜色特别的规则进行约束，红黑树确保没有任何⼀条路径会比其他路径长出2倍，即保证最长路径（一黑一红）<= 最短路径*2（全黑），因此红黑树是接近平衡的。

规则

1，每个结点不是红色就是黑色。

2，根结点是黑色的。

3，如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点。

4，对于任意⼀个结点，从该结点到其所有空结点（NULL）的简单路径上，均包含相同数量的黑色结点。

5，最长路径（一黑一红）<= 最短路径*2（全黑）。

说明：《算法导论》等书籍上补充了⼀条每个叶⼦结点(NIL)都是黑色的规则。他这⾥所指的叶⼦结点不是传统的意义上的叶⼦结点，⽽是我们说的空结点，有些书籍上也把NIL叫做外部结点。NIL是为了⽅便准确的标识出所有路径，《算法导论》在后续讲解实现的细节中也忽略了NIL结点，所以我们知道⼀下这个概念即可

实现

结点

// 枚举值表⽰颜⾊
enum Colour
{RED,BLACK
};// 这⾥我们默认按key_value结构实现
template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;//这⾥更新控制平衡也要加⼊parent指针RBTreeNode<K, V>* _parent;Colour _col;//构造RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(BLACK){}
};

插入

首先实现最简单的插入操作。

1，首先判断是否是空树，因为空树也是红黑树。如果是空树，创建新节点，颜色是黑色（根节点必须是黑色），返回即可。

2，查找我们数据应该插入的位置，查找规则和二叉搜索树一样。比当前结点大，再去和右孩子的结点比较；比当前结点小，再去和左孩子的结点比较；即大就向右走，小就向左走，直到找到空，执行插入操作。

3，不是空树，创建新增结点，默认颜色是红色。为什么不给黑色，仔细分析红黑树的规则发现：如果新增结点是黑色的话，那么就可能会破坏其他简单路径上黑色结点数量，造成简单路径黑色结点的数量不相等。所以默认是红色结点，这样更方便。

那是否可以将全部结点都设置为黑色呢？按照红黑树的规则来看，逻辑上没有问题，但是这样的红黑树就失去了原本意义，全部都是黑色结点和二叉搜索树没有区别，而且还浪费了存储颜色的额外空间。

4，最简单的情况是，新节点的父亲结点是黑色，则插入成功后就结束。

但是如果父亲结点是红色，那么插入新节点后就需要进行变色处理，原因是红黑树不会存在连续的红色结点，变色处理稍微麻烦，放到后边位置详细说明。

参考代码：

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);return true;}//记录cur的父结点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;}else{parent->_left = cur;}cur->_parent = parent;return true;}private:Node* _root = nullptr;
};

变色

前面分析过，如果新节点的父亲结点存在且为红色，那么需要对祖先结点进行变色。

但是变色依旧有多种情况，需要分别讨论。

为了方便使用缩写展示：g代表grandfather，p代表parent，u代表uncle，c代表cur即新结点。

1，

父亲结点存在且为红色
此时的父亲结点是爷爷结点的左孩子
叔叔结点存在并且为红色

在这里插入图片描述

此时经过分析得到，我们需要对父亲结点进行变色处理，以下是参考过程：

将父亲和叔叔结点颜色变黑，爷爷结点颜色变红
注意：为了防止此处将根结点也变为红色，所以在最后一处_root->_col = RED
如果此时符合红黑树的规则，那么即可结束，反之向上更新结点，直到结束。

//更新结点位置，向上更新
cur = grandfather;
parent = cur->_parent;

2，

父亲结点存在且为红色
此时的父亲结点是爷爷结点的左孩子
叔叔结点不存在或者存在且为黑色

此时需要进行变色+旋转处理。

但是旋转时又有所差异：如果cur是parent的左孩子（如下图），需要以grandfather为旋转点进行右单旋；

如果cur是parent的右孩子（如下图），需要先以parent为旋转点左单旋，再以grandfather为旋转点进行右单旋的左右双旋，最后要记得将旋转后的cur改为黑色，grandfather改为红色。

3，

父亲结点存在且为红色
此时的父亲结点是爷爷结点的右孩子
叔叔结点存在且为红色

与情况1类似不再赘述。

4，

父亲结点存在且为红色
此时的父亲结点是爷爷结点的右孩子
叔叔结点不存在或者存在且为黑色

与情况2类似不再赘述。

变色参考代码：

		//变色处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//  g//p   uif (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔叔结点存在，并且为红色if (uncle && uncle->_col == RED){//将父亲和叔叔结点颜色变黑，爷爷结点颜色变红//为了防止此处将根结点也变为红色，所以在最后一处_root->_col = REDparent->_col = uncle->_col = BLACK;grandfather->_col = RED;//更新结点位置，向上更新cur = grandfather;parent = cur->_parent;}//叔叔结点不存在，或者存在并且为黑色//变色+旋转else{//    g//  p   u//cif (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//cur == parent->_rightelse{//    g//  p   u//    c//双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//    g//  u   p//parent == grandfather->_rightelse{Node* uncle = grandfather->_left;//叔叔结点存在，并且为红色if (uncle && uncle->_col == RED){//将父亲和叔叔结点颜色变黑，爷爷结点颜色变红//为了防止此处将根结点也变为红色，所以在最后一处_root->_col = REDparent->_col = uncle->_col = BLACK;grandfather->_col = RED;//更新结点位置，向上更新cur = grandfather;parent = cur->_parent;}//叔叔结点不存在，或者存在并且为黑色//变色+旋转else{//    g//  u   p//		   cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//cur == parent->_leftelse{//    g//  p   u//    c//双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;

查找

查找很简单，与二叉搜索树的查找规则一样。

即要查找的cur结点的值大于根结点就向右走，比当前结点小就向左走，直到查找到或者走到空为止。

查找参考代码

//查找
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;
}

遍历

因为红黑树是二叉搜索树，所以使用中序遍历即可。

//中序遍历
void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);
}

红黑树检查

对红黑树检查时，可以从红黑树的规则入手。

1，每个结点不是红色就是黑色。

2，根结点是黑色的。

3，如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红色结点。

4，对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点。

对于规则1，我们在实现时，使用的就是红色和黑色的枚举，不可能出现其他颜色。

对于规则2，也很好判断，加一句判断语句即可。

对于规则3，前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检查⽗亲的颜⾊就⽅便多了。

对于规则4，前序遍历，遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可。

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);
}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);
}