第13章 红黑树(3)
13.3 插入
我们可以在O(lg n)时间将一个结点插入到含有n结点的红黑树。为了插入结点，我们将TREE-INSERT方法（第12.3节）做稍稍的修改把树T当做普通的二叉查找树插入结点z，然后将z着成红色。（练习13.3-1让你解释一下为什么我们选择红色而不是黑色。）为了保持红黑树的性质，我们调用辅助方法RB-INSERT-FIXUP去着色和旋转。调用RB-INSERT(T,z)将结点z插入树T中，其中z结点已经包含填充了key。
TREE-INSERT和RB-INSERT方法有四个地方不一样。第一，所有TREE-INSERT使用NIL的地方都被替换成了T.nil。第二，在RB-INSERT的第14到15行，我们将z.left和z.right设置成了T.nil，是为了维护合适的树结构。第三，在第16行，我们将z着成红色。第四，由于将z着成红色将会导致红黑树的某个性质发生了违例，所有我们在第17行调用RB-INSERT-FIXUP(T,z)去恢复红黑树的性质。
为了理解RB-INSERT-FIXUP是如何工作的，我们将代码分成三个主要步骤去解释。首先，我们要判断在RB-INSERT中将z着成红色会出现哪些违反红黑树的性质的情况。其次，我们将考查第1到15行的while循环的目的。最后，我们将分析while循环体的的三种情况看它们是如何达到目的的。图13.4展示了RB-INSERT-FIXUP在红黑树上的执行过程的一个例子。
在调用RB-INSERT-FIXUP之前红黑树的哪些性质将不能保持？性质1将会继续保持，同理性质3，因为新插入的红色结点的两个孩子是T.nil。性质5，内容是从指定结点出发到叶子结点的每条简单路径上的黑色结点的数量是相同，这个性质也跟之前一样的，是因为结点z替换了（黑色）哨兵结点，并且z结点带有哨兵结点的红色结点。因此，只有性质2，要求根结点是黑色的，和性质4，红色结点不能有红色结点的孩子。这两个可能的不能保持的情况都是由z着成红色造成的。性质2是当z是根结点的时候不能保持，性质4是当z的双亲是红色的不能保持。图13.4(a)展示了z插入后违反性质4的一个例子。
图13.4 RB-INSERT-FIXUP操作。(a)插入后的结点z。因为z和它的双亲都是红色的，所以发一次性质4违例。因为z的叔叔是红色的，所以适应于情形1。我们重新将结点着色并且将指针z从树上向上提升，结果如(b)所示。跟上面的情形一样，z的它的双亲双都是红色的，但是z的叔叔是黑色的。因为z是z.p的右孩子，所以适用于情形2。我们做一次左旋，结果如图(c)所示。现在z是双亲的左孩子，那它适用于情形3。重新着色并右转直到成为图(d)中的树，它一棵合法的红黑树。
第1到15行的while循环在每次迭代的开始都维护了下面三个不变式：
- 结点z是红色的
- 如果z.p是根，那么z.p是黑色的。
- 如果红黑树的性质招到破坏，那么最多只有一个性质被破坏，性质2或者性质4被破坏。如果是性质2，那是因为z是根并且是红色。如果性质4被破坏那是因为z和z.p都是红色的。
c部分，处理这些违反红黑树性质的部分，在RB-INSERT-FIXUP恢复红黑树性质上比(a),(b)部分更为重要，我们用它来了解程序代码中的情况。因为我们注意力聚集在z结点及它在树中的周围结点上，从(a)部分我们知道z是红色的。我们可以利用(b)部分知道z.p.p是存在的，我们在第2，3，7，8，13中引用到它。（译者注，因为b部分说根是黑色的，而且z.p也是红色的，所以z.p.p肯定存在。）
我们证明在第一次迭代时循环不变式是真的，每次迭代都维护这个不变式，在循环结束时，这个不变式将给我们提供一个很好性质。
我们从初始化和终止开始讨论。然后我们详细考查循环体是如何工作的，我们将讨论每次迭代的循环维护这个不变式。随后，我们将表明每次循环迭代后都有两种可能的结果：z指针向上移动或者做一些旋转后循环终止。
初始化：在第一次迭代前，我们用一棵合法的红黑树开始，然后我们插入了红色结点z。我们各种情况下调用RB-INSERT-FIXUP时不变式都是成立的：
当调用RB-INSERT-FIXUP时，z是被添加的红色结点。
如果z.p是根，那么z.p开始时就是黑色调用RB-INSERT-FIXUP不用修改。
当我们调用RB-INSERT-FIXUP时，我们已经看到性质1，3，5保持不变。
如果树的性质2不能保持，那么说明添加了红色的根结点z，z是树中的唯一一个内部结点。因为双亲和两个孩子都是哨兵结点，它们都是黑色的，树就不会违反性质4。因些违反性质2的情况，是整棵树中唯一一处破坏红黑树性质的地方。
如果树的性质4不能保持，由于结点z的孩子是黑色的哨兵并且在添加z前整个棵树没有其它的违反红黑性质的地方，那么这种违反一定是z和z.p都是红色的。而且，没有 对红黑树的其它性质的违反。
终止：当循环结束时，它是因为z.p是黑色才结束的。（如果z是根结点，那z.p是哨
兵T.nil,它也是黑色的）因此，在循环结束时，树不会违反性质4。通过循环不变式，仅仅只有性质2可能不满足。第16行也恢复了这个性质。所以在RB-INSERT-FIXUP结束时，所有的红黑树性质都满足了。
维护：在while循环里我们实际上需要考虑到6种情形，但有三种情形与另外三种情形是对称的，取决于第二行的z的双亲z.p是z的祖亲z.p.p的左孩子还是右孩子。我们仅仅给出了z.p是左孩子的解决方案的代码。结点z.p.p是存在的，是由于b部分的循环不等式，如是z.p是根，那么z.p是黑色的。因为我们仅当z.p是红色才会进入循环迭代，我们知道z.p肯定不是根。意味着z.p.p是存在的。
我们根据z双亲的兄弟或称作“叔叔”的颜色来区分情形1与情形3。第3行让y指向z的叔叔z.p.p.right，第4行测试y的颜色。如是y是红色的，我们执行情形1。否则，执行跳到情形2和情形3。所有的三种情况，z的祖亲是黑色的，是因为z.p是红色的，只有z和z.p是违反性质4。
情形1：z的叔叔是红色的
图13.5展示了情形1（第5到8行），z.p和y都是红色的时候属于这种情形。因为z.p.p和y是黑色的，我们将z.p和y都着成黑色，用来修复z和z.p都是红色的问题，并且我们z.p.p着成红色来保持性质5。我们把z.p.p当成新的结点z来重得while循环。在树上z指针向上移动了两层。
现在，我们证明情形1在下一次迭代前维护了循环不等式。我们用z来表示当前迭代中的结点z,那z’ = z.p.p来表示第1行下次迭代被为结点z的结点。
- 因为本次迭代将z.p.p着成了红色，结点z’在下一次迭代开始时是红色的。
- 结点z’.p是本次迭代的z.p.p.p，它的颜色没有改变。如是这个结点是根，它在本次迭代前是黑色的，并且在下次迭代开始是也保持黑色。
- 我们已经讨论了情形1维护了性质5，它不会破坏性质1或者3。
图13.5 RB-INSERT-FIXUP情形1的处理过程。性质4被破坏了，由于z和它的双亲z.p都是红色的。不管z是右孩子还是左孩子，我们操作方法都是一样的。每一个子树α，β，γ，δ和ε都有一个黑色的根，并且它们有相同的black-height。情形1改变了一些结点的颜色，为了保持性质5：从一结点向下到叶子结点都有相同数量的黑结点。while循环所z.p.p当成新的z继续下去。所以违反性质4都只可能发现在新红色z和它的双亲之间，如它的双亲是红色的，处理方法跟上面的一样。
情形2：z的叔叔是黑色的并且z是右孩子
情形3：z的叔叔是黑色的并且z是左孩子
在情形2和情形3中，z的叔叔的颜色是黑色的。我们通过z是z.p的左孩子还是右孩子来区分这两种情形。第10到11行形成了情形2，在图13.6中与情形上放在一起。在情形2中，结点z是双亲的右孩子。我们立即使用一次左旋变成了情形3（第12到14行），这种情形z变成了左孩子。因为z和z.p都是红色的，旋转影响了结点的black-height和性质5。不管直接的情形3还是通过情形2转化而来的，z的叔叔都是黑色的，否则的话将会执行情形1了。另外，z.p.p是存在的，在执行第2和3行时，我们已经讨论了这个结点是存在的，并且在第10行将z向上提升了一层然后在第11行向下降了一层，z.p.p仍然没有变化。在情形3中，我们将一些结点的颜色改变了并且做了一次右旋，这些是为了保持性质5，然后在一条线上就不存在两个红色的结点，就这样完成了。因为现在z.p是黑色的了，while循环不再进行下一次的迭代了。
图13.6 RB-INSERT-FIXUP情形2和3的处理过程。跟情形1一样，不管是情形2还是情形3由于z和z的双亲都是红色的而破坏了性质4。它的任意一棵子树α，β，γ，δ都有一个黑色的根（α，β，γ是根据性质4，δ如果不是黑色将执行情形1），并且它有相同的black-height。我们通过一次左旋将情形2转化成情形3，保持了性质5：从一结点向下到叶子结点都有相同数量的黑结点。情形3一些点颜色被改变了并且做了一次右转，也是为了保持性质5。然后while循环结束了，因为性质4满足了：在一条线上不再有两个红色结点。
现在我们来证明情形2与情形3保持了循环不等式。（正如我们讨论过的，z.p将会在第1的下次测试z.p将会是黑色，并且循环体将不再执行。）
- 情形2使z指向z.p，z.p是红色的。z和它的颜色在情形2和3中不再变化。
- 情形3使z.p着成黑色，所以如果z.p是下次迭代开始的根，那么它就是黑色的。
- 跟情形1一样，性质1、3和5在情形2，3中也得以保持。由于在情形2和3中，结点z不是根，我们知道这不会破坏性质2，由于唯一结着成红色的结点在情形3变成一个黑色结点的子女。情形2和3修正了性质4的破坏，同时它们也不会引进新的破坏。
在讨论每次循环迭代维护不变式时，我们也证明了RB-INSERT-FIXUP正确地恢复了红黑树的性质。
分析
RB-INSERT的运行时间是多少呢？由于n结点的红黑树的高度是O(lg n)，RB-INSERT第1到16行花费了O(lg n)时间。在RB-INSERT-FIXUP中，while循环只有遇到情形1的时候才会重复循环，然后z向树上移动两层。while循环执行的总次数因此是O(lg n)。因此RB-INSERT总共花了O(lg n)的时间。更有意思的是，它旋转次数决不会多于两次，因为如果执行了情形2或者情形3,while循环就结束了。
练习
13.3-1 在RB-INSERT的第16行，我们将新插入的结点z设置成了红色。观察如果我们选择将z的颜色设置成黑色，那么红黑树的性质4会不会破坏。为什么我不选择将z设置成红色？
13.3-2 成功将key为41,38,31,12,19,8都插入空的红黑树后，画出这棵红黑树。
13.3-3 假设在图13.5和图13.6中任意子树α，β，γ，δ和ε的back-height是k。标记每个结点的black-height去验证图示的转换能保持性质5。
13.3-4 Teach教授担心RB-INSERT-FIXUP可能会设置T.nil.color为红色，这样的话当z是根的时候循环将不会结点。通过证明RB-INSERT-FIXUP决不会将T.nil.color设置成红色来说明这位教授的担心是没有必要的。
13.3-4 假设红黑树是通过RB-INSERT插入n结点形成的。证明如果n>1,那么树中至少有一棵红结点。
13.3-6 考虑一下，如果红黑树表示没有存储双亲结点的指针，应该如何有效地实现RB-INSERT。
全文下载：第13章 红黑树