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，较大的元素记为

Presentation on theme: "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，较大的元素记为"— Presentation transcript:

1 9.1-1 按照竞争树的办法求最小值需n-1次比较，然后在lgn个与最小值比较过的元素中求出最小值即为原来n个元素的次小值，需lgn-1次比较，所以共需n+lgn-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次比较

3 9.2-4 最坏时Randomized-Partition每次都返回余下元素中最大的一个，划分序列是{9,8,7,6,5,4,3,2,1,0}
9.3-1 每组7个元素时大于x的元素为 ,此时递归式为 用代换法解得复杂度为O(n) 每组3个元素时同理可得递归式为 用代换法解得复杂度为Ω(nlogn)

4 9.3-2 SELECT中大于x的元素至少为 当n>=140时满足3n/10-6>= ，同理可证小于的情况
通过比较得到的第i小的元素，在比较过程中比这个元素小的元素构成的集合即为i – 1个小数集合，而比较过程中比这个元素大的元素则构成了n – i 个大元素集合。不需要增加比较次数，只需要每次保留比较信息即可 (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 in S,if |x - i| <= d,add x to set T n次 (5) return T

5 12.3-1 Tree-Insert(T,z) { T-Insert(T,z){ y=root(T); x=root(T); if(y==NIL){ if(key[z]<key[x]) key[y]=key[z]; if(left[x]==NIL) left[y]=NIL; left[x]=key[z]; right[y]=NIL; } else T-Insert(left[x],z); else else T-Insert(y,z); if(right[x]==NIL) } right[x]=key[z]; else T-insert(right[x],z);

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

7 BST(Binary Search Tree)上某个结点的旋转次数，是这个结点能够左旋和右旋的次数之和，即非空的右孩子结点和非空的左孩子结点数之和。对BST上所有结点的旋转次数求和，得到BST的边数为n – 1，这就是n – node的BST可能的旋转数目。 首先证明任意的二分查找树可通过至多n-1次旋转变成右行链。 再由对称性可知右行链可通过至多n-1次旋转变成任意的二分查找树，这样任意两棵二分查找树之间的转换至多需要2(n-1)次旋转。

8 13.2.5 (1)右行链就不可以通过右旋转换成其它的二分查找树。
(2)分析得递归式为 取k=0就可得最坏情况下为 。 取成黑色会改变树的黑高度，这样调整起来更麻烦。 略 用归纳法证即可。

9 13.4-3．删除过程如下： 删去结点8，其他结点颜色不变 删去结点12，则第四条性质不满足，依据case 2 ，结点19改为黑色，结点31改为红色 删去结点19，结点31成为结点38的左孩子，结点31改为黑色 删去结点31，则第四条性质不满足，依据case 2 ，结点41改为红色 删去结点38，结点41成为根结点，改为黑色 删去结点41，树空，结束

10 14.1-1．函数运行过程大致如下： r=13, i=10, i<r 设X为T的左孩子， 进入r=8, i=10, i>r 设Y为X的右孩子， 进入r=3, i=2, i<r 设Z为Y的左孩子， 进入r=1, i=2, i>r 设M为Z的右孩子， 进入r=1, i=1, i=r 返回M，即值为20的结点

11

12

13 14. 3-6．实现要求的数据结构有多种。一种参考的数据结构可以书中14
14.3-6．实现要求的数据结构有多种。一种参考的数据结构可以书中14.3节介绍的Interval trees作为基础的数据结构，动态集合中的每个值作为结点的 low endpoint，集合中下一个值作为 该结点的high endpoint，再在此基础上增加一个min-gap域，该域存放的值是以该结点为根的树中，所有结点的high endpoint与low endpoint值差异最小的值。 Insert，Delete，Search算法和Interval trees基本相同，时间复杂度为 。 Min-Gap算法的值可直接由根结点的min-gap域的值直接得到，时间复杂度为

14 19.1-1 if x is root degree(sibing[x])>degree(x)
if x is not root degree(sibing[x])=degree(x)-1 19.1-3证明：1）由树的构成可知：x的第i孩子的二进制表示为x二进制表示的最右0后第i位置反。 由这个性质我们可以得到第i层节点的二进制表示中有k－i个1。 2）包含j个1的节点个数为第i层的个数。 3）数学归纳法证明

15 过程略 ( union操作 ) （1）decrease-key （2）extract-min 过程略 算法思想：找到堆中最小值min，用min-1代替-∞. [遍历堆中树的根节点]

16 课堂小测 关键字41,12,19,8插入一棵初始为空的红黑树,画出插入过程,从建好的树中连续删除关键字12,19
请给出一个时间 O(n^2) 的算法,使之能找出一个N个数的序列中最长的单调递增子序列.