《《算法导论》习题答案6、7、8、9章.ppt》由会员分享，可在线阅读，更多相关《《算法导论》习题答案6、7、8、9章.ppt（21页珍藏版）》请在三一办公上搜索。
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=NILthen T-z if yNIL then pz=y else if keyzkeyT then Tree-insert-recursive(
2、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=NIL，那么无法对x进行右旋；若rightx=
4、NIL，那么无法对x进行左旋；树中边的个数就是BST上所有可能的旋转操作之和；n个节点的树中，边的个数为n-1。,Chap.13,13.2-4首先证明任意的二分查找树可通过至多n-1次旋转变成右行链:从根开始，反复对根节点执行right-rotate直到根的左子树中的节点都处于根的右行链中；沿着右行链遍历，找到原来树中根节点的右儿子，遍历过程中对每个节点执行right-rotate操作直到该节点没有左子树；对原来根的右孩子执行同样的操作，反复进行right-rotate操作；所有可能的right-rotate有n-1个由对称性可知右行链可通过至多n-1次旋转变成任意的二分查找树任意两棵二分查找
5、树之间的转换至多需要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-Insert-Fixup将对以下3种情况进行调整：case1：z仍为红色，算法上升到z
6、的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改为黑色，结点31改为红色删去结点19，结点31成为结点38的左孩子，结点31改为黑色删去结点31，则第四条性质
7、不满足，依据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,i=r 返回M，即值为20的结点,Chap.14,14.1-2运行过程：,Chap.14,14.1-3 Non-recursive
8、 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域，该域存放的值是以该结点为根的树中，所有结点的high endpoint与low endpoint值差异最大的值。Insert，Delete，Search算法和Interval trees基本相同，时间复杂度为;Min-Gap算法的值可直接由根结点的min-gap域的值直接得到，时间复杂度为,
