《算法导论2版》课后答案_加强版5

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 keyz1），它将保持为红色。若z的parent为红色，那么RB-Insert-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改为黑色，结点31改为红色删去结点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, 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域，该域存放的值是以该结点为根的树中，所有结点的high endpoint与low endpoint值差异最大的值。 Insert，Delete，S