第7章集合与搜索 如果指针p处于第i个结点(=1,2…,n),它左边有i个不成功的位置,右边有n+1个不成功的位置。 2(-6)+-1+D/(m+1)=(”*(m+3)+p i-i*n+1/(n+1) 般地,搜索不成功的平均数据比较次数为 n*(n+3) ASLunsace (n+1)2 +12-i-1*n+ 2n2+7n+6 n+1 7-12在一棵表示有序集S的二叉搜索树中,任意一条从根到叶结点的路径将S分为3部分:在该路径左 边结点中的元素组成的集合S1:在该路径上的结点中的元素组成的集合S;在该路径右边结点中的元素 组成的集合S3。S=S1∪S2∪S。若对于任意的a∈S,b∈S,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不成立。 7-13请给出下列操作序列运算的结果: Union(1,2), Union(3,4), Union(3,5), Union(1,T),Umon(3,6), Union(8, 9), Union( 1, 8), Union (3, 10), Union(3, 11), Union( 3, 12), Union(3, 13), Union(14, 15), Union( 16, 17), Unin(14,16), Union(1,3), Union(1,14),要求 (1)以任意方式执行 Union (2)根据树的高度执行Umon; (3)根据树中结点个数执行U 【解答】 (1)对于 union(i,j),以i作为j的双亲 (2)按i和j为根的树的高度实现 union(i,j),高度大者为高度小者的双亲第 7 章 集合与搜索 61 40 如果指针 p 处于第 i 个结点(i = 1, 2, …, n)，它左边有 i 个不成功的位置，右边有 n-i+1 个不成功的位置。 一般地，搜索不成功的平均数据比较次数为 7-12 在一棵表示有序集 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 不成立。 7-13 请给出下列操作序列运算的结果：Union(1, 2), Union(3, 4), Union(3, 5), Union(1, 7), Union(3, 6), Union(8, 9), Union(1, 8), Union(3, 10), Union(3, 11), Union(3, 12), Union(3, 13), Union(14, 15), Union(16, 17), Union(14, 16), Union(1, 3), Union(1, 14)，要求 (1) 以任意方式执行 Union； (2) 根据树的高度执行 Union； (3) 根据树中结点个数执行 Union。 【解答】 (1) 对于 union(i, j)，以 i 作为 j 的双亲 (2) 按 i 和 j 为根的树的高度实现 union(i, j)，高度大者为高度小者的双亲； 1 2 7 8 9 4 5 6 10 11 12 13 3 14 15 16 0 3 15 16 1 2 7 8 9 4 5 6 10 14 45 30 15 25 70 65 35 50 * 1 ( 1) 2 * ( 3) ( ) ( 1) ( 1) 2 1 0  +      + − − + +  + =      − +  − + = − = i i i n n n n i k k i n n k i i k = + + +  =      + − − + + + = n i unsucc n n n i i i n n n n ASL 0 2 2 2 1 2 7 6 * 1 2 *( 3) ( 1) 1