911按照竞争树的办法求最小值需n1次比较然后在lgn个

1、 9.1-1 按照竞争树的办法求最小值需n-1次比较， 然后在lgn个与最小值比较过的元素中求出最小值 即为原来n个元素的次小值，需lgn-1次比较，所 以共需n+lgn-2次比较 9.1-2 题目是要证明3n/2-2是最少的比较次数， 而不是要构造出这样的算法。我们把某个元素与 其它元素间的大小关系称作一条信息，那么最大 元素包含n-1条信息(这个元素比其它n-1个元素都 大)，同样，最小元素也包含n-1条信息，同时求 出最大和最小元素就需要获得2n-2条信息。未比 较过的元素记为N，比较后较小的元素记为S，较 大的元素记为L，那么每次比较获得的信息数如下 表： 在最坏情况下，只能在两个未比

2、较过的元 素间比较才能得到两条信息，其余的比较 至多得到一条信息，而未比较过的元素至 多有n个，这样为了得到2n-2条消息至少需 要n/2+(2n-2-n)=3n/2-2次比较 9.2-4 最坏时Randomized-Partition每次都返回余下 元素中最大的一个，划分序列是9,8,7,6,5,4,3,2,1,0 9.3-1 每组7个元素时大于x的元素 为 ,此时递归式为 用代换法解得复杂度为O(n) 每组3个元素时同理可得递归式为 用代换法解得复杂度为(nlogn) 12 4(2)8 277 n n 9.3-2 SELECT中大于x的元素至少为 当n=140时满足3n/10-6= ，同理

3、可证小于的情 况 9.3-4 通过比较得到的第i小的元素，在比较过程中比 这个元素小的元素构成的集合即为i 1个小数集合， 而比较过程中比这个元素大的元素则构成了n i 个大 元素集合。不需要增加比较次数，只需要每次保留比 较信息即可 9.3-7 (1) Find the median i of S O(n) (2) Construct a new set S, such that for every element x in S, there is a corresponding element y in S, where y = |x - i| n次 (3) Find the kth or

4、der statistics d inS kn次 (4) For each element x in S,if |x - i| = d,add x to set T n次 (5) return T 13 3(2 )6 251 0 n n 12.3-1 Tree-Insert(T,z) T-Insert(T,z) y=root(T); x=root(T); if(y=NIL) if(keyzkeyx) keyy=keyz; if(leftx=NIL) lefty=NIL; leftx=keyz; righty=NIL; else T-Insert(leftx,z); else else T-In

5、sert(y,z); if(rightx=NIL) rightx=keyz; else T-insert(rightx,z); 12.3-3 中序遍历O(n)，最好情况下是完全二叉树， 运行时间为O(nlogn)，最坏情况下是一个链，运 行时间O(n2) 12.3-6 自己定义一个priority，可以是左右子树的 高、左右子树的大小或者等概率随机选择一个 13.1-1 略 13.1-2 都不是，红色违反性质4，黑色违反性质5 13.1-6 最多时是红黑相间的满二叉树，而且最底 层内结点为红色，此时内结点总数为(22k)-1，最 少时是全黑的满二叉树，此时内结点总数为 (2k)-1 13.2.

6、2 BST(Binary Search Tree)上某个结点的旋 转次数，是这个结点能够左旋和右旋的次数之和， 即非空的右孩子结点和非空的左孩子结点数之和。 对BST上所有结点的旋转次数求和，得到BST的 边数为n 1，这就是n node的BST可能的旋转 数目。 13.2.4 首先证明任意的二分查找树可通过至多n-1 次旋转变成右行链。 再由对称性可知右行链可通过至多n-1次旋转变成 任意的二分查找树，这样任意两棵二分查找树之 间的转换至多需要2(n-1)次旋转。 13.2.5 (1)右行链就不可以通过右旋转换成 其它的二分查找树。 (2)分析得递归式为 取k=0就可得最坏情况下为 。 13

7、.3.1 取成黑色会改变树的黑高度，这样 调整起来更麻烦。 13.3.2 略 13.3.5 用归纳法证即可。 ) 10 () 1()()()(nkknTkTnOnT )( 2 n 13.4-3删除过程如下： 删去结点8，其他结点颜色不变 删去结点12，则第四条性质不满足，依据case 2 ，结点19改为黑色， 结点31改为红色 删去结点19，结点31成为结点38的左孩子，结点31改为黑色 删去结点31，则第四条性质不满足，依据case 2 ，结点41改为红色 删去结点38，结点41成为根结点，改为黑色 删去结点41，树空，结束 14.1-1函数运行过程大致如下： r=13, i=10, ir

8、设Y为X的右孩子， 进入r=3, i=2, ir 设M为Z的右孩子， 进入r=1, i=1, i=r 返回M，即值为20的结点 14.3-6实现要求的数据结构有多种。一种参考 的数据结构可以书中14.3节介绍的Interval trees 作为基础的数据结构，动态集合中的每个值作为 结点的 low endpoint，集合中下一个值作为 该结 点的high endpoint，再在此基础上增加一个min- gap域，该域存放的值是以该结点为根的树中， 所有结点的high endpoint与low endpoint值差异最 小的值。 Insert，Delete，Search算法和Interval t

9、rees 基本相同，时间复杂度为 。 Min-Gap算法的值可直接由根结点的min-gap 域的值直接得到，时间复杂度为 nlg 1 19.1-1 if x is root degree(sibingx)degree(x) if x is not root degree(sibingx)=degree(x)-1 19.1-3证明：1）由树的构成可知：x的第i孩子的二进制表 示为x二进制表示的最右0后第i位置反。 由这个性质我们可以得到第i层节点的二进制表示中有ki 个1。 2）包含j个1的节点个数为第i层的个数。 3）数学归纳法证明 19.2-2 过程略 ( union操作 ) 19.2-3 （1）decrease-key （2）extract-min 过程略 19.2