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

算法习题课 Chapter12 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 ifT NILthenT zify NILthenp z yelseifkey z key T thenTree insert recursive left T z T elseTree 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 6RB 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 51 右行链就不可以通过右旋转换成其它的二分查找树 2 分析得递归式为取k 0就可得最坏情况下为 Chap 13 13 3 1取成黑色会改变树的黑高度 这样调整起来更麻烦 13 3 2略 Chap 13 13 3 5考虑最后插入的节点z 如果z的parent是黑色 那么RB Insert Fixup将仅仅保证root为黑 算法终止 并没有改变z的颜色 除非它是树中第一个节点 但n 1 它将保持为红色 若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 则第四条性质不满足 依据case2 结点19改为黑色 结点31改为红色删去结点19 结点31成为结点38的左孩子 结点31改为黑色删去结点31 则第四条性质不满足 依据case2 结点41改为红色删去结点38 结点41成为根结点 改为黑色删去结点41 树空 结束 Chap 13 13 4 6 证明如下 若不为黑色 则为红色 因而它的两个孩子必为黑色 w是的孩子 则w应该为黑色 这与RB delete Fixup中第四行矛盾 故Case1情况下 必为黑色 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 3Non recursiveversionofOS Selectwhiledoifi rthenelsereturny Chap 14 14 1 5首先调用找出元素x的rankr 时间复杂度为 调用找出rank为r i的元素 时间复杂度为 总的复杂度为 Chap 14 14 3 3Min interval Search T i x root T y Interval Search x i flag truewhileflagandy nil T dox left y z Interval Search x i ifz nil T theny zelseflag falsereturny Chap 14 14 3 6一种参考的数据结构可以书中的Intervaltrees作为基础的数据结构 动态集合中的每个值作为结点的lowendpoint 集合中下一个值作为该结点的highendpoint 再在此基础上增加一个min gap域 该域存放的值是以该结点为