第13章 红黑树(1)
第12章我们讨论了在高度为h的二叉查找树能够在O(h)时间完成任何动态集操作，比如查找（SEARCH）,前躯（PREDECESSOR）,后继(SUCCESSOR),最小值（MINIMUM），最大值（MAXIMUM）,插入（INSERT）和删除（DELETE）操作。因此，如果树高矮的时候这些动态集的操作是很快的。如果树高很高的话，那么这些动态集的操作就没有链表快了。红黑树是众多“均衡”查找树中的一种，它可以保证基本的动态集操作在最坏的情况下运行时间为O(lg n)。
13.1 红黑树的性质
红黑树是一棵二叉查找树，并且每个结点都附加一个额外的存储位：结点颜色，它的值可以是红色或者黑色。通过对根到叶子路径上结点图色的限制，红色黑树保证没有哪一条路径是其它路径的二倍长，所以这棵树大致上是平衡的。
现在每个结点都包含属性color,key,left,right和p。如果结点没有孩子或者双亲结点不存在（译者著：根结点没有双亲结点，普通的叶子结点没有孩子），那么该结点的这些属性（译者著：孩子或者双亲指针）值是NIL。我们把这些NIL当作二叉树中指向叶子（外部结点）的指针，正常包含key的结点为树的内部结点。
红黑树是一种二叉查找树，并且还满足下面的红黑性质：
- 每个结点不是红色就是黑色。
- 根结点是黑色的。
- 每个叶子结点（NIL）都是黑色的。
- 如果一个结点是红色的，那么它所有的孩子都是黑色的。
- 对于每一个结点，从当前结点到后代的叶子的路径上包含黑色结点的数量是相同的。
图13.1(a)展示了一棵红黑树的例子。
为了方便处理边界条件，在实现红黑树的代码里，我们使用了一个哨兵结点也替换NIL（查看第238页）。对于一棵红黑树T，哨兵T.nil是跟树中普通结点有同样属性的一个对象。它的颜色是黑色，它的其它属性-p,left,right和key-可以是任意值。如图13.1(b)所示，所有NIL指针都替换成指向哨兵结点T.nil.
我们使用哨兵结点是为了我们可以把x结点的NIL孩子看成是x的一个普通的孩子。尽管我们可以在树中我可以用不同的哨兵结点替换每一个NIL，第一个NIL的双亲都这样定义，但是这样将会很浪费空间。所以，我们使用一个哨兵结点T.nil代替所有NIL-所有以的叶子结点和根结点的双亲。哨兵结点的属性p,left,right和key都是无关紧要的，为了方便我们在方法里还是设置了它们。
我们基本上只对内部结点有兴趣，是因为它们含有key值。本章剩下的部分，当我们绘制红黑树的时候，我们会忽略叶子，如图13.1(c)所示。
我们把从结点x，不包括到x,向下到叶子结点的结点的任意路径上黑色结点的个数称为结点的black-height,记作bh(x)。通过性质5，black-height概念是明确的，结点所有下降的路径上都有数量相同的黑色结点。我们把红黑树root的black-height定义成这棵红黑色树的black-height。
下面引理说明了为什么红黑树是一种好的搜索树。
引理13.1
具有n内部结点的红黑树的高度最高为2lg(n+1)。
证明
首先，我们论证对于以任意结点x为根的子树包含至少2^bh(x) – 1个内部结点。我们通过照给x的高度来证明这个论点。如是x的高度是0，那x一定是叶子(T.nil)，以x为根的子树的确包含至少2^bh(x) – 1=2^0-1=0个内部结点。接下来归纳，如果结点x的高度为正数并且是两个孩子的内部结点。每个孩子只的black-height是bh(x)或者bh(x-1),这取决于他们自身的颜色。由于x的孩子的高度肯定比x自身要低，我们用归纳假设得出每个孩子至少包含2^(bh(x)-1) – 1个内部结点。那么以x为根的子树包含至少2^(bh(x)-1) – 1 + 2^(bh(x)-1) – 1 +1 = 2^bh(x)-1个内部结点，这就证明了上面的提出的论点。
为了完成引理的证明，假设树高为h。根据性质4，从根的出发到达叶子结点的任意路径，不包括根结点，至少有一半结点是黑色的。因此，根结点的black-height至少h/2;所以
n ≥ 2^(h/2) – 1.
把1移到左边再把两边取对数，lg(n+1) ≤h/2,或h≤2log(n+1)
由这个引理可以得出，我们可以用红黑色树去实现运行时间为O(lg n)动态集操作查找（SEARCH）,最小值（MINIMUM）,最大值（MAXIMUM）,后继（SUCCESSOR）和前驱（PREDECESSOR），因为在高度为h（第12章介绍的那样）的二叉查找树中每个操作的运行时间为O（h）,n结点的任意红黑树是高为O(lg n)的二叉树。（当然，在第12章中使用NIL指针要替换成T.nil。）对于给定的红黑树用第12章的TREE-INSERT和TREE-DELETE算法运行时间也是O(lg n)，但是这两个算法不能直接支持动态集操作INSERT和DELETE，因为它们不保证修改过的二叉树是否仍然是红黑树。然而，在13.3和13.4节，我们将看到如何在O(lg n)运行时间内实现这两种操作。
图13.1 这是一棵红黑树，黑色表示黑结点，阴影表示红结点。红黑树中的每一个结点，不是红色的就是黑色的，红结点的孩子都是黑色的，从某结点到叶子结点的所有路径中的有相同数量的黑结点。（a）每一个叶子，用NIL来表示，是黑色的。每一个非NIL结点都标记它的black-height；NIL结点的black-heigth为0.(b)同样的红黑树，但是用一个T.nil替换了所有的NILL，它总是黑色的，并且它的black-height被忽略。根结点的双亲是哨兵。（c）同样的红黑色树，但是叶子结点和根的双亲被完全忽略了。在本章的剩余部分，我们将用这种方式绘制红黑树。
练习
13.1-1 按照13.1(a)的方式，绘制高度为3的完全二叉查找树,key值为{1,2,…,15}。添加NIL叶子结点并分别画出black-height为2，3，4三种不同方式的红黑树。
13.1-2 画出向图13.1中的树调用TREE-INSERT，key为36的结点后的红黑树。如果插入的结点着成红色它还是一棵红黑树吗？如果着成黑色呢？
13.1-3 让我定义一种relaxed red-black树，它一棵二叉查找树，并且满足红黑树的性质1，3，4和5。换句说，根可能是红色或者黑色。假设有一棵relaxed red-black树T，它的根是红色的。如果我们将根着成黑色树T其它的都不变，那么着色后它是一棵红黑树吗？
13.1-4 假设在红黑色树我们让每个红色结点都被它的黑色双亲结点“吸纳”，那么红色结点的孩子都变成黑色双亲的孩子。（忽略key的变化）所有红色结点被吸纳后，黑色结点可能的度是多少？你能说出结果这个棵树的高度是多少吗？
13.1-5 证明在红黑树中从结点x开始到叶子最长路径的长度最多是从结点x开始到叶子的最短路径的两倍。
13.1-6 在高度为k的红黑树中内部结点数量最多是多少？最少是多少？
13.1-7 请描述下n个key构成的红黑树，它的红色内部结点与黑色内部结点比值最大，这个最大比值是多少？那比值最小的红黑树是什么样的，比值是多少？
全文下载：第13章 红黑树