北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第十二章 高级树结构

代价分析 目标长n=S,模式长m=/P 空间代价 ST 20n SA 4n 建数据结构时间代价 STO(n SA O(nlogn ■查找子串时间代价 ST O(m) sA O(m log n) 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 26

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 代价分析 „ 目标长n=|S|，模式长m=|P|) „ 空间代价 „ ST 20n „ SA 4n „ 建数据结构时间代价 „ ST O(n) „ SA O(nlogn) „ 查找子串时间代价 „ ST O(m) • SA O(m log n)

后缀树小结 后缀树和后缀数组提供了很好的 全索引结构 适合于各种字符串算法 大量后缀树的变种 尽力减少其空间消耗 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 27

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 后缀树小结 „ 后缀树和后缀数组提供了很好的 全索引结构 „ 适合于各种字符串算法 „ 大量后缀树的变种 „ 尽力减少其空间消耗

122二叉树结构的改进 最佳二叉排序树 平衡的二叉搜索树 伸展树 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 28

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 12.2 二叉树结构的改进 „ 最佳二叉排序树 „ 平衡的二叉搜索树 „ 伸展树

asL(n) ∑p(1+1)+∑q 0 B 5 5OD 3○H 32 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 29

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 1 B 5 4 3 F H 2 1 5 4 3 D 1 1 0 1 ( ) (1 1) n n ii i i i ASL n p q l W = = ⎡ ⎤ = ++ ′ ⎢ ⎥ ⎣ ⎦ ∑ ∑

最佳二叉搜索树的动态规划 最佳子结构、重复子结构 任何子树都是最佳二叉搜索树 动态规划过程 第一步:构造包含1个结点的最佳二叉搜索树 找t(O,1),t(1,2) t(n-1, n 第二步构造包含2个结点的最佳二叉搜索树 找t(0,2),t(1,3), (n-2,n) 再构造包含3,4,个结点的最佳二叉搜索树 最后构造t(0,n) 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 30

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 最佳二叉搜索树的动态规划 „ 最佳子结构、重复子结构 „ 任何子树都是最佳二叉搜索树 „ 动态规划过程 „ 第一步：构造包含1个结点的最佳二叉搜索树 „ 找t(0，1)，t(1，2)，…，t(n-1，n) „ 第二步构造包含2个结点的最佳二叉搜索树 „ 找t(0，2)，t(1，3)，…，t(n-2，n) „ 再构造包含3，4，…个结点的最佳二叉搜索树 „ 最后构造t(0，n)