1、教你透彻了解红黑树二叉查找树由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）, 排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 任意结点的左、右子树也分别为二叉查找树。 没有键值相等的结点（no duplicate nodes）。因为，一棵由 n 个结点，随机构造的二叉查找
2、树的高度为 lgn，所以顺理成章，一般操作的执行时间为 O（lgn）.（至于 n 个结点的二叉树高度为 lgn 的证明，可参考算法导论 第 12 章 二叉查找树 第 12.4 节）。但二叉树若退化成了一棵具有 n 个结点的线性链后，则此些操作最坏情况运行时间为 O（n）。后面我们会看到一种基于二叉查找树-红黑树，它通过一些性质使得树相对平衡，使得最终查找、插入、删除的时间复杂度最坏情况下依然为 O（lgn ）。红黑树前面我们已经说过，红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为 O(
3、log n)。但它是如何保证一棵 n 个结点的红黑树的高度始终保持在 h = logn 的呢？这就引出了红黑树的 5 条性质：1）每个结点要么是红的，要么是黑的。 2）根结点是黑的。 3）每个叶结点（叶结点即指树尾端 NIL 指针或 NULL 结点）是黑的。 4）如果一个结点是红的，那么它的俩个儿子都是黑的。 5）对于任一结点而言，其到叶结点树尾端 NIL 指针的每一条路径都包含相同数目的黑结点。 正是红黑树的这 5 条性质，使得一棵 n 个结点是红黑树始终保持了 logn 的高度，从而也就解释了上面我们所说的“红黑树的查找、插入、删除的时间复杂度最坏为 O(log n)”这一结论的原因。如下
4、图所示，即是一颗红黑树(下图引自 wikipedia：http:/ “叶结点 “ 或“NULL 结点“，它不包含数据而只充当树在此结束的指示，这些结点以及它们的父结点，在绘图中都会经常被省略。树的旋转知识当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。为了继续保持红黑树的性质，我们可以通过对结点进行重新着色，以及对树进行相关的旋转操作，即修改树中某些结点的颜色及指针结构，来达到对红黑树进行插入或删除结点等操作后，继续保持它的性质或平衡。树的旋转，分为左旋和右旋，以下借助图来做形象的解释和介绍：1.左旋如上图所示：当在某个结点 pivot 上，做左旋操作时，我们
5、假设它的右孩子 y 不是 NILT，pivot 可以为任何不是NILT的左孩子结点。左旋以 pivot 到 y 之间的链为 “支轴”进行，它使 y 成为该孩子树新的根，而 y 的左孩子 b 则成为pivot 的右孩子。左旋操作的参考代码如下所示（以 x 代替上述的 pivot）：LEFT-ROTATE(T, x) 1 y rightx Set y. 2 rightx lefty Turn ys left subtree into xs right subtree. 3 plefty x 4 py px Link xs parent to y. 5 if px = nilT 6 then roo
6、tT y 7 else if x = leftpx 8 then leftpx y 9 else rightpx y 10 lefty x Put x on ys left. 11 px y 2.右旋右旋与左旋差不多，再此不做详细介绍。对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。红黑树的插入要真正理解红黑树的插入和删除，还得先理解二叉查找树的插入和删除。磨刀不误砍柴工，咱们再来分别了解下二叉查找树的插入和删除。二叉查找树的插入如果要在二叉查找树中插入一个结点，首先要查找到结点插入的位置，然后进行插入
7、，假设插入的结点为 z 的话，插入的伪代码如下：TREE-INSERT(T, z)1 y NIL2 x rootT3 while x NIL4 do y x5 if keyz keyx6 then x leftx7 else x rightx8 pz y9 if y = NIL10 then rootT z Tree T was empty11 else if keyz keyy12 then lefty z13 else righty z可以看到，上述第 3-7 行代码即是在二叉查找树中查找 z 待插入的位置，如果插入结点 z 小于当前遍历到的结点，则到当前结点的左子树中继续查找，如果 z
8、大于当前结点，则到当前结点的右子树中继续查找，第 9-13 行代码找到待插入的位置，如果 z 依然比此刻遍历到的新的当前结点小，则 z作为当前结点的左孩子，否则作为当前结点的右孩子。红黑树的插入和插入修复现在我们了解了二叉查找树的插入，接下来，咱们便来具体了解红黑树的插入操作。红黑树的插入相当于在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作。假设插入的结点为 z，红黑树的插入伪代码具体如下所示：RB-INSERT(T, z) 1 y nilT 2 x rootT 3 while x nilT 4 do y x 5 if keyz keyx 6 then x leftx 7 e
9、lse x rightx 8 pz y 9 if y = nilT 10 then rootT z 11 else if keyz keyy 12 then lefty z 13 else righty z 14 leftz nilT 15 rightz nilT 16 colorz RED 17 RB-INSERT-FIXUP(T, z) 我们把上面这段红黑树的插入代码，跟我们之前看到的二叉查找树的插入代码，可以看出，RB-INSERT(T, z)前面的第 1-13 行代码基本就是二叉查找树的插入代码，然后第 14-16 行代码把 z 的左孩子、右孩子都赋为叶结点 nil，再把 z 结点着为
10、红色，最后为保证红黑性质在插入操作后依然保持，调用一个辅助程序 RB-INSERT-FIXUP 来对结点进行重新着色，并旋转。换言之 如果插入的是根结点，因为原树是空树，此情况只会违反性质 2，所以直接把此结点涂为黑色。 如果插入的结点的父结点是黑色，由于此不会违反性质 2 和性质 4，红黑树没有被破坏，所以此时也是什么也不做。但当遇到下述 3 种情况时： 插入修复情况 1：如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色 插入修复情况 2：当前结点的父结点是红色 ,叔叔结点是黑色，当前结点是其父结点的右子 插入修复情况 3：当前结点的父结点是红色 ,叔叔结点是黑色，当前结
11、点是其父结点的左子又该如何调整呢？答案就是根据红黑树插入代码 RB-INSERT(T, z)最后一行调用的 RB-INSERT-FIXUP（T,z）所示操作进行，具体如下所示：RB-INSERT-FIXUP（T,z）1 while colorpz = RED 2 do if pz = leftppz 3 then y rightppz 4 if colory = RED 5 then colorpz BLACK Case 1 6 colory BLACK Case 1 7 colorppz RED Case 1 8 z ppz Case 1 9 else if z = rightpz 10 t
12、hen z pz Case 2 11 LEFT-ROTATE(T, z) Case 2 12 colorpz BLACK Case 3 13 colorppz RED Case 3 14 RIGHT-ROTATE(T, ppz) Case 3 15 else (same as then clause with “right“ and “left“ exchanged) 16 colorrootT BLACK 下面，咱们来分别处理上述 3 种插入修复情况。插入修复情况 1：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。即如下代码所示：1 while colorpz = RED
13、 2 do if pz = leftppz 3 then y rightppz 4 if colory = RED 此时父结点的父结点一定存在，否则插入前就已不是红黑树。与此同时，又分为父结点是祖父结点的左子还是右子，对于对称性，我们只要解开一个方向就可以了。在此，我们只考虑父结点为祖父左子的情况。同时，还可以分为当前结点是其父结点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。对策：将当前结点的父结点和叔叔结点涂黑，祖父结点涂红，把当前结点指向祖父结点，从新的当前结点重新开始算法。即如下代码所示：5 then colorpz BLACK Case 1 6 colory BLACK
14、Case 1 7 colorppz RED Case 1 8 z ppz Case 1 针对情况 1，变化前（图片来源：saturnman ）当前结点为 4 结点 ：变化后：插入修复情况 2：当前结点的父结点是红色 ,叔叔结点是黑色，当前结点是其父结点的右子对策：当前结点的父结点做为新的当前结点，以新当前结点为支点左旋。即如下代码所示：9 else if z = rightpz10 then z pz Case 211 LEFT-ROTATE(T, z) Case 2如下图所示，变化前当前结点为 7 结点：变化后：插入修复情况 3：当前结点的父结点是红色 ,叔叔结点是黑色，当前结点是其父结点的
15、左子解法：父结点变为黑色，祖父结点变为红色，在祖父结点为支点右旋，操作代码为：12 colorpz BLACK Case 313 colorppz RED Case 314 RIGHT-ROTATE(T, ppz) Case 3最后，把根结点涂为黑色，整棵红黑树便重新恢复了平衡。如下图所示当前结点为 2 结点变化后：红黑树的删除ok，接下来，咱们最后来了解，红黑树的删除操作。“我们删除的结点的方法与常规二叉搜索树中删除结点的方法是一样的，如果被删除的结点不是有双非空子女，则直接删除这个结点，用它的唯一子结点顶替它的位置，如果它的子结点分是空结点，那就用空结点顶替它的位置，如果它的双子全为非空，我们就把它的直接后继结点内容复制到它的
