《算法导论》习题答案6、7、8、9章.ppt

1、算法习题课,Chapter 12,13,14,Chap. 12,12.2.1 根据给定的序列，构造对应的查找树，不满足BST的性质的序列有c,e； 12.2.5若节点有两个孩子，则其后继为其右子树中的最小节点，前驱为左子树的最大节点；易知，前驱没有右孩子，后继没有左孩子（反证）。 12.2.9x是叶子节点，则y是x的前驱或者后继,Chap. 12,12.3.1Tree-insert的递归版本 Tree-insert-recursive(T,z,y) if T=NIL then T-z if yNIL then pz=y else if keyzkeyT then Tree-insert-rec

2、ursive(leftT,z,T) else Tree-insert-recursive(rightT,z,T),Chap. 12,12.3-3:最好情况 ，此时形成的BST树高与相同节点数目的完全二叉树的高度相同；最坏情况 ,若关键字的插入顺序是递增或递减有序，此时形成的BST高度为n；,Chap. 12,12.3-6: 首先解释下题目，书中的Tree-Delete算法是若待删节点有两个孩子，寻找待删节点的后继，用后继的信息代替待删节点，然后删除后继节点（因为后继节点只有右儿子，删除交较简单）；但同样的，可以查找待删节点的前驱，用前驱的信息代替待删节点，删除前驱节点。 题目要求给出一个策略，

3、可以在前驱和后继中公平的选择。 在删除前生成随机数，用其奇偶性作为选择标准；或者利用左右子树的高度。 策略不唯一，保证等概率即可。,Chap.13,13.1-1 略 13.1-2 插入后，36所在的节点成为35所在节点的右孩子； 若新插入的节点是红色，则违反性质4，红色节点的孩子不能是红色；若为黑色，则从根到新节点所在的路径黑高度比其余路径大，不满足性质5.,Chap. 13,13.1-6 RB-Tree中，若黑高度为k，那么节点个数最多为 ，对应的树高为2k，树中红黑节点相间；最少为 ，对应树高为k，树中所有节点都是黑色的。,Chap.13,13.2-2 对于树中任一节点x，若leftx=N

4、IL，那么无法对x进行右旋；若rightx=NIL，那么无法对x进行左旋； 树中边的个数就是BST上所有可能的旋转操作之和； n个节点的树中，边的个数为n-1。,Chap. 13,13.2-4 首先证明任意的二分查找树可通过至多n-1次旋转变成右行链: 从根开始，反复对根节点执行right-rotate直到根的左子树中的节点都处于根的右行链中； 沿着右行链遍历，找到原来树中根节点的右儿子，遍历过程中对每个节点执行right-rotate操作直到该节点没有左子树； 对原来根的右孩子执行同样的操作，反复进行right-rotate操作； 所有可能的right-rotate有n-1个 由对称性可知右

5、行链可通过至多n-1次旋转变成任意的二分查找树 任意两棵二分查找树之间的转换至多需要2(n-1)次旋转。,Chap. 13,13.2-5 1.右行链就不可以通过右旋转换成其它的二分查找树； 2.分析得递归式为 取k=0就可得最坏情况下为 。,Chap.13,13.3-1取成黑色会改变树的黑高度，这样调整起来更麻烦。 13.3-2略,Chap. 13,13.3-5考虑最后插入的节点z： 如果z的parent是黑色，那么RB-Insert-Fixup将仅仅保证root为黑，算法终止，并没有改变z的颜色（除非它是树中第一个节点，但n1），它将保持为红色。 若z的parent为红色，那么RB-Inse

6、rt-Fixup将对以下3种情况进行调整： case1： z仍为红色，算法上升到z的parent的parent，递归的进行调整；但z的颜色始终不变； case2-3：分析可知，这两种情况下，z的parent将保持为红色。,Chap. 13,13.4-2证明如下： 调用RB-delete之后，x成为 的孩子，若二者皆为红色，则不满足性质4。调用RB-delete-fixup之后，不执行while循环，直接将x变为黑色。树T仍然满足第四条特性。,Chap. 13,13.4-3删除过程如下： 删去结点8，其他结点颜色不变 删去结点12，则第四条性质不满足，依据case 2 ，结点19改为黑色，结点3

7、1改为红色 删去结点19，结点31成为结点38的左孩子，结点31改为黑色 删去结点31，则第四条性质不满足，依据case 2 ，结点41改为红色 删去结点38，结点41成为根结点，改为黑色 删去结点41，树空，结束,Chap.13,13.4-6证明如下： 若 不为黑色，则为红色，因而它的两个孩子必为黑色，w是 的孩子，则w应该为黑色，这与RB-delete-Fixup中第四行矛盾。故Case 1情况下， 必为黑色。,Chap. 14,14.1-1 函数运行过程大致如下： r=13, i=10, ir, 设Y为X的右孩子，进入 r=3, i=2, ir 设M为Z的右孩子，进入 r=1, i=1,

8、 i=r 返回M，即值为20的结点,Chap. 14,14.1-2运行过程：,Chap. 14,14.1-3 Non-recursive version of OS-Select while do if ir then else return y,Chap. 14,14.1-5 首先调用 找出元素x的rank r，时间复杂度为 ；调用 找出rank为r+i的元素，时间复杂度为 ；总的复杂度为 。,Chap. 14,14.3-3 Min-interval-Search (T,i) xroot T yInterval-Search (x,i) flagtrue while flag and ynil T do xlefty zInterval-Search(x,i) if znil T then yz else flagfalse return y,Chap.14,14.3-6 一种参考的数据结构可以书中的Interval trees作为基础的数据结构，动态集合中的每个值作为结点的 low endpoint，集合中下一个值作为 该结点的high endpoint，再在此基础上增加一个min-gap域，该域存放的值是以该结点