《按照竞争树的办法求最小值需n-1次比较》由会员分享，可在线阅读，更多相关《按照竞争树的办法求最小值需n-1次比较（16页珍藏版）》请在金锄头文库上搜索。
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,09.3-1 每组7个元素时大于x的元素为 ,此时递归式为 用代换法解得复杂度为O(n) 每组3个元素时同理可得递归式为 用代换法解得复杂度为(nlogn)9.3-2 SELECT中大于x的元素至少为 当n=140时满足3n/10-6= ，同理可证小于的情况9.3-4 通过比较得到的第i小的元素，在比较过程中比这个元素小的
3、元素构成的集合即为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 order statistics d inS kn次 (4) For each element x
4、 in S,if |x - i| = d,add x to set T n次 (5) return T 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-Insert(y,z); if(rightx=NIL) rightx=keyz; else T-insert(rightx,z); 12.3-3 中序遍
5、历O(n)，最好情况下是完全二叉树，运行时间为O(nlogn)，最坏情况下是一个链，运行时间O(n2)12.3-6 自己定义一个priority，可以是左右子树的高、左右子树的大小或者等概率随机选择一个13.1-1 略13.1-2 都不是，红色违反性质4，黑色违反性质513.1-6 最多时是红黑相间的满二叉树，而且最底层内结点为红色，此时内结点总数为(22k)-1，最少时是全黑的满二叉树，此时内结点总数为(2k)-1 BST(Binary Search Tree)上某个结点的旋转次数，是这个结点能够左旋和右旋的次数之和，即非空的右孩子结点和非空的左孩子结点数之和。对BST上所有结点的旋转次数求
6、和，得到BST的边数为n 1，这就是n node的BST可能的旋转数目。13.2.4 首先证明任意的二分查找树可通过至多n-1次旋转变成右行链。再由对称性可知右行链可通过至多n-1次旋转变成任意的二分查找树，这样任意两棵二分查找树之间的转换至多需要2(n-1)次旋转。 13.2.5 (1)右行链就不可以通过右旋转换成其它的二分查找树。(2)分析得递归式为 取k=0就可得最坏情况下为 。13.3.1 取成黑色会改变树的黑高度，这样调整起来更麻烦。13.3.2 略13.3.5 用归纳法证即可。删除过程如下：删去结点8，其他结点颜色不变删去结点12，则第四条性质不满足，依据case 2 ，结点19改
7、为黑色，结点31改为红色删去结点19，结点31成为结点38的左孩子，结点31改为黑色删去结点31，则第四条性质不满足，依据case 2 ，结点41改为红色删去结点38，结点41成为根结点，改为黑色删去结点41，树空，结束函数运行过程大致如下：r=13, i=10, ir 设Y为X的右孩子，进入r=3, i=2, ir 设M为Z的右孩子，进入r=1, i=1, i=r 返回M，即值为20的结点实现要求的数据结构有多种。一种参考的数据结构可以书中节介绍的Interval trees作为基础的数据结构，动态集合中的每个值作为结点的 low endpoint，集合中下一个值作为 该结点的high en
8、dpoint，再在此基础上增加一个min-gap域，该域存放的值是以该结点为根的树中，所有结点的high endpoint与low endpoint值差异最小的值。 Insert，Delete，Search算法和Interval trees基本相同，时间复杂度为 。 Min-Gap算法的值可直接由根结点的min-gap域的值直接得到，时间复杂度为19.1-1 if x is root degree(sibingx)degree(x)if x is not root degree(sibingx)=degree(x)-1证明：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 过程略 算法思想：找到堆中最小值min，用min-1代替-. 遍历堆中树的根节点课堂小测关键字41,12,19,8插入一棵初始为空的红黑树,画出插入过程,从建好的树中连续删除关键字12,19请给出一个时间 O(n2) 的算法,使之能找出一个N个数的序列中最长的单调递增子序列.
