《算法导论2版》课后答案_加强版5-(精品课件).pptVIP

Chap. 12 12.2.1 根据给定的序列，构造对应的查找树，不满足BST的性质的序列有c,e； 12.2.5 若节点有两个孩子，则其后继为其右子树中的最小节点，前驱为左子树的最大节点；易知，前驱没有右孩子，后继没有左孩子（反证）。 12.2.9 x是叶子节点，则y是x的前驱或者后继 Chap. 12 12.3.1 Tree-insert的递归版本 Tree-insert-recursive(T,z,y) if T=NIL then T-z if y≠NIL then p[z]=y else if key[z]key[T] then Tree-insert-recursive(left[T],z,T) else Tree-insert-recursive(right[T],z,T) Chap. 12 12.3-3:最好情况 ，此时形成的BST树高与相同节点数目的完全二叉树的高度相同；最坏情况 ,若关键字的插入顺序是递增或递减有序，此时形成的BST高度为n； Chap. 12 12.3-6: 首先解释下题目，书中的Tree-Delete算法是若待删节点有两个孩子，寻找待删节点的后继，用后继的信息代替待删节点，然后删除后继节点（因为后继节点只有右儿子，删除交较简单）；但同样的，可以查找待删节点的前驱，用前驱的信息代替待删节点，删除前驱节点。 题目要求给出一个策略，可以在前驱和后继中公平的选择。 在删除前生成随机数，用其奇偶性作为选择标准；或者利用左右子树的高度。 策略不唯一，保证等概率即可。 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，若left[x]=NIL，那么无法对x进行右旋；若right[x]=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次旋转变成任意的二分查找树 任意两棵二分查找树之间的转换至多需要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的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改