第8章搜索 般地,搜索不成功的平均数据比较次数为 AL=1S(m+32+2-1-tm+1)=2n+7m+6 (n+1 8-5在一棵表示有序集S的二叉搜索树中,任意一条从根到叶结点的路径将S分为3部分:在该路径左 边结点中的元素组成的集合S1;在该路径上的结点中的元素组成的集合S2;在该路径右边结点中的元素 组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1,b∈S2,c∈S3,是否总有a≤b≤c?为什么? 【解答】 答案是否定的。举个反例:看下图粗线所示的路径 Sl={15},S2={25,30,35,45},S3={40,50,65,70} c=40∈S3,b=45∈S2,b≤c不成立。 8-6设有一个输入数据的序列是{46,25,78,62,12,37,70,29},试画出从空树起,逐个输入各个数据而 生成的二叉搜索树。 【解答】 空树加46 加25 加78 加12 加70 8-7在二叉搜索树上删除一个有两个子女的结点时,可以采用以下三种方 (1)用左子树T上具有最大关键码的结点X顶替,再递归地删除X (2)交替地用左子树TL上具有最大关键码的结点和右子树TR上具有最小关键码的结点顶替,再递 归地删除适当的结点 3)用左子树T上具有最大关键码的结点或者用右子树TR上具有最小关键码的结点顶替,再递归 地删除适当的结点。可随机选择其中一个方案。第 8 章 搜索 82 40 一般地，搜索不成功的平均数据比较次数为 8-5 在一棵表示有序集 S 的二叉搜索树中，任意一条从根到叶结点的路径将 S 分为 3 部分：在该路径左 边结点中的元素组成的集合 S1；在该路径上的结点中的元素组成的集合 S2；在该路径右边结点中的元素 组成的集合 S3。S = S1  S2  S3。若对于任意的 a  S1, b  S2, c  S3， 是否总有 a  b  c？为什么？ 【解答】 答案是否定的。举个反例：看下图粗线所示的路径 S1 = { 15 }, S2 = { 25, 30, 35, 45 }, S3 = { 40, 50, 65, 70 } c = 40  S3，b = 45  S2，b  c 不成立。 8-6 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 37, 70, 29 }, 试画出从空树起，逐个输入各个数据而 生成的二叉搜索树。 【解答】 8-7 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法： (1) 用左子树 TL 上具有最大关键码的结点 X 顶替，再递归地删除 X。 (2) 交替地用左子树 TL 上具有最大关键码的结点和右子树 TR 上具有最小关键码的结点顶替，再递 归地删除适当的结点。 (3) 用左子树 TL 上具有最大关键码的结点或者用右子树 TR 上具有最小关键码的结点顶替，再递归 地删除适当的结点。可随机选择其中一个方案。 45 30 15 25 70 65 35 50 = + + +  =      + − − + + + = n i 0 2 2 unsucc 2 n 1 2n 7n 6 i i i*n 1 2 n*(n 3) (n 1) 1 ASL 46 46 25 46 25 78 46 25 78 62 46 25 78 12 62 46 25 78 12 37 62 46 25 78 12 37 62 70 46 25 78 12 37 62 29 70 空树 加46 加25 加 78 加 62 加 12 加 37 加 70 加 29