7. 红黑树
红黑树背景
红黑树（Red Black Tree） 也是一种自平衡二叉查找树，它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间非常良好，在实践中效率高效： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
应用背景
实现一种数据结构，可以对历史版本的访问
例如：
search( ver, key)：除了关键码key，还提供了版本号ver
insert( ver, key ) ； remove( ver, key)
如果一个数据结构能够支持这种类型的需求，就称之为Presistent Structure（一致性结构，持久性）
如何实现？
-
蛮力实现：对每个版本独立保存一份，各个版本入口自成一个搜索结构
Version
h = |history| : 历史版本数
时间上单次O(log h + log n)，而空间复杂度难以接受（每个版本都存一份），累计O(h*n)时间/空间
So，如何控制这里的复杂度呢？将复杂度控制在O(n+h*log n)内？
-
需要利用相邻版本之间的
关联性实现
解决方案：
O(1)重构
- 大量共享，少量更新（实现复杂，以后学习）
任何一个动态操作，引发的结构变化量不超过O(1)，这里红黑树正是具有这一特性的变种！！！
红黑树结构
定义：
由红，黑两类节点组成的BST （其中统一增设外部节点NULL，使整棵树成为真二叉树），满足一下4个条件
- 1 . 树根 ： 必为黑色
- 2 . 外部节点 ： 均为黑色
- 3 . 其余节点 ： 节点是红色或黑色，红之子，红之父，必为黑色
- 4 . 所有外部节点到根节点的路径中黑节点数目相等，计路径中黑色节点数目为黑深度
注：
（2）中外部节点为黑色的NULL节点，增设的！！
（4）中的特性，确保所有外部节点到根节点的路径中，没有一条路径会比其他路径长出2倍。因而，红黑树是相对平衡的二叉树！！！
红黑树图示
RB-Tree
通过上图，对红黑树进行提升变换（lifting）：即将所有的红色节点提升至与其父亲相同的高度；
红黑树提升变换的意义：所有底层节点都变成同一水平高度，平齐；
从上面lifting变换后的角度来看，红黑树就是4阶B-Tree（即(2，4)树）；
红黑树 ＝＝ （2，4）B 树
- 提升红节点，使其与其父亲等高
- 若将黑节点和提升上来的红孩子视作关键码合并成超级节点
- 无非4种组合，分别对应 4 阶 B-Tree 的一类内部节点
4种组合
如上4种组合，通过将红节点lift至与父节点等高后，满足4阶B树的特征
红黑树常用接口定义
1. Search() // 沿用 BST 的搜索算法
2. BinNode * insert(const T &e) // 插入算法（重写，动态）
3. bool remove(const T &e) // 删除算法（重写，动态）
4. 动态操作后若不满足红黑树定义的结构，进行拓扑结构修正操作，使之满足
4.1 void SolveDoubleRed(BinNode * x) // 双红修正
4.2 void SolveDoubleBlack(BinNode * x) // 双黑修正
5. 动态维护节点的高度
更新节点 x 的高度，注：只统计黑节点的高度！！！（重写）
int updateHeight(BinNode * x) 更新节点 x 的高度，注：只统计黑节点的高度！！！
1. RB-Tree 更新节点高度，只计黑节点高度
#define NodeHeight(p) ((p) ? p->height : 0) //节点高度，约定空树的节点高度为 0
int updateHeight(BinNode * x)
{
x->height = max(NodeHeight(x->lchild), NodeHeight(x->rchild));
if (IsBlack(x))
{
x->height ++ ; // 只计黑色节点
}
return x->height;
}
2. RB-Tree 插入节点操作
RB-Tree == 4阶B-Tree，借助B-Tree的模型，能更好的了解红黑树相关算法的原理＆过程
借助B-Tree理解红黑树的动态变换
插入算法流程：
- 现拟插入关键码为
e的节点； # 不妨设T中不含有e - 按
BST的常规算法，插入之； #x=insert(e)必为末端节点，不妨设x的父亲p = x->parent存在 - 将插入节点
x染红（除非它是根）； #x->color = isRoot(x) ? B : R
通过上述的操作，可以断定红黑树定义条件（1）（2）（4）依然满足，但（3）不见得，有可能x的父亲p为红色，导致双红缺陷！！！
双红缺陷
双红缺陷：double-red # p->color == x->color = red
若出现双红缺陷，如何修复呢？：SolveDoubleRed()
- 考察：插入节点
x的祖父g = p -> parent
注：因为出现双红，
p是红色节点，那么g一定不为红，有g != NULL && g->color = B
- 父亲节点
p的兄弟u = ( ( p==g->lchild ) ? g->rchild : g->lchild )
u节点即x的叔父，其中u的颜色不定
- 视
u的颜色R or B，分两种情况处理 ！！！，后面分析；
插入算法框架实现
BinNode * insert(const T &e)
{
1. 确认目标节点不存在（留意对 _hot 的设置）
BinNode * x = search(e);
if (NULL != x)
return x;
2. 创建红节点 x，以search()后的 _hot 为父，黑深度-1
x = new BinNode(e, _hot, NULL, NULL, -1);
_size ++;
3. 如有必要，需要做双红缺陷修正
SolveDoubleRed(x);
4. 返回插入的节点
return x ? x ： _hot->parent;
}//无论原树中是否存在e，返回时总有 x->data = e
详细讨论双红缺陷的两种情况以及解决方法
-
RR-1 : 插入节点
x的叔父节点u的颜色为黑色（u->color == B） -
RR-2 ：插入节点
x的叔父节点u的颜色为红色（u->color == R）
3. 红黑树的删除节点算法
相对于插入，删除操作更加复杂
理解方面：通过lifting变换，转换成B-Tree来理解
