※ 引述《jouen (呵呵)》之铭言：
: https://i.imgur.com/TMCf9D4.jpg
: 第一个图插入10之后，2、8有一定要变黑吗？ 如果2、8维持红色，应该也是符合红黑树
: 的规则吧？而且对应的2-3-4树高度反而比较低不是吗？
: 可是为什么图中要将2、8变为黑色？ 还是我有理解错的地方呢
认真的回一下这篇文章来讨论各类红黑树。
我先给个摘要的结果：
方法 时间 空间 #Pass 旋转 变色
Top-down O(lg n) O(1) 1 O(lg n) O(lg n)
Bottom-up O(lg n) O(1) 2 O(1) O(lg n) Amortized O(1)
Top-down-Tarjan O(lg n) O(1) 1 O(lg n) O(lg n) Amortized O(1)
Amortized O(1)
其中 Bottom-up 的空间复杂度是指没有 parent pointer 的情况。
有 parent pointer 很简单是 O(1) ，但是没有 parent pointer 还
是可以 O(1) 的
这三种方法的简介如下：
1. Top-down: 红黑树原始论文上的方法，想知道细节的可以参考
Mark Allen Weiss 的资料结构。这方法不需要 back track，
所以可以容易的用循环实作但是最多会有 O(lg n) 个旋转。
2. Bottom-up: Tarjan 参考 half-balanced tree 设计出来的方
法，想知道细节的可以参考 CLRS 。因为需要 backtrack ，
所以用递回或是用循环 + parent 指标实作。这方法插入最
多只需要两次旋转，删除最多三次旋转。而且这方法可以被证
明，当插入或是删除的节点确定后，之后的rebalance （变色 + 旋转）
复杂度是 amortized O(1)！这个性质对 C++ 函式库很重要，
因为标准规定在 set 的 insert 和 erase 可以提供 hint ，
如果 hint 是正确的话，时间复杂度必须是 amortized O(1)。
换言之，如果把已排序元素循序插入到 set 中，只要有提供
对的 hint ，插入 n 个元素只需要 O(n) 时间。也因为这个
要求，AVL 是不能拿来实作 C++ 的 set 的。
3. Tarjan's Top-down: 这是另一种 top-down 的方法，但是旋
转和变色的数量是 amortized O(1) 的 [1]。
以下我稍微介绍一下我是怎么理解 bottom-up 的插入法的。
在 Horowitz 和 Sahni 的资料结构书上，介绍 AVL 的插入时，
有用到一个性质是，如果需要旋转，那么旋转只会发生在一个节
点上（可能是单旋或是双旋），而且从此点（Tarjan 称之为
safe node）往下到插入的地方，就只是单纯调整 balance factor 而已。
可以用同样的方法来处理红黑树，先找到要旋转的点，此点以下
就只是单纯的变色，然后最后旋转即可。
在插入的时候，会先需要从 root 往下开始 traverse 去找需要插入的
位置，为了讨论方便，我们把 root 到插入位置的搜寻路径叫做 p ，
而新插入节点设定为红色。safe node 就是在 p 上，距离插入节点最近，
至少有一个黑子节点的黑点，如果没有这种点的话，那就把 root 当
safe node。
因为插入的点是红色，只有插入点的父节点是红色时才会违反红黑树条件，所以接
下来就只讨论插入点的父节点是红色的情况。
虽然条件有点复杂，但是如果把 p 画成一条直线，不在 p 上的分叉点画成垂直线，
那么 p 必定会长成这样
情况 1： safe node 在 p 上的下一个点是黑点。
safe node 插入点
root - .. - 黑 - 黑 - 红 - 黑 - 红 - .. 红 - (红) - 黑 (sentinel)
| | | | | | |
黑/红 红 黑 红 黑 黑 黑 (sentinel)
也就是，在 p 上，safe node 以下，必定是红点接着有两个红子节点的黑点相继出现。
另一种情况是
情况 2： safe node 在 p 上的下一个点是红点。
safe node 插入点
root - .. - 黑 - 红 - 黑 - 红 - .. 红 - (红) - 黑 (sentinel)
| | | | | |
黑 黑 红 黑 黑 黑 (sentinel)
而调整的方式就是从 safe node 以下，先变色。
情况 1 ，变完色就成为
safe node 插入点
root - .. - 黑 - 红 - 黑 - 红 - 黑 - .. 黑 - (红) - 黑 (sentinel)
| | | | | | |
黑/红 黑 红 黑 红 红 黑 (sentinel)
这样就变成合法的红黑树了。而情况二则是变完色之后要再旋转，旋转的判断
有两个 case ，详情请参考 CLRS 。
所以 bottom-up 的插入，第一个 pass 先找到 safe node ，
然后从 safe node 以下进行第二个 pass 来变色，最后再旋转，
就可以使用循环来实作，所以就算没有 parent pointer 也可以
只使用 O(1) 空间。
删除其实也类似，先找到 safe node ，以下变色，然后旋转，
只是 safe node 的条件稍微复杂一些，有人想知道的话我再写
一篇吧。
这技巧也被用在 WAVL tree 上，有兴趣的可以研究。
https://en.wikipedia.org/wiki/WAVL_tree
除了这三种红黑树之外，还有一些相关的资料结构。
AA tree
https://en.wikipedia.org/wiki/AA_tree
用二元树模拟 2-3 tree，可以参考 Mark Allen Weiss 的资料结构。
Left-leaning red–black tree
https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree
用二元树模拟 2-3 tree 或是 2-3-4 tree。
可以参考 Sedgewick and Wayne 的 Algorithms。
（Sedgewick 是红黑树的发明人之一）
[1] Robert Endre Tarjan
Efficient Top-Down Updating of Red-Black Trees