目录
红黑树
简述
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
性质/规则
详细说明:红黑树_百度百科 (baidu.com)
主要规则:
为了方便理解和记忆,先将红黑树规则分解,以下三点是我认为理解红黑树是最主要的规则.加粗的是关键字,先记住这些关键字,去学习红黑树时会容易理解许多.
- 根节点是黑色.
- 任意两个相邻结点不能同时为红.即红色结点的孩子是黑色的.(不能出现连续的红色结点)
- 任意结点到其可到达的叶节点间,均包含相同数量的黑色结点.(每条路径上都有相同的黑色结点)
其他规则:
默认规则:每个结点不是红色就是黑色
补充:叶结点都是黑色,且不存数据,也被称为NIL结点nil（计算机语言）_百度百科 (baidu.com)
转载:通过将红黑树的所有叶子节点都替换为NIL节点，可以保证红黑树的每个节点都至少有一个子节点，从而简化了操作的实现。NIL节点的存在有助于维护红黑树的结构和性质，特别是在处理边界情况时，通过判断节点的子节点是否为NIL节点来避免特殊处理叶子节点的情况.
推导性质:
推导规则是红黑树规则加二叉树性质推导的一些规则,在后面用来证明和理解红黑树的一些操作.
- 推导性质1:
一条路径的所有可能情况中,最长路径节点个数不会超过最短路径的两倍(连续的红节点能够使最长路径超过最短路径的两倍)
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
红色结点如果有两个孩子,则都是黑色.(可能有0,1,2个黑孩子)
修改祖先结点颜色变化不会影响所有分支路径的黑色结点的平衡(修正常用)
- 推导性质2:
-
最短路径:全部是黑色结点
-
最长路径:红黑相间(一黑一红,最后一个非NIL结点可以是红)
-
去掉红色结点的红黑树接近一棵满二叉树.(直接去掉红色结点可能就不是二叉树了,hold不住)
-
当只有一个根节点时(黑),第二个结点只能是红色(满足黑结点数量相同),被迫只能插入红色结点.
-
新增结点默认为红色,红色规则比黑色宽松
- 推导性质3:
设黑色结点有N个
-
最短路径长度为:$log_2(N) $
-
最长路径长度为:$2log_2(N)$
-
一棵红黑树的所有结点数量在[N,2N]之间.(全黑为N,红黑全满为2N)
-
性能上,假设有10亿个结点,AVL树最多查找30次, RB树最多查找60次
注:文章仅以理解红黑树的主要功能(插入修正)实现为主,没有实现对NIL结点处理等其他情况,不是严谨的红黑树实现.
红黑树的基本实现
基本功能和AVL树是几乎一样的.以下就简要描述了
struct RBTreeNode
template<class K, class V>
struct RBTreeNode {
//三叉链
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
std::pair<K,V> _kv;
Color _col;
RBTreeNode(const decltype(_kv)& kv)
: _left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(Color::RED) //默认为红,因为规则最宽松
{}
};
class RBTree
enum class Color { RED, BLACK };
template<class K,class V>
class RBTree {
public:
bool Insert(const std::pair<K,V>& kv);
private:
using Node = RBTreeNode<K,V>;
Node* _root;
};
红黑树的插入
插入的重点和AVL树一样,在于插入修正
bool Insert(const std::pair<K,V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = Color::BLACK;
return true;
}
Node* cur = _root;
Node* parent = _root;
while (cur) {
if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur -> _right;
}
else if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur -> _left;
}
else {
//存在相同的
return false;
}
} //while比较过程 [end]
//没找到,新增
cur = new Node(kv); //cur地址改变,只能使用kv进行比较(始终使用kv就好了)
//维护三叉链
if (cur->_kv->first > parent->_kv.first) {
parent->_right = cur;
}
else {
parent->_left = cur;
}
//检查和调整红黑树
FixInsert();
}
红黑树插入修正前言
在实现红黑树插入前,我们知道红黑树插入新结点后,一定会出现不满足红黑树规则的情况,因此我们先将需要,红黑树的修正操作主要通过旋转和变色来实现.
什么时候需要变色:
只有父亲是红色时,才需要变色,且必须变色.(红节点不相邻规则)
变色的基础:
插入红节点规则最宽松,不需要调整其他路径,因此插入结点不可变色,所以只能将父亲变成黑色,后面就围绕父亲变黑后,爷爷结点和叔叔结点如何变色进行处理.
一句话:父亲是红色时,必须要变色,且变色的是父亲.(扩展说法:都是父爷颜色交换.后文详细解释)
为什么需要旋转与变色
变色:
根据二叉树规律:满二叉树总是一个结点两个孩子,总是1:2的关系.
通过这个关系可以实现数量对调操作,即1个黑色父:2个红色孩子 可以转换成 1个红色父:2个黑色孩子
这样变色对父结点的所有分支路径颜色影响比较小,不容易破坏红黑树黑结点数量相同规则(简称).
旋转
首先,1个黑结点,两个红节点.观察发现,只要一定的旋转操作即可平衡.
红黑树在某些情况下,直接变色操作难以满足规则,或者较为复杂;而通过一定地旋转操作后,会更加简单,因此红黑树需要循环.具体情况请看下文.
;另外,具体的旋转操作我在另一篇博客详细描述了,本篇就不再描述太多了.AVL树
需要修正的所有情况
红黑树需要修正的所有情况都是从下面这棵抽象树衍生出的.
只有理解红黑树基本的修正情况才能够实现红黑树.下面将循序渐进讲解:
先认识最简单的情况
最简单的情况可以认为是最远的几个结点之间的修正,也是插入后第一次修正,最简单情况也是最容易理解的.红黑树修正和AVL树的一样,情况很多很复杂,搞定简单的再去看抽象情况好理解很多.
1. 叔叔是红色结点
描述:叔叔和父亲都是红色,且叔叔和父亲都是非NIL结点的最远结点.
反证:如果叔叔还有子结点,那一定是黑色,即多了一个黑色结点;为了满足各路径黑结点数量相同的规则,父结点也必须要有黑色子节点,且必须要有两个,那就无法再插入新节点了,因此这种情况不可能.
- 左左(LL型)
插入到父结点的左边
操作:父变黑,爷变红(父爷交换颜色),叔叔变黑
感性解释:
父子都是红,只能且必须由父亲变黑.因为多了一个黑结点,所以所在路径必须上少一个黑结点;
要少哪一个呢?肯定不能往下了,因为下面是已经处理过了(修正操作是往上迭代的),所以只能往上寻找;
因为插入前路径上的所有结点都是满足红黑树规则的,所以爷爷结点一定是黑色;又因为爷爷距离父是最近的结点,对其他结点影响最小,因此选择将爷爷结点置为红,即将父爷结点颜色交换;
爷爷颜色是红色结点后,叔叔路径则少了一个黑色结点,因此叔叔结点必须变黑.
- 左右(LR型)
操作:父变黑,爷变红(父爷交换颜色),叔叔变黑.
因为父和叔都是最远结点,调整过程没有子结点影响,也不需要旋转等额外操作,因此和LL型是完全相同的.
注意:
爷爷非根,在有叔叔且为红的情况下,新增结点加一轮修正后,爷爷会变红 此时如果祖爷爷也为红,需要继续修正.
也只有这种情况下才可能需要继续修正
2.没有叔叔结点
从操作上来看,没有叔叔的情况和叔叔为黑的情况是一样的.不过没有叔叔的情况是第一轮修正的状态,较为容易理解.
叔叔为黑色的情况下,黑结点数量不匹配,说明这种情况是上一次调整导致的(中间状态/不平衡状态);
没有叔叔的情况下,根据长度规则,此时已是最长路径(爷爷是最后一个非NIL黑结点),因此新增结点一定是最远结点,即插入后的第一次修正
- 左左(LL型):爷爷右单旋(降高度),交换父爷颜色
- 为什么要旋转?
在叔叔为空的情况下,插入红色结点可能会违反长度规则(一条路径中最长路径不超过最短路径的两倍),
(上图举例)
在上一篇AVL树中我们知道使用旋转子树可以降低高度(旋转过程在AVL树篇有详细描述,本篇不再具体描述,.同样的,红黑树在违反长度规则后也可以使用旋转来降低高度.经过验证,旋转处理可以有效解决违反长度规则问题.
如何旋转?
LL型中,对爷爷结点进行左旋,之后爷爷结点成为父结点的左孩子,高度-1;再交换父爷结点颜色,红黑树就平衡了.
旋转下来后为什么要变色? 如何变色?
旋转下来,父亲结点是祖先,是红色;但是爷爷是黑色,即以父结点为根的两条路径黑结点数量不平衡,一条多一个另一条少一个,这种情况下交换父爷结点颜色即可平衡.
- 左右(LR型):父左单旋(转成LL型),爷爷右单旋(降高度),交换父爷颜色.
3. 叔叔是黑色结点
(本身黑结点数量不匹配,说明这种情况一定是上一次调整导致的)
直接上图
所有结构的基础衍生结构（以左为例）
在认识了简单结构后,我们对红黑树修正的基本情况有了大概的认识了.现在来分析这些结构怎么来的,下图是一个抽象结构,所有的需要修正的情况都是由下图所衍生.
矩形▯为任意高度的子树，其中x为可能插入的位置,y是由x决定的（根据红黑树规则）。
简单情况衍生
当x为插入的结点时，
（△表示一个结点,其中a,b是新结点可能插入的位置，c只能为红色或没有结点。）
- 当c为一个红色结点时,衍生出以下情况
显然就是在上文的简单结构,红叔叔的情况.
- 当c为一个黑色结点时
和上文的一样,这种情况是修正中间状态,由上一轮修正引起的
- 当c为空时
二级修正的情况衍生
当矩形x非插入结点，并根据
- 红黑树规则
- 和在简单情况中分析的，只有叔叔为红色结点时，才会使爷爷结点变红，进而可能影响到祖先结点
进行往下衍生一次，得到此图。
其中c为下图i/j/k/l中任意一种情况，d下面具体分析
在最远结点四个位置插入均会引发爷爷结点变红。以插入最左位置为例
- d为红时
- d为黑时，有两种基本情况
其中a可能为i/j/k/l四种，b和c只能为空或者一个红色结点
- 当d为空时，在简单情况分析中得知调整方法和d为黑是一样的，可以复用，就不再分析了。
总结：
往后还有3级，4级...等,我们知道2级怎么来的就足够了,套用1级的方法,加上迭代修正,就能完成最终平衡.