[C++] 深入理解红黑树与代码实现-171主机测评

1. 红黑树的概念

红黑树是一颗二叉搜索树，具备二叉搜索树的所有性质。可以跳转至这篇文章了解二叉搜索树：

C++：深入理解二叉搜索树与代码实现

红黑树在二叉搜索树的基础上还具有以下性质：

只有红色和黑色两种节点

根节点为黑色

任何一条路径都不会出现连续的红色节点

任何一条路径上的黑色节点数量相同

红黑树在二叉搜索树的基础上，通过控制颜色来控制平衡，最长路径不超过最短路径的两倍。

为什么呢？根据性质4，极端场景下的最短路径全是黑色节点，假设最短路径是 b（black）；由规则2，3可知，极端场景下的最长路径为一黑一红节点间隔组成，那么最长路径为 2 * b；但并不是每一棵红黑树的最长 / 最短路径都符合以上的极端情况，因此，假设任意一条路径长度为x，那么 b <= x <= 2 * b 。请添加图片描述

2. 时间复杂度分析

假设N是红黑树中节点的数量，h是最短路径的长度，那么可以得出 2^h -1 <= N < 2^(2*h) -1 的结论，由此可以推断出 h 近似为 logN 。也就是说红黑树增删查改的最坏情况也就是走最长路径即 2 * logN ，时间复杂度的量级还是 O(logN)。请添加图片描述红黑树和AVL树都是通过不同的方式使二叉搜索树尽量平衡，因此他们的效率位于同一档次；且红黑树对平衡的控制没那么严格，因此旋转次数更少，C++的STL中也更多使用红黑树作为底层容器。

3. 红黑树的实现

3.1 红黑树的结构

节点：红黑树仅仅在平衡规则部分与AVL树不同，因此红黑树的节点中没有平衡因子，而是用颜色作为枚举值来表示。剩余成员和AVL树相同（父节点指针，左右孩子指针，key / value）。
树：红黑树的成员为根节点。

以下是以key / value为例的红黑树框架：

// 枚举值表示颜色
enum Colour
{
RED,
BLACK
};

// 这里我们默认按key/value结构实现
template<class K, class V>
struct RBTreeNode
{
// 这里更新控制平衡也要加入parent指针
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
{
private:
Node* _root = nullptr;
typedef RBTreeNode<K, V> Node;
public:
//…
};

3.2 红黑树的插入

红黑树的插入逻辑和二叉搜索树相同，即找到一个合适的空位置插入。插入后仅需观察颜色是否符合规则即可：

若为空树，插入的节点为根节点，颜色设置为黑，插入结束。

不为空树，插入的节点颜色设置为红，如果父节点为黑，则符合条件，插入结束；若父节点为红，则不满足规则3（不能出现连续的红色节点），需要向上调整颜色 / 旋转。

对于是否需要旋转，主要观察的是uncle节点，也就是父节点的兄弟节点，如图：在这里插入图片描述（插入的是x节点，parent节点为6，uncle节点为15，grandparent节点为10）

3.2.1 情况一：仅变色

当uncle节点存在且为红色时，仅需变色即可：在这里插入图片描述

如果grandparent节点的父节点仍然是红色，则一直向上更新；

如果父节点为黑色，则停止更新；

最坏情况是一路向上更新到了根节点，此时需要将根节点变为黑色，停止更新。

3.2.2 情况二：旋转 + 变色

当uncle节点不存在或者为黑色时，需要旋转 + 变色。

我们可以通过uncle节点的状态来推断cur节点的性质：如果uncle节点不存在，则cur节点一定是新增节点；如果uncle节点存在且为黑，则cur节点一定不是新增节点。假设法证明如下：在这里插入图片描述

旋转：究竟需要单旋还是双旋，判断条件和AVL树相同。即看cur，parent，grandparent节点是否在一条直线上，如果在，则单旋；否则双旋。
变色：要解决连续红色节点的问题，同时还要保证各条路径上的黑色节点数量相同，接下来我们具体情况具体分析。

⭕左单旋：

请添加图片描述当g，p，c节点呈一条直线，且p，c均为右孩子节点时，需要进行左单旋。旋转后p，c节点均为红色，为了避免出现连续红色节点，需要将p节点变为黑色，原先左边路径有两个黑色节点，为了保持一致，需要更改g的颜色为红色。

由于之前证明了c节点一定不是新增节点，因此旋转前每条路径的黑色节点个数是符合规则4（任意路径黑色节点数量相同）的，只需要保持原先路径的黑色节点数量不变即可，不需要改变c节点的颜色。

⭕右单旋：

右单旋的场景就是左单旋的水平翻转，变色规则相同：请添加图片描述

⭕左右双旋:

请添加图片描述当p为g的右孩子节点，c为p的左孩子节点时，需要进行左右双旋。旋转后p，c节点均为红色，为了保证没有连续的红色节点，并且路径上黑色节点数量一致，需要将c节点变为黑色，g节点变为红色。

⭕右左双旋：

右左双旋的场景就是左右双旋的水平翻转，变色规则相同：请添加图片描述

红黑树插入代码实现：

bool Insert(const pair<K, V>& kv)
{
//根
if(!_root)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}

//非根
Node* cur = _root;
Node* parent = nullptr;
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;

//旋转调整
while(parent && parent->_col = RED)
{
Node* grandfather = parent->_parent;

//p在g左
if(parent == grandfather->_left)
{
Node* uncle = grandfather->_right;

//u存在且为红->变色继续向上处理
if(uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;

cur = grandfather;
parent = grandfather->_parent;
}
else //u不存在或为黑
{
if(cur == parent->_left)
{
RotateR(grandfather);

parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);

cur->_col = BLACK;
grandfather->_col = RED;
}

break;
}
}
//p在g右
else
{
Node* uncle = grandfather->_left;
//仅变色
if(uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;

cur = parent;
parent = grandfather;
}
else //旋转 + 变色
{
if(cur == parent->_right)
{
RotateL(grandfather);

parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);

cur->_col = BLACK;
grandfather->_col = RED;
}

break;
}
}
}

//一律设置为黑
_root->_col = BLACK;

return true;
}

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

//1.parent和subLR
parent->_left = subLR;

if(subLR)
{
subLR->_parent = parent;
}

Node* parentParent = parent->_parent;

//2.parent和subL
parent->_parent = subL;
subL->_right = parent;

//3.subL和parentParent
if(parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if(parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}

subL->_parent = parentParent;
}
}

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

//1.parent和subRL
parent->_right = subRL;
if(subRL)
{
subRL->_parent = parent;
}

//2.parent和subR
Node* parentParent = parent->_parent;

parent->_parent = subR;
subR->_left = parent;

//3.subR和parentParent
if(parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if(parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}

subR->_parent = parentParent;
}
}

在写双旋代码的过程中，可以按照以下顺序实现，思路更清晰：

parent节点和subRL / subLR节点

parent节点和subR / subL节点

subR / subL节点和parentParent节点

3.3 红黑树的查找

按照二叉搜索树的规则查找即可，时间复杂度为O(logN)：

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

return nullptr;
}

4. 红黑树的验证

红黑树的验证主要根据四点规则开展，满足了规则就能保证最长路径不超过最短路径的两倍：

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

// 本期内容就到这里啦，如果对你有帮助，请三连支持！我是青云，我们下期见^_~

[C++] 深入理解红黑树与代码实现

1. 红黑树的概念

2. 时间复杂度分析