高级数据结构.ppt

JYP 高级数据结构 代价分摊（1.5.4） 两个字符串的最长公共子序列（2.4.3） 机场模拟（2.9） 二叉树计数(4.9) 最小最大堆 (5.2) 5.2.2 插入操作 5.2.3 删除最小元素操作 双堆 (5.3) 5.3.2 插入操作 5.3.3 删除最小元素 左偏树 (5.4) 二项式堆 (5.5) 5.5.1 二项式堆定义 5.5.2 插入操作 5.5.3 合并操作 5.5.4 删除最小元素 5.5.5 分析 斐波纳契堆 (5.6) 5.6.2 删除操作 5.6.3 关键字减少操作 5.6.4 瀑布修剪 5.6.5 分析 双连分量 (6.4.2) 求解最小生成树的普瑞姆算法（6.5.2） 斐波纳契堆在最短路径算法中的应用 基于链表和映射表排序结果的顺序化（7.8） 7.9 外排序 7.9.2 k路归并 7.9.3 生成初始归并段 7.9.4 归并段的最佳归并和哈夫曼树 二叉查找树的结合与分裂 （8.2.3） 二叉查找树的性能分析 （8.2.4） 最佳二叉查找树 （8.2.5） 8.6.6 B+树 动态散列 （8.9） 8.9.1 带目录动态散列 8.9.2 无目录动态散列 例8.2 设n = 3，(a1, a2, a3) = (data, pipe, work)，(p1, p2, p3) = (0.5, 0.05, 0.1)，(q0, q1, q2, q3) = (0.15, 0.05, 0.1, 0.05)。 初始时，wii = qi，cii = 0，0≤i≤3。利用(8.7)和(8.8)式，并注意到wij = wi,j-1 + pj + qj，可得 w01 = w00 + p1 + q1 = 0.15 + 0.5 + 0.05 = 0.7 c01 = w01 + min{c00 + c11} = 0.7 r01 = 1 w12 = w11 + p2 + q2 = 0.05 + 0.05 + 0.1 = 0.2 c12 = w12 + min{c11 + c22} = 0.2 r12 = 2 w23 = w22 + p3 + q3 = 0.1 + 0.1 + 0.05 = 0.25 c23 = w23 + min{c22 + c33} = 0.25 r23 = 3 在wi,i+1和ci,i+1的基础上（0≤i 3），再次利用(8.7)和(8.8)式，可计算出wi,i+2、ci,i+2和ri,i+2，0≤i 2。重复此过程，最终可得到w03、c03和r03。 下一页的图8.10给出了此计算结果。 由此，c03 = 1.55是最小代价，T03的根结点含标识符a1，其左子树是T00，右子树是T13。 T13的根结点含标识符a3，其左子树是T12，右子树是T33。 T12的根结点含标识符a2，其左子树是T11，右子树是T22。由此可以构造T03，如右图所示。 由于本例子中假设的pi和qi与上一个例子的相同，所以该树在结构上与上一个例子的最佳二叉查找树相同。 由上可得计算cij和rij（0≤i n，i j≤n）以及根据rij构造T0n的方法：按（j – i）= 1, 2, …, n的顺序计算cij。 当j – i = m时，需要计算n – m + 1个cij。每计算一个cij需要从m个量中选择最小的（(8.8)式），计算时间是O(m)。计算所有cij的总时间为O(nm – m2)。 计算全部cij和rij的总时间是 = O(n3) Knuth的研究成果表明，(8.8)式中的最佳u的选择可限定在ri,j-1≤u≤ri+1,j的范围。 因此，当j – i = m时，1≤r0,m-1≤r1,m≤r2,m+1 ≤ … ≤rn-m+1,n≤n，总计算时间改进为 ≤2n – m + 1 = O(n) 当j – i = m，且m = 1时的总计算时间为n – m + 1。计算全部cij和rij的总时间改进为 n – m + 1 + = O(n2) 假设二维数组w、c和r是类BST的私有数据成员。算法obst实现了上述方法，并根据计算结果调用函数build构造最佳二叉查找树。 同理，新加入B部分应作为当前B中关键字最大元素所在结点（用R指向）的右子树。 为了避免判断树为空的情况，在开始时为B和C分别引入头结点Y和Z。下面是实现分裂操作的算法： template