大数据

当前位置:首页 > 大数据

《算法导论》第十二章

第十二章  二叉搜索树





搜索树数据结构支持许多动态集合操作,包括SEARCH、MINIMUM、 MAXIMUM、PREDECESSOR、SUCCESSOR、INSERT和DELETE等。因此,我们使用一棵搜索树既可以作为一个字典又可以作为一个优先队列。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于有n个结点的一棵完全二叉树来说,这些操作的最坏运行时间为Θ(lgn)。然而,如果这棵树是一条n个结点组成的线性链,那么同样的操作就要花费Θ(n)的最坏运行时间。在12.4节中,我们将看到一棵随机构造的二叉搜索树的期望高度为O(lgn),因此这样一棵树上的动态集合的基本操作的平均运行时间是Θ(lgn)。

实际上,我们并不能总是保证随机地构造二叉搜索树,然而可以设计二叉搜索树的变体,来保证基本操作具有好的最坏情况性能。第13章给出了一个这样的变形,即红黑树,它的树高为O(lgn)。第18章将介绍B树,它特别适用于二级(磁盘)存储器上的数据库维护。

在给出二叉搜索树的基本性质之后,随后几节介绍如何遍历一棵二叉搜索树来按序输出各个值,如何在一棵二叉搜索树.上查找一个值,如何查找最小或最大元素,如何查找一个元素的前驱和后继,以及如何对一棵二叉搜索树进行插入和删除。树的这些基本数学性质见附录B。


12.1 什么是二叉搜索树

顾名思义,一棵二叉搜索树是以一棵二叉树来组织的,如图12-1所示。这样一棵树可以使用一个链表数据结构来表示,其中每个结点就是一个对象。除了key和卫星数据之外,每个结点还包含属性left、right 和p,它们分别指向结点的左孩子、右孩子和双亲。如果某个孩子结点和父结点不存在,则相应属性的值为NIL.根结点是树中唯一父指针为NIL的结点。

QQ截图20220516104834.jpg

图12-1二叉搜索树。 对任何结点x,其左子树中的关键字最大不超过x. key,其右子树中的关键字最小不低于x. key。不同的二叉搜索树可以代表同一组值的集合。大部分搜索树操作的最坏运行时间与树的高度成正比。(a)- 棵包含6个结点、高度为2的二叉搜索树。(b)一棵包含相同关键字、高度为4的低效二叉搜索树

二叉搜索树中的关键字总是以满足二叉搜索树性质的方式来存储:

设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点,那么y. key≤x. key。如果y是x右子树中的一个结点,那么y. key≥x. key。

因此,在图12-1(a)中,树根的关键字为6,在其左子树中有关键字2、5和5,它们均不大于6;而在其右子树中有关键字7和8,它们均不小于6。这个性质对树中的每个结点都成立。例如,树根的左孩子为关键字5,不小于其左子树中的关键字2并且不大于其右子树中的关键字5。

二叉搜索树性质允许我们通过一个简单的递归算法来按序输出二叉搜索树中的所有关键字,这种算法称为中序遍历(inordertreewalk)算法。这样命名的原因是输出的子树根的关键字位于其左子树的关键字值和右子树的关键字值之间。(类似地,先序遍历(preorder tree walk)中输出的根的关键字在其左右子树的关键字值之前,而后序遍历(postordertreewalk)输出的根的关键字在其左右子树的关键字值之后。)调用下面的过程INORDER TREE-WALK(T. root),就可以输出一棵二叉搜索树T中的所有元素。

QQ截图20220516105124.jpg

作为一个例子,对于图12-1中的两棵二叉搜索树,中序遍历输出的关键字次序均为2,5, 5,6, 7, 8。根据二叉搜索树性质,可以直接应用归纳法证明该算法的正确性。

遍历一棵有n个结点的二叉搜索树需要耗费Θ(n)的时间,因为初次调用之后,对于树中的每个结点这个过程恰好要自己调用两次:一次是它的左孩子,另一次是它的右孩子。下面的定理给出了执行一次中序遍历耗费线性时间的一个证明。

定理12. 1  如果 x是一棵有n个结点子树的根,那么调用INORDER TREE-WALK(x)需要Θ(n)时间。

证明  当 INORDER-TREE-WALK作用于一棵有n个结点子树的根时,用T(n)表示需要的时间。由于INORDER TREE-WALK要访问这棵子树的全部n个结点,所以有T(n)=Ω(n)。下面要证明T(n)=O(n)。

由于对于一棵空树,INORDER-TREE-WALK需要耗费一个小的常数时间(因为测试x≠NIL),因此对某个常数c>0,有T(O)=c。

对n>0,假设调用INORDER TREE-WALK作用在一个结点x上,x结点左子树有k个结点且其右子树有n-k-1个结点,则执行INORDER- TREE-WALK(x)的时间由T(n)≤T(k)+T(n-k- 1)+d限界,其中常数d>0。此式反映了执行INORDER TREE-WALK(x)的一个时间上界,其中不包括递归调用所花费的时间。

使用替换法,通过证明T(n)≤(c+d)n+c,可以证得T(n)=O(n)。对于n=0,有(c+d) · 0+c=c=T(0)。对于n>0,有

T(n)≤T(k)+ T(n-k-1)+d= ((c+d)k +c)+(c+d)(n-k-1)+c)+d = (c+d)n+c-(c+d)+c+d= (c+d)n十c

于是,便完成了定理的证明。



练习

12.1-1  对于关键字集合{1, 4,5,10,16, 17,21},分别画出高度为2、3、4、5和6的二叉搜索树。

12.1-2  二叉搜索树性质与最小堆性质(见6.1节)之间有什么不同?能使用最小堆性质在O(n)时间内按序输出一棵有n个结点树的关键字吗?可以的话,请说明如何做,否则解释理由。

12.1-3 设计一个执行中序遍 历的非递归算法。(提示:一种容易的方法是使用栈作为辅助数据结构;另一种较复杂但比较简洁的做法是不使用栈,但要假设能测试两个指针是否相等。)

12.1-4 对于一棵有n个结点的树,请设计在Θ(n)时间内完成的先序遍历算法和后序遍历算法。

12.1-5 因为在基于比较的排序模型中,完成n个元素的排序,其最坏情况下需要Ω(n lgn)时间。试证明:任何基于比较的算法从n个元素的任意序列中构造一棵二叉搜索树,其最坏情况下需要Ω(nlgn)的时间。


12.2 查询二叉搜索树

我们经常需要查找一个存储在二叉搜索树中的关键字。除了SEARCH操作之外,二叉搜索树还能支持诸如MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR的查询操作。本节将讨论这些操作,并且说明在任何高度为h的二叉搜索树上,如何在O(h)时间内执行完每个操作。

查找

我们使用下面的过程在一棵二叉搜索树中查找一个具有给定关键字的结点。输入一个指向树根的指针和一个关键字k,如果这个结点存在,TREE SEARCH返回一个指向关键字为k的结点的指针;否则返回NIL.。

QQ截图20220516110019.jpg

这个过程从树根开始查找,并沿着这棵树中的一条简单路径向下进行,如图12-2所示。对于遇到的每个结点x,比较关键字k与x.key。如果两个关键字相等,查找就终止。如果k小于x. key,查找在x的左子树中继续,因为二叉搜索树性质蕴涵了k不可能被存储在右子树中。对称地,如果k大于x. key,查找在右子树中继续。从树根开始递归期间遇到的结点就形成了一条向下的简单路径,所以TREE SEARCH

的运行时间为O(h),其中h是这棵树的高度。

QQ截图20220516110244.jpg

图12-2 一棵二叉搜索树上的查询。为了查找这棵树中关键字为13的结点,从树根开始沿着15→6→7→13路径进行查找。这棵树中最小的关键字为2,它是从树根开始一直沿着left 指针被找到的。最大的关键字20是从树根开始一直沿着right 指针被找到的。关键字为15的结点的后继是关键字为17的结点,因为它是15的右子树中的最小关键字。关键字为13的结点没有右子树,因此它的后继是最低的祖先并且其左孩子也是一个祖先。这种情况下,关键字为15的结点就是它的后继

我们可以采用while循环来展开递归,用一种迭代方式重写这个过程。对于大多数计算机,迭代版本的效率要高得多。

QQ截图20220516110509.jpg

最大关键字元素和最小关键字元素

通过从树根开始沿着left孩子指针直到遇到一个NIL,我们总能在一棵二叉搜索树中找到一个元素,如图12-2所示。下面的过程返回了一个指向在以给定结点x为根的子树中的最小元素的指针,这里假设不为NIL:

QQ截图20220516110635.jpg

二叉搜索树性质保证了TREE-MINIMUM 是正确的。如果结点x没有左子树,那么由于x右子树中的每个关键字都至少大于或等于

x. key,则以x为根的子树中的最小关键字是x. key。如果结点x有左子树,那么由于其右子树中没有关键字小于x. key,且在左子树中的每个关键字不大于x. key,则以x为根的子树中的最小关键字一定在以x. left为根的子树中。

TREE-MAXIMUM的伪代码是对称的,如下:

QQ截图20220516110819.jpg

这两个过程在一棵高度为h的树上均能在O(h)时间内执行完,因为与TREE SEARCH一样,它们所遇到的结点均形成了一条从树根向下的简单路径。

后继和前驱

给定一棵二叉搜索树中的一个结点,有时候需要按中序遍历的次序查找它的后继。如果所有的关键字互不相同,则一个结点x的后继是大于x. key的最小关键字的结点。一棵二叉搜索树的结构允许我们通过没有任何关键字的比较来确定一个结点的后继。如果后继存在,下面的过程将返回一棵二叉搜索树中的结点x的后继;如果x是这棵树中的最大关键字,则返回NIL。

QQ截图20220516111026.jpg

把TREE-SUCCESSOR的伪代码分为两种情况。如果结点x的右子树非空,那么x的后继恰是x右子树中的最左结点,通过第2行中的TREE-MINIMUM(x. right)调用可以找到。例如,在图12-2中,关键字为15的结点的后继是关键字为17的结点。

另一方面,正如练习12. 2-6所要做的,如果结点x的右子树非空并有一个后继y,那么y就是x的有左孩子的最底层祖先,并且它也是x的一个祖先。在图12-2中,关键字为13的结点的后继是关键字为15的结点。为了找到y,只需简单地从x开始沿树而上直到遇到一个其双亲有

左孩子的结点。TREE-SUCCESSOR中的第3~7行正是处理这种情况。

在一棵高度为h的树上,TREE SUCCESSOR的运行时间为O(h),因为该过程或者遵从一条简单路径沿树向上或者遵从简单路径沿树向下。过程TREE-PREDECESSOR与TREE-SUCCESSOR是对称的,其运行时间也为O(h)。

即使关键字非全不相同,我们仍然定义任何结点x的后继和前驱为分别调用TREE-SUCCESSOR(x)和TREE-PREDECESSOR(x)所返回的结点。

总之,我们已经证明了下面的定理。

定理12.2  在一棵高度为 h的二叉搜索树上,动态集合上的操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR可以在O(h)时间内完成。


练习

12.2-1  假设一棵二叉搜索树中的结点在1到1 000之间,现在想要查找数值为363的结点。下

     QQ截图20220516111410.jpg

12. 2-2  写出TREE-MINIMUM和TREE-MAXIMUM的递归版本。

12. 2-3  写出过程TREE-PREDECESSOR的伪代码。

12. 2-4  Bunyan 教授认为他发现了一个二叉搜索树的重要性质。假设在一棵二叉搜索树中查找一个关键字k,查找结束于一个树叶。考虑三个集合:A为查找路径左边的关键字集合;B为查找路径上的关键字集合;C为查找路径右边的关键字集合。Bunyan 教授声称:任何a∈A, b∈B和c∈C, 一定满足a≤b≤c。请给出该教授这个论断的一个最小可能的反例。

12.2-5  证明:如果一棵二叉搜索树中的一个结点有两个孩子,那么它的后继没有左孩子,它的前驱没有右孩子。

12.2-6  考虑一棵二叉搜索树T,其关键字互不相同。证明:如果T中一个结点x的右子树为空,且x有一个后继y,那么y一定是x的最底层祖先,并且其左孩子也是x的祖先。(注意到,每个结点都是它自己的祖先。)

12.2-7  对于一棵有 n个结点的二叉搜索树,有另一种方法来实现中序遍历,先调用TREE-MINIMUM找到这棵树中的最小元素,然后再调用n-1次的TREE-SUCCESSOR。证明:该算法的运行时间为Θ(n)。

12.2-8  证明:在一棵高度为h的二叉搜索树中,不论从哪个结点开始,k次连续的TREE-SUCCESSOR调用所需时间为O(k+h)。

12.2-9  设T是一棵二叉搜索树,其关键字互不相同;设x是一个叶结点,y为其父结点。证明:y.key或者是T树中大于x. key的最小关键字,或者是T树中小于x. key的最大关键字。

相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~