红黑树

平衡二叉树(AVL树) 虽然可以保证再最坏的情况下，查找、插入和删除的时间复杂度为$O(\log n)$ ，但是插入和删除后重新调整平衡可能需要多达 $O(\log n)$ 次的旋转，频繁地调整平衡导致全树地整体拓扑结构地变化。AVL树地左右子树高度绝对差的绝对值不超过1，而红黑树在AVL树“适度平衡”的基础上，进一步放宽条件：红黑树的左右子树高度不超过两倍。

红黑树也是一种平衡二叉搜索树，虽然和AVL树一样，查找、插入和删除的时间复杂度均为 $O(\log n)$ ，但其统计性能更好一些，不需要频繁调整平衡，且任何不平衡都能在3次旋转之内解决。因此红黑树在很多地方都广泛应用，例如在C++ STL中的 set，multiset，map，multimap 都应用了红黑树的变体。Java中的集合类 TreeMap 就是红黑树的实现。

首先我们来介绍一个概念：黑高。从某个节点x(不包含该节点) 到叶子的任意一条路径上黑色节点称为该节点的黑高

红黑树是满足以下性质的二叉搜索树

1) 每个节点都是红色或者是黑色的

2) 根节点是黑色的 //旋转的时候需要维护

3) 每个叶子节点是黑色的(包括空孩子)

4) 如果一个节点为红色，则其孩子节点、父节点必定为黑色。//旋转的时候需要维护

5) 从任一结点到其后代叶子的路径上，均包含相同数目的黑节点。这说明左右子树的黑高是相同的 //旋转的时候需要维护

因此，ps：红黑树的黑色节点越多红黑树就平衡，如果一颗红黑树全是黑色节点，那么这一定是一颗满二叉树。

问题：红黑树没有AVL树那么平衡，为什么查找插入和删除的速度也是$O(\log n)$ 呢？

这是因为含有n个内部节点的红黑树的高度不超过$O(\log n)$

证明：假设红黑树的高度为h，根到叶子结点至少一半是黑色节点，根的黑高至少为 $h/2$ ，那么高为 $h/2$ 的二叉树节点数为 $2^{h/2}-1$ ，而除了这些节点，后面的 h/2 肯定还有节点存在，否则树高也不会为h。因此 $n\geq 2^{h/2}-1$, 即 $n+1\geq 2^{h/2}$ .两边同时取对数，得到 $h\leq 2log(n+1)=O(\log n)$

红黑树与4阶B树

红黑树和4阶B树之间存在等价关系。如哦从红黑树的树根开始，自顶向下逐层检查，如果遇到红结点，则将该节点压缩到父节点一侧；如果遇到黑节点，则保留。因为红结点对黑高没有贡献，而黑结点对黑高有贡献。

红黑树与4阶B树的4种等价方式：

1）两个黑孩子(黑黑)，如图所示：

2）左黑右红(黑红)，如图所示：

3) 左红右黑(红黑) ，如图所示：

4）两个红孩子(红红)，如图所示

从红黑树与4阶B树的等价关系可以看出，4阶B树中的结点中必然含有一个黑节点。而且不会出现红色的父亲。每一个结点最多包含三个关键字：如果包含2个红关键字，则黑关键字必然在中间位置。

我们可以尝试将这一棵红黑树进行压缩。

最后可以得到这样一棵4阶的B树

那么既然红黑树和4阶B树是可以互相转化的，那么为什么还要用红黑树呢？这是因为红黑树和B树处理的方向不同。B树主要用于内外存的访问，旋转不是很容易，但是红黑树的旋转调平衡比较方便

红黑树的查找

红黑树的查找相当于二叉搜索树的查找。因为红黑树也要有中序有序性。

红黑树的插入

在红黑树中插入xx，首先要查找。如果查找成功，什么也不用做，直接返回即可。如果查找失败了，那么就在查找失败的位置创建x结点，并置红色(如果是树根，则置为黑色)

那么，为什么插入的结点一定要置为红色呢？

如果置为黑色有可能改变黑高，违反性质5。如果置红色，不会改变黑高，但是有可能违反性质4(红结点必然有黑孩子)

插入分为两种情况：

如果新插入的结点x的父亲为黑色，则仍然满足红黑树的条件，插入成功
如果新插入的结点的父亲为红色，则出现“双红”(也就是说父亲和孩子都是红色的),此时需要修正，使其满足红黑树的条件。

双红修正：

将x的父亲和祖父记为p(parent) 、g(grandpa), x的叔叔记为 u（uncle).下面我们会说明修正过程，让大家明白红黑树中的结点为什么可以那么任性的变颜色。

u为黑色

修正原理：当u为黑色，x及其父亲p出现”双红“，可以根据红黑树与4阶B树来进行转换实现。首先将红黑树通过压缩转换为4阶B树，此时4阶B树的结点中出现了两个红色的结点，则黑节点必然在中间。因此将中间结点p置为黑色，两旁的结点置为红色，然后再将其转为红黑树即可。

如图所示：

修正方法

修正的原理清楚了，那么该修正方法也可以看作是旋转和染色的过程。g到x的路径为LL，执行LL型旋转。将g右旋，然后将旋转后的根染黑，将其两个孩子染红，如图所示：

同样的道理，如果x是p的右孩子，也可以采用该方法来修正。如图所示：

通过旋转来解决的话，我们可以这样来做：

通过x向左旋转，我们可以得到一个LL型的红黑树，然后就按照上面所说的方法将g右旋下来并进行染色即可

根据对称性，如果g的左右子树互换了位置，则又会出现两种情况(RR型或者RL型) ，如图所示:

RR型:

RL型：

u为红色

如果x的叔叔为红色，x及其父亲p出现”双红“。其修正方法也可以根据红黑树与4阶B树的转换实现。首先将红黑树通过压缩转换为4阶B树，此时4阶B树的节点中出现了4个结点，发生上溢，需要执行分裂操作。令g上升到g的父结点中，分裂后x、p均为红结点，而4阶B树结点中必然含有一个黑节点，因此可以保持x的红色，将p、u染黑，g染红(保持黑高不变，如果g为树根，则染黑)，然后将其转换为红黑树即可