算法 理解红黑树
本文 blog 链接 http://www.leyafo.com/post/2014-10-27-a-red-black-tree-implementation/
红黑树是有序平衡 BST(binary search tree) 的一种，它于 1978 年由 Guibas 和 Sedgewick 发明。红黑树是2-3-4 树 的一种抽象表示。有趣的是现在大多数算法书关于红黑树都没有提到过 2-3-4 树。算法书上关于红黑树的讲解都是基于定理来实现红黑树。至于这些定理怎么来的，算法书却没有描述过。这就是为啥算法书上的红黑树难以理解，这是算法书的坑。所以要理解红黑树，理解 2-3-4 树 是必不可少的一个过程。
2-3-4 树
2-3-4 树的基本性质
2-3-4 树也是一种有序的平衡树，所有从 leaf 到 root 的 path 的高度都是相等的。每个节点可以容纳 1 到 3 个节点，可以有 2 到 4 个子节点。下面就是 2-3-4 树的 3 种类型。
B D F H K O
/ \ / | \ / \ / \ / \
A C B E G A I L Y
2树 3树 4树
类似于 BST，2-3-4 对元素的排序是左小右大。不同的 3 树和 4 树的子节点会有中间大小的子节点。比如上图的 3 树中的 E 就比 D 大 比 F 小。4 树中的 I 比 H 大，比 K 小。L 比 K 大，比 O 小。
2-3-4 树的插入
前面说了 2-3-4 树是一种平横树，所有从 leaf 到 root 的 path 的高度都是相等的。这也就意味着每当插入一个新节点不能单纯的像 BST 那样将新的节点插入到树的底部，否则会破坏树的平衡。2-3-4 树使用的平衡方法是合并。就是将 2 树变为 3 树，3 树变 4 树。如下图：
B B
/ \ 插入 D => / \
A C A C D
B B
/ \ 插入 H=> / \
A C D A C D H
上面的插入方法解决了往 2-3-4 树 插入新节点而不破坏树的平衡的问题。但是如果要插入的节点已经是一个 4 树了，这种方法就不管用了，因为 4 树是没法变为 5 树的。可以将 4 树往上挪一个节点，并分裂出俩个 2 树的子节点。如果上面的父节点已经是 4 树了，则继续往上挪动。直到 root 节点，再需要分裂的话，这个时候可以将 root 节点也进行分裂。root 节点分裂后整颗树的高度会增加一层。如下图所示：
A A S A E S
/ \ 插入 S=> / | \ =>插入 E / \ / \ / \ => 插入 R ---->
先将 A E S 往上分裂 => E E
/ \ 插入 R=> / \
A S A R S
2-3-4 树的删除
树结构的删除都很麻烦，2-3-4 树 也不例外。2-3-4 树 插入的时候需要保持树的平衡，删除的时候也需要保持树的平衡。如果需要降低树的高度从 root 合并来降低树的高度。2-3-4 树 和 BST 一样会选择从 leaf 节点将 node 删除。如果找到的节点不是 leaf 节点会从当前节点的右边出发，找到最左边的 leaf 节点来替换，然后删除被替换后的 leaf 节点。如果 leaf 节点是 3 树或者或者 4 树，直接删除即可。如果是 2 树的话就不能直接删除，需要对其进行旋转操作，从临近的同一层节点挪个节点过来补上。如果临近元素也是 2 树则从父节点挪一个节点下来。 下图是删除 3 树和 4 树的情况：
C C D D
/ 删除 B=> / / 删除 B => /
AB A ABC AC
下图是一个比较复杂的删除操作，删除一个非叶子节点，会碰到 2 树的删除并需要旋转的情况。(节点比较多所以用数字来表示节点)
40
/ \
20 50 删除根节点40
/ \ / \ 找到右树最左边的42节点 ----------->
14 32 43 62 70 79 并替换掉,再删除替换后的叶子节点
/\ /\ /\ / | | \
10 18 25 33 42 47 57 65 74 81
42
/ \
左树不变 50
/ \ 相邻节点也是2树，将43挪下来并合并 ------>
43 62 70 79
/ \ / | | \
x 47 57 65 74 81
42
/ \
左树不变 50
/ \
43 47 62 70 79 上一步中43也是2树
/ | | \ 需要从临近的节点通过旋转来拿到一个节点 ----->
57 65 74 81
42
/ \
左树不变 62 <----- 62旋转上来
/ \
50 70 79
/ \ / | \
43 47 57 65 74 81 <----------- 57变为50的子节点
红黑树
红黑树是 2-3-4 树的一种抽象表示，在 1978 年 Guibas 和 Sedgewick 发明最初的红黑树。2008 年 Sedgewick 对其进行了改进，并将此命名为 LLRBT(Left-leaning red–black tree 左倾红黑树)。LLRBT 相比 1978 年的红黑树要简单很多，实现的代码量也少很多。Sedgewick 的一篇 PPT 对此有非常详细的介绍。现在大部分工程中的红黑树都是基于 1978 发明的算法，本文介绍的是 LLRBT。
红黑树的抽象表示
在红黑树中表示 2-3-4 树的 3 树和 4 树会用红链接来表示。如下图所示 (markdown 没有文本色彩支持，本文用//或\\来表示红色链接)：
A B B A A B C B
/ | \ <=红黑树表示=> // 或者 => \\ / | | \ <=红黑树表示=> // \\
A B A C
红黑树的插入
红黑树在插入时也通过旋转来降低或者升高树的高度 (关于旋转请看我的另一篇文章)。不同的是红黑树插入节点的方式是按照 2-3-4 树插入节点的方式来进行的。2-3-4 树每插入一个节点会对树自底向上进行调整 (合并或分裂)，红黑树也是对应于 2-3-4 树进行同样的操作。2-3-4 树通过将 3 树合并为 4 树，4 树分裂为俩个 2 树。红黑树通过旋转来做这些操作。
在2树中插入一个节点：
D 插入C=> D
//
C
<===等同于3树===> C D
C D / | \
C 插入D=> \\ 左旋=> //
D C
在3树中插入一个节点:
C H H H
/ | \ 红黑树表示=> // // C A C H
C 插入 A=> C 右旋=> // \\ 2-3-4树表示=> / | | \
// A H
A
H H H
A H 红黑树表示=> // // // C A C H
/ | \ A 插入 C=> A 左旋=> A 右旋=> // \\ 2-3-4树表示=> / | | \
\\ // A H
C C
A C C C
/ | \ 红黑树表示=> // // \\ A C H
A 插入 H=> A H 2-3-4树表示=> / | | \
从上图可以看出，LLRBT 之所以使用左倾 (left-leaning) 是为了将 3 树限制为一种，以便更容易的将 3 树转为 4 树，来减少实现上复杂度。下图是 4 节点的分裂。
/ //
A C H 4树分裂为俩个2树=> C C C
/ | | \ / \ 红黑树表示=> // \\ 分裂=> / \ <---将红链提上去
A H A H A H
红黑树在最初插入时使用的方式和普通的二叉树一样，递归查找到树的底部，然后将新节点插入到树的底部。在递归往回弹的时候对整颗树进行旋转调整，和 2-3-4 树使用相同的方式（3 树变 4 树，4 树分裂成俩个 2 树）来调整整颗树的高度。
红黑树的删除
红黑树的删除方法非常复杂。删除任意一个节点，红黑树会像 BST 一样会从右树的最左边找到一个节点进行替换并删除。所以实现红黑树的关键一点就是要实现 DeleteMin 方法。LLRBT 结构是没有 parent 节点的，在删除一个节点是并不能像 AVL 树那样在删除后再旋转。LLRBT 在查找要删除的节点时就会对树进行调整，它会将要删除节点的那个方向的树通过旋转将树的高度升高一层。
下图是在 DeleteMin 方法中将树的左边升高一层
// <----因为树是向左边递归的， /
H 所以到 H 的链都是红的 H
/ \ // \\
C S 颜色反转，将红色向下传=> C S
/ /
B B
这时如果 S 节点的left为红色，需要对其再做两次旋转
/ / /
H H P
// \\ // \\ // \\
C S 右旋S=> C P 左旋 H=> H S
/ // / \\ //
B P B S C
/
B
//
再将颜色反转回来=> P
/ \
H S
//
C
/
B
上面做的这些操作的最终目的就是将树的最底部要删除的节点变为红色，这样是为了在删除的时候避免要删除的节点为 2 树。因为删除 3 树中的一个节点是不需要做其他转换可以直接删除的。在删除后需要重新自底向上修复整颗树的平衡。这样的删除方式看起来非常慢，实际上确实非常慢。即使在没有找到要删除的节点也会递归进行旋转 - 修复这一过程。另外这里的删除使用的抽象方式并不是 2-3-4 树的删除方式，实际上使用的是 2-3 树的抽象方式。在红树向下传递的过程中最终的叶子会是颗 3 树，而不会是 4 树。Sedgewick 的 PPT 里面并没有说到这个问题。他的另一篇论文才说到了这个问题。
PS： 本人实现的 Red Black Tree。 Sedgewick 的 PPT 里面有两个错误. 1. 在 deleteMax 方法中向下递归是 deleteMax(h.left) 应该是 deleteMax(h.right)。 2. 在 delete 方法中需要添加当前节点是否为空的判断，否则递归到空节点时程序会挂掉。
以前研究过算法导论里的红黑树，光插入操作就有至少 4 中情况，会涉及到叔叔，爷爷之类的节点。删除操作则更复杂。
当年尝试过从根本上理解红黑树，也只能想通插入的那些操作。工作后基本没用过，都忘得差不多了。
能不能结合实践讲一下呢，比如我有 5 台交换机，我怎么把这些设备名抽象到这种这种数据结构之中去，从数据结构我能知道他们的这种连接关系。 A / \ B C / \ D E
