red black tree
为什么要有红黑树？
BST（binary search tree）查询的时间复杂度是log n \log nlogn。
但是，当它退化成链表的时候：
查询时间复杂度就变成了O ( n ) O(n)O(n)。
这是很糟糕的情况，虽然它还是符合二叉树的定义（左小右大）。
所以，我们要限制一些规则，来让树保持平衡（尽可能的），以此保证查询效率为log n \log nlogn。
红黑树就是这么一棵尽可能保持平衡的二叉搜索树。
什么是红黑树？
红黑树要满足四个性质：
- 每个节点要么是红的，要么是黑的
- 根节点和叶节点都是黑的
- 每个红色节点的父节点是黑的。或者说，不可能出现连续的两个红色节点
- 对任意节点x xx，它到叶子节点的简单路径所包含的黑色节点的数量是一样的，我们称之为其黑高度是相等的。
前三点很好理解，第四点是什么意思呢？
随便找一个节点x xx，找一条路径到叶子节点，简单路径的意思就是你别回头。
它的任意一条简单路径所包含的黑色节点是相同的。
比如上图，黑色节点都是5个，我们说，其黑高度为5。
举一个红黑树的例子：
性质1，2，3都轻而易举地满足，我们看性质4。
首先是叶子节点，它们是空指针，它们的黑高度是0。
3，8，10，11，22，26的黑高度都是1。
7，18的黑高度是2。
因此性质四也满足。
为什么查询时间复杂度是log n \log nlogn?
我们将证明h ≤ 2 log ( n + 1 ) h \le 2\log(n+1)h≤2log(n+1)
其中，h hh是树高，n nn是key的数量，也就是节点的数量（不包含叶子的数量）。
我们的方法是：将红色节点上移合并到黑色节点。
合并后，这就变成了一棵2-3-4树，因为叶子有两片的，有三片的，也有四片的。
我们数一下，合并前的红黑树，它的key的数量是8，叶子的数量是9。
一般来说，叶子节点的数量=key的数量+1=n+1
回到2-3-4树。现在假定2-3-4树的树高为h ′ h'h′。
因为每个节点至少有两个分支，至多有四个分支，所以：
h ′ 2 ≤ ( n + 1 ) ≤ h ′ 4 h'^2\le(n+1)\le h'^4h′2≤(n+1)≤h′4
我们关注左半部分。
h ′ ≤ log ( n + 1 ) h' \le \log(n+1)h′≤log(n+1)
那么h hh与h ′ h'h′有什么关系呢？
由性质3可以得到，
h ′ ≥ 1 2 h h' \ge \frac{1}{2} hh′≥21h
所以
h ≤ 2 log ( n + 1 ) h \le 2\log(n+1)h≤2log(n+1)
这就证明了查询的时间复杂为O ( log n ) O(\log n)O(logn)。
操作
红黑树的操作只要包括变色和旋转。
比如要插入一个元素15，默认是红色节点，就必然会违反红黑树的一些性质。只有通过变色和旋转才能保证四条性质。
我们讲一下旋转。
旋转有左旋和右旋。
右旋：
上图的α , β , γ \alpha,\beta,\gammaα,β,γ都是subtree。
右旋其实很好理解，它必须要保证BST的性质，即
∀ a ∈ α , b ∈ β , c ∈ γ 有 a ≤ A ≤ b ≤ B ≤ c \forall a \in \alpha,b \in \beta, c \in \gamma \quad 有a\le A \le b \le B \le c∀a∈α,b∈β,c∈γ有a≤A≤b≤B≤c
左旋反过来即可。