《红黑树详解17页》由会员分享，可在线阅读，更多相关《红黑树详解17页（17页珍藏版）》请在金锄头文库上搜索。
1、红黑树详解在本文，我将比较透彻地讲解红黑树。本文适合那些有对二叉树有一定的基础，并且熟悉C语言的读者。本文最主要的参考资料是Introduction to Algorithms 3rd Edition。1.1 二叉查找树1.1.1 基本概念二叉查找树是在数据结构中比较重要的数据结构之一，从外部看它满足集合性质，具有查找，插入和删除的基本功能，同时还可以求最大值和最小值。由于二叉查找树独特的性质，它特别适合用来存储动态集合。定义：对于二叉树上的所有结点x，如果y是x的左子树，那么y.key x.key。如果y是x的右子树，那么y.key x.key，这样的二叉树就称为二叉查找树(Binary S
2、earch Tree)。我们关心的二叉查找树的逻辑结构，下面的两棵二叉树：图1 二叉查找树。(a)这一棵高度为3的二叉树，因为10比15小，所以10在15的左子树上；同理在以10为根的左子树里，7比10小所以7在左子树上，12在10为根的子树的右子树上；20在以15为根的右子树上。(b)这是一棵高度是4的二叉查找树，它的所有key与图(a)是一样的。在图(a)中，查找最坏的情况是7和12，它们需要经过3次比较才能找到，而图(b)最坏情况是20，需要经过4次比较才能找到。要想二叉树的查找的花费时间小，我们尽可能让二叉树不出现类以于单链形态的二叉树，让树的高度尽量的低。对于高度为h的二叉查找树，从
3、树根对叶子最坏的情况是比较h次。也就是说，对于高度为h的二叉查找树的最坏查找情况的运行时间是O(h)。二叉树的查找效率取决于树的高度。1.1.2 操作二叉树做为动态集，它有查找、插入、删除、最大值、最小值、前驱和后继这些基本操作。为了后序的方便，我们定义了结点和树，另外我们还用0表示空子树。查找在二叉查找树中根据给定的key找到该结点。由于二叉树的性质，我们就知道，如果目标key比当前结点的key要小，那么目标结点必定在当前结点的左子树上。最小值与最大值我们来分析一下最小值的位置。我们认为最小值的位置是从根出发一直沿结点的左子树直到某个结点x的左子树为空，那么这个结点x就是整个二叉树中key最
4、小的结点。注意，我们并没有做任何key的比较。证明：假设这个结点x不是最小值，另外有最小值结点y，那么y.k x.k。如果y是x的祖先，因为x位于y的左子树上，那么x肯于定比y要小，所以y不是x的祖先。如果y不是x的祖先，假设y与x的最小的共同祖先的z，又因为y不是x的祖先，所以y在z的右子树上，所以z.k x.k，与假设的y.k x.k矛盾，所以假设不成立，x是二叉查找树中key最小结点。最大值的分析方法也是一样的。前驱和后继前驱与后继定义来源于二叉树中序遍历的key序列。我们知道二叉的中序遍历的key序列是一个升序序列。在二叉查找树中，对于结点x，如果有结点y，满足y.keyx.key并且
5、y是这些结点中key最小的，那么y就称之为x的后继。同理，在二叉查找树中，对于结点x，如果有结点y，满足y.keyr)，这时候y已经从树中脱离了，然后我们将y嫁接到z的右孩子的双亲上，这样y就成了z右孩子的双亲了，这和情形b是同一种情况了。下面是删除的代码：1.1.3 实现参考附件：bstree.c。1.1.4 思考题1. Bunyan教授认为他发现了二叉查找树的一个重要的性质。假设在二叉查找树上查找key为k的结点,并且key为k的结点是一个叶子结点。那么有三个集合：A，搜索路径的左边结点的集合；B，搜索路径上的结点的集合；C是搜索路径右边的结点集合。Buyan教授认为对于三个集合的任意值a
6、A，bB，cC一定满足abc。对于上面的观点，请给出最小可能一个的反例。2. 证明：在高度为h的二叉查找树上，我们实现的动态集基本操作:min，max，successor，predecessor，search，insert和delete的运行时间都是O(h)。3. 在二叉查找树的删除操作中，假设我们不取z的后继而取z的前驱替换z，请相应对称的代码。1.2 红黑树在上节的思考题中，我们证明了在高度为h的二叉查找树上，我们实现的动态集基本操作运行时间都是O(h)。总而言之，树度h决定查找效率。如果我们通过某种方法能够将二叉树尽可能的低，那么二叉树的查找效率将会大大地提高。对于一个含有n结点的最坏的
7、情况是这n个结点形成一条单链，那么二叉查找树的树高为n，运行时间为O(n)；那么最好情况是n个结点形了一棵完全二叉树。所谓完全二叉树是指对于一棵高度为h的二叉树，除第h层外，其它各层的结点数都达到最大个数，并且第h层所有的结点都连续集中在最左边，这样的二叉树称为完全二叉树。那么h介于lg n与lg n+1之间，也就是说运行时间为O(lg n)。可以说它的效率是极高的。1.2.1 基本概念如果我把二叉查找树的每个结点都涂上红色或者黑色。如果它满足下面的5个性质，那么我们就称它为红黑树（Red Black Tree）：1 每个结点不是红色就是黑色。2 根结点是黑色的。3 每个叶子结点（NIL）都是
8、黑色的。4 如果一个结点是红色的，那么它所有的孩子都是黑色的。5 对于每一个结点，从当前结点到后代的叶子的路径上包含黑色结点的数量是相同的。根据红黑树的性质，我们可得出下面的结论：具有n内部结点的红黑树的高度最高为2lg(n+1)。在证明这个结论之前，我们来看看红黑树的表示。每个结点到叶子结点（NIL）经过的黑色结点的个数（包括自已）称之为黑高度(black-height)。我们把NIL称之为外部结点，那些带有key的“合法”的结点称之为内部结点。图6 红黑树的表示。key为64的结点的黑高度为3，key为26，81，14，44的结点黑高度为2，key为5，19，30，76，92的结点黑高度为
9、1。证明：我们将红色结点吸附到黑色的双亲结点上，那么一个黑色结点最多可以吸附2个结点，并且可以有4个孩子，那么就形成了一个大结点，如图7所示。这样树我称之为234树。红黑树的数学本质就是234树，并且所有的“叶子”结点的高度都是相等的。不难看出，黑高度就是这棵234树的高度。图7 将图6中的红色结点吸附到双亲结点上，这样对应数学结构为234树。对于高度为h并且所有的“叶子”结点的高度都是相等的234树最多有多少个结点呢？要想结点最多，并且所有的“叶子”结点的相同。那么它就是一棵满234树，每个结点的出度4，每个结点包含3个内部结点，那么对于高度为h的234树，则树的结点个数n，满足：（公式1）
10、对于高度为h并且所有的“叶子”结点的高度都是相等的234树最少有多少个结点呢？要想结点最少，那么它就退化出了满二叉树了。所以，树的结点个数n满足：（公式2）由公式2得出：两边取对数即。这里的h是234树的高度，由前面所述，红黑数的黑高度就是对应234树的高度。对于黑高度了h，由性质2、3、4得出红色结点不可能多于黑色结点。所以结点个数不大于黑高度的2倍。所以具有n内部结点的红黑树的高度最高为2lg(n+1)，证毕。我们证明的结论说明红黑树的搜索运行时间为O(2lg(n+1)也就是O(lg n)。为了方便操作，我们引入一个NIL结点，这个NIL结点是跟普通的结点一样，不过我们只使用color这个
11、域，因为NIL结点是黑色的。我们定义了结点的颜色，同时每个结点都增加了一个c域来表示结点的颜色。除此之外我们还为树定义了一个nil结点，之前实现的二叉查找树中指向NIL都改为指向T-nil。1.2.2 查找因为红黑树本身就是一棵二叉查找树，所以对红黑树的查找操作跟普通的二叉查找树的操作没有什么不一样，但注意的时，在这里我们已经用T.nil取代了0。下面仅仅给出查找操作的代码，读者可以比较一下与普通的二叉查找树有什么不一样的地方。有两处不一样，第一处是x!=0替换成了x!=&T-nil，另外一处是在结尾出增加了对x是否是nil的判断，操作上的代码没有二致。对于前驱和后继，我就不举例了，有兴趣的读者可以自行思考或者参考一下附件的实现。1.2.3 旋转在介绍红黑色的插入与删除前，我们介绍一下二叉树的旋转操作：旋转分为左旋(Left-Rotate)和右旋(Right-Rotate
