【高阶数据结构】红黑树详解
前言
<font color = black>这篇文章我们再来学习一种平衡搜索二叉树——红黑树
1. 红黑树的概念及性质
1.1 红黑树的概念
<font color = "#000066">红黑树（Red-Black Tree）也是是一种自平衡的二叉搜索树，与AVL树不同的是它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍（最长路径也不会超出最短路径的两倍，因此红黑树的平衡性要求相对宽松，没有AVL树那样严格），从而使搜索树达到一种相对平衡的状态。
1.2 红黑树的性质
红黑树具有以下特点
<font color = blue>每个结点不是黑色就是红色
<font color = blue>根结点必须是黑色的
<font color = blue>红色结点的两个子结点必须都是黑色的，这保证了没有两个连续的红色节点相连
<font color = blue> 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也被称为NIL节点)
<font color = blue>任意结点到其每个叶子结点的简单路径上，黑色节点的数量相同：确保了树的黑平衡性，即红黑树中每条路径上黑色结点的数量一致。
大家可以对照着看一下上面的图，看它是否满足这些性质。
思考：为什么满足上面的性质，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍？（其实不带第4条就可以，加不加第4条都不会影响每条路径黑色结点数量是否相等）
<font color = "#000066">那通过上面的性质我们可以得知，红黑树中的结点要么是黑色，要么是红色，这没什么可说的；然后要求根结点一定是黑色的，红色结点不能连续出现，如果出现了红色结点，那它的子结点必须是黑色的，然后还要求每条路径黑色结点的数量必须相等。 那这样其实就可以保证一棵红黑树中最长路径不超高最短路径的两倍。 当然实际中不同的红黑树情况是不一样的，所以我们这里来分析一种极端的情况： 大家想，如果一棵红黑树有红有黑，它里面如果有一条全黑的路径，那这条全黑的路径一定就是最短路径； 如果有一条是一黑一红，一黑一红...，这样黑红相间的，那他就是最长的路径。 然后它们里面的黑色结点个数又是相同的的，所以最长路径最多是最短路径的两倍，不可能超过最短路径两倍。 所以这样红黑树的高度就能够保持在一个相对平衡的范围内，当然他就没有AVL树那么严格。 比如这样的
那另外:
<font color = black>其实分析上面的性质，红黑树是可以全黑的，全部黑色结点，只要满足上面的性质即可。
然后大家思考一个问题，上面第四条性质——每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也被称为NIL节点)，有什么用？
<font color = "#000066">那大家先算一下这个红黑树有多少条路径？
如果不带空的话，我们可能会认为有5条，但是这里计算路径其实应该走到空（NIL），所以正确的应该是有11条路径。 所有我们可以认为这条规则就是为了更好的帮我们区分不同路径的。
然后再补充一个概念：
<font color = blue>结点的黑高（黑色高度）：从某结点出发（不含该结点）到达任一空叶结点的路径上经过的黑结点总数
1.3 已经学了AVL树，为啥还要学红黑树
然后我们再来分析一个问题：
<font color = "#000066">大家想，对于一棵红黑树来说，如果它里面全部的黑色结点一共有N个的话，那它的最短路径长度就差不多是$log_2 (N)$。 然后整棵树的节点数量就是在【N，2N】之间。 所以最长路径长度就可以认为差不多是2$log_2 (N)$ 所以红黑树的查找最少是$log_2 (N)$次，最多是2$log_2 (N)$次，所以红黑树查找的时间复杂度是O($log_2 N$)，计算时间复杂度前面的常数项可以省略嘛。 而AVL树也是O($log_2 N$），但AVL树是比较严格的O($log_2 N$），而红黑树是省略了常数项。 所以严格来说，红黑树的查找效率是比不上AVL树的（但对于计算机来说是没什么差别的），但是它们是同一个数量级的，都是O($log_2 N$）。
那既然好像都差不多，为什么我们已经学了AVL树了，还要学红黑树呢？红黑树有什么优势吗？
<font color = "#000066">🆗，由于AVL树要求更加严格的平衡，所以在进行插入和删除操作时，可能需要更频繁地进行旋转操作来调整树的结构，以保持平衡。相比之下，红黑树的插入和删除操作需要旋转的次数相对较少，因此在插入和删除操作频繁的情况下，红黑树可能更加高效。 这个如果大家学完这篇文章或许能更好的理解。
所以综合而言：
<font color = "#000066">红黑树其实更胜一筹，红黑树在实际应用中更为常用，STL中的map和set底层就是用的红黑树，我们后面也会用红黑树进行模拟实现。 当然红黑树和AVL树在不同的应用场景下有各自的优势和适用性，所以我们都有必要学习学习。
2. 红黑树结构的定义
那我们先来定义一下红黑树的结构：
<font color = black>这里结点的颜色我们可以用一个枚举
然后大家看，这里结点的颜色我们给的是红色，为什么要选择红色呢？黑色不可以吗？
<font color = "#000066">我们来分析一下如果我们插入一个新结点给的是黑色，那它一定会违反上面提到的红黑树的第5条性质——每条路径上黑色结点的数量一致。
所以我们新插入的结点给成红色，当然如果是第一次插入根结点我们可以直接给黑色，因为红黑树要求根结点必须是黑色嘛。
3. 插入（仅仅是插入过程）
由于红黑树也是一种搜索二叉树，是在二叉搜索树的基础上加上其平衡限制条件来实现平衡。
所以红黑树插入的逻辑也根搜索二叉树一样：
<font color = "#000066">
那插入一下就完事了吗？
<font color = "#000066">当然不是，和AVL树一样，插入新结点之后，我们要去判断此时这棵树是否还满足是一棵红黑树，如果不满足就要进行相应的调整。
那红黑树又是如何进行调整的呢？
4. 插入结点之后根据情况进行相应调整
对于红黑树来说，插入新结点之后，我们要检查红黑树的性质是否遭到破坏，如果遭到破坏的话，就需要进行相应的调整。
因为新节点的默认颜色是红色，因此：
<font color = blue>如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整； 但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连续红色结点出现，此时需要对红黑树分情况来讨论：
约定：
<font color = blue>当我们在红黑树中插入一个新结点的时候，cur为当前新插入结点，p（parent）为父结点，g（grandfather）为祖父结点，u（uncle）为叔叔节点 比如
我们下面分成了三种情况，但是有些地方分的比较细的话会分为五种：
<font color = "#000066">第一种就是第一次插入，作为根结点，直接将它染成黑色就完了，那这种我们上面已经处理过了。 第二种就是插入的时候它的父亲是黑色的（新插入的结点是红色的），这种就不需要调整，插入完直接结束。 那第二种的话我们也不需要单去处理，因为第二种不进入我们下面讲的三种情况，所以就不会对他进行任何处理，最后直接结束。
最后全部写完大家可以自己捋一遍。
下面讲解剩下的三种情况：
4.1 cur为红，p为红，g为黑，u存在且为红（无需旋转，变色即可）
情况分析及处理
那这个我们就认为是情况三。
那首先我们还是来看一下该情况对应的一个抽象图：
<font color = "#000066">
那对于这种情况我们要如何去处理呢？
<font color = blue>首先第一步：将p,u改为黑，g改为红
那这样就完了吗？
<font color = blue>还没有。 如果g是根节点，调整完成后，需要将g改为黑色。
那上面是g是根结点的情况，那如果g是一棵子树呢？
<font color = blue>比如这样：
那这种情况又如何处理呢？
<font color = blue>如果g是子树，那前面的步骤还是一样——将p,u改为黑，g改为红
代码实现
那我们来写一下代码：
<font color = black>
4.2 cur为红，p为红，g为黑，u不存在/u存在且为黑（单旋+变色）
情况四
情况分析及处理
那上面讨论的是u存在且为红的情况，那如果u不存在或者u存在且为黑呢？
先来看u不存在的情况：
<font color = "#000066">像这样
来看u存在且为黑的情况：
<font color = "#000066">如果出现u存在且为黑的情况一定是由上面的4.1情况3调整得到的。 为什么呢？ 大家看，如果插入的时候就是这种情况
那上面说了u为空也是一样的处理，我们可以来画一下
<font color = "#000066">
<font color = blue>这里变色的情况是一样的，关键在于判断并进行不同的旋转。
<font color = blue>我们上面分析的情况是在较高左子树的左侧插入，所以先要进行右单旋，然后变色。 如果我们是在右侧插入（较高右子树的右侧）的话，那就是先进性左单旋，然后变色，这里变色是一样的。 比如这样：
代码实现
<font color = "#000066">这里的代码我们等到后面和双旋的一起写
那上面我们说细分的话有5种情况，上面已经说了4种，那最后一种其实也是u不存在/u存在且为黑，与上一种情况的区别就是第5中是==双旋==+变色
4.3 cur为红，p为红，g为黑，u不存在/u存在且为黑（双旋+变色）
上面我们分析的是需要进行单旋然后变色的情况，那当然就有需要进行双旋调整高度，然后再变色的情况。 当然本质是因为插入的情况不同，所以需要不同的旋转来降高度。
情况分析及处理
那我们就来分析一下需要双旋+变色的情况：
<font color = "#000066">首先前提条件根上面一样，还是cur为红，p为红，g为黑，u不存在/u存在且为黑
这里画图我就不分那么细了，因为跟上面其实差不多，只是要进行的旋转不同
<font color = "#000066">我们来画一种左右双旋+变色的情况
那如果u不存在，那就是这样
<font color = blue>
再给大家画一下u存在且为黑的情况吧：
<font color = blue>同样的，如果这里出现u存在且为黑的情况，也一定是有4.1情况3调整更新得到的 比如这样
4.4 （单/双）旋转+变色 代码统一实现
那接下来我们来写一下需要旋转+变色调整的几种情况的代码
首先我们来看左侧插入的情况（右单旋/左右单旋）
<font color = black>
那我们再来写一下右侧插入的：
<font color = black>
5. 红黑树的测试
5.1 验证其为搜索二叉树
首先我们还是先来验证他是否是二叉搜索树，看它中序是否有序就行了
<font color = black>
5.2 验证其是否平衡且满足红黑树性质
那如何判断它是否满足是一棵红黑树呢？
其实就是去检查那几条规则（性质）：
<font color = "#000066">首先结点颜色要么是黑色，要么是红色，这没什么好检查的。 然后根结点必须是黑色，这个可以检查一下，如果根结点不是黑色（是红色）直接就不符合了
然后我们来验证一下：
<font color = black>
5.3 大量随机数构建红黑树进行测试
下面我们来生成一些随机数构建一棵红黑树测试一下：
<font color = black>先来10万个
5.4 插入相同数量随机数比较AVL树和红黑树的高度
然后我们AVL树写的求高度的函数拷贝过来，在AVL树和红黑树中插入相同数量的随机数，看看它们的高度会差多少：
<font color = black>
6. 红黑树的删除
红黑树的删除呢我们这里不做详细讲解：
<font color = "#000066">红黑树的删除比较复杂，要比插入还复杂好多。 但关键的是红黑树的删除在考研包括我们找工作笔试面试的时候一般是不会考察的，所以我们也没必要去学。 大家有兴趣的可以自己查找相关资料进行学习，可以参考《算法导论》或者《STL源码剖析》
7. 红黑树的查找
那红黑树的查找就也和搜索二叉树的查找一样，之前讲过，这里就不再说了。
8. 红黑树与AVL树的比较
<font color = blue face = "楷体" size = 3>红黑树和AVL树都是高效的自平衡搜索二叉树，增删改查的时间复杂度都是O($log_2 N$)。 红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，所以AVL树的插入和删除操作比红黑树更耗时。 因为AVL树在插入和删除节点后，会进行更多的旋转操作以维持一个较为严格的平衡，所以插入和删除操作的时间复杂度更高。 相对而言，红黑树对平衡的控制比较宽松，降低了插入删除时需要旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。 在实际应用中，红黑树的使用更广泛。许多编程语言和库都使用红黑树作为基础数据结构，例如C++ STL中的std::map和std::set就是基于 红黑树实现的。
9. 红黑树的应用
<font color = black>1. C++ STL库 -- map/set、mutil_map/mutil_set
Java 库
linux内核
其他一些库
10. 源码分享
10.1 RBTree.h
#pragma once
enum Colour
{
RED,
BLACK,
};
template <class T>
struct RBTreeNode
{
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
T _data;
Colour _col;
RBTreeNode(const T& data)
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _data(data)
, _col(RED)
{}
};
template <class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (data < cur->_data)
{
parent = cur;
cur = cur->_left;
}
else if (data > cur->_data)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//走到这里cur为空，就是key应该插入的位置
cur = new Node(data);
//链接
if (data < parent->_data)
parent->_left = cur;
if (data > parent->_data)
parent->_right = cur;
//链接父亲指针
cur->_parent = parent;
//如果插入之后它的parent是红的，就需要进行调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//如果父亲是祖父的左孩子，那右孩子就是叔叔
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//这里处理的情况是叔叔存在且为红，变色+向上继续处理
if (uncle && uncle->_col == RED)
{
//将p,u改为黑，g改为红
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//更新cur为grandfather，判断它的父亲是什么情况：
//1.如果不存在或者为黑，就需要继续处理了，也不会进行循环了
//2.如果它的父亲存在且为红，重新循环进行调整
cur = grandfather;
parent = cur->_parent;
}
else//叔叔不存在/叔叔存在且为黑的情况
{
// g
// p u
// c
if (cur == parent->_left)//左左——右单旋+变色
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//左右——左右双旋+变色
{
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
//这里调整完就可以break了，因为颜色都变的合适了，而相关的链接关系旋转会帮我们处理
break;
}
}
//如果父亲是祖父的右孩子，那左孩子就是叔叔
else //parent = grandfather->_right
{
Node* uncle = grandfather->_left;
//这里处理的情况是叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//将p,u改为黑，g改为红
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//更新cur为grandfather，判断它的父亲是什么情况：
//1.如果不存在或者为黑，就需要继续处理了，也不会进行循环了
//2.如果它的父亲存在且为红，重新循环进行调整
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//右右——左单旋+变色
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//右左——右左双旋+变色
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//上面处理过程中有可能会把根变成红色，这里统一处理一下，把根置成黑
_root->_col = BLACK;
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBlance()
{
if (_root && _root->_col == RED)
{
cout << "根结点是红色" << endl;
return false;
}
//先求出一条路径黑色结点数量
int mark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++mark;
cur = cur->_left;
}
//检查是否出现连续红色结点及所有路径黑色结点数量是否相等
return _Check(_root, 0, mark);
}
int TreeHeight()
{
return _TreeHeight(_root);
}
private:
int _TreeHeight(Node* root)
{
if (root == nullptr)
return 0;
int RightH = _TreeHeight(root->_left);
int leftH = _TreeHeight(root->_right);
return RightH > leftH ? RightH + 1 : leftH + 1;
}
bool _Check(Node* root, int blackNum, int mark)
{
if (root == nullptr)
{
//走到空就是一条路径走完了，比较一下是否相等
if (blackNum != mark)
{
cout << "存在黑色结点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
++blackNum;
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "出现连续红色结点" << endl;
return false;
}
return _Check(root->_left, blackNum, mark)
&& _Check(root->_left, blackNum, mark);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//旋转并更新_parent指针
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//先保存一下parent->_parent，因为下面会改它
Node* pparent = parent->_parent;
//旋转并更新_parent指针
subR->_left = parent;
parent->_parent = subR;
//若pparent为空则证明旋转的是一整棵树，因为根结点的_parent为空
if (pparent == nullptr)
{
//subR是新的根
_root = subR;
_root->_parent = nullptr;
}
//若pparent不为空，则证明旋转的是子树，parent上面还有结点
else
{
//让pparent指向子树旋转之后新的根
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
//同时也让新的根指向pparent
subR->_parent = pparent;
}
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//旋转并更新_parent指针
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//先保存一下parent->_parent，因为下面会改它
Node* pparent = parent->_parent;
//旋转并更新_parent指针
subL->_right = parent;
parent->_parent = subL;
//若parent等于_root则证明旋转的是一整棵树（这也是一种判断方法）
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
//让pparent指向子树旋转之后新的根
if (parent == pparent->_left)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
//同时也让新的根指向pparent
subL->_parent = pparent;
}
}
private:
Node* _root = nullptr;
};10.2 Test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <time.h>
#include "RBTree.h"
void RBTest1()
{
//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int arr[] = { 95,47,32,29,7,7,2,50,74,30 };
RBTree<int> t1;
for (auto e : arr)
{
t1.Insert(e);
}
t1.InOrder();
cout << t1.IsBlance() << endl;
}
void RBTest2()
{
srand((unsigned int)time(nullptr));
const int N = 100000;
RBTree<int> t;
for (int i = 0; i < N; ++i)
{
int x = rand() + i;
t.Insert(x);
}
cout << t.TreeHeight() << endl;
AVLTree<int, int> t2;
for (int i = 0; i < N; ++i)
{
int x = rand() + i;
t2.Insert(make_pair(x, x));
}
cout << t2.TreeHeight() << endl;
}
int main()
{
RBTest2();
return 0;
}
- 点赞
- 收藏
- 关注作者
评论（0）