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

数据结构与算法 主要内容 第十二章高级树结构 12.1Trie和 Patricia结构 122改进的BsT 任课教员:张铭 最佳二叉搜索树 http://db.pku.edu.cn/mzhang/ds nzhang@db.pku.edu.cn 伸展树 北京大学信息科学与技术学院 12.3空间树结构 网络与信息系统研究所 ■12.4决策树和博弈树 版权所有,转载或翻印必究 北大恤血_邮c前有,轨成邮邮究 12.1Trie结构和 Patricia树 Trie结构 ■引子:BST(二叉搜索树)不是平衡的树 关键码对象空间分解 树结构与输入数据的顺序有很大的关系 “trie”这个词来源于“ retrieva” 主要应用 信息检索( information retrieva) 自然语言大规模的英文词典 叉Trie树 输入顺序:7、5、4、6、8 用每个字母的二进制编码来代表 编码只有0和1 输入顺序:4、5、6、7、8 真太恤鑫张陪。权所有,成即究 北大血信张帖 有:轨收些究 二叉Trie结构 英文字符树2Tie 元素为2、5、9、17、41、45、63 an”子树代表具 0(16)O1c16xO、1c48) 8)18)O l(44) 一棵子树代衰具有相同前缀的关键码的集合 张帖质有,轨成邮

1 数据结构与算法 第十二章 高级树结构 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 12.1 Trie和Patricia 结构 „ 12.2 改进的BST „ 最佳二叉搜索树 „ AVL树 „ 伸展树 „ 12.3 空间树结构 „ 12.4 决策树和博弈树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 12.1Trie结构和Patricia树 „ 引子：BST（二叉搜索树）不是平衡的树 „ 树结构与输入数据的顺序有很大的关系 4 5 6 7 8 7 5 8 4 6 输入顺序: 4、5、6、7、8 输入顺序: 7、5、4、6、8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 Trie结构 „ 关键码对象空间分解 „ “trie”这个词来源于“retrieval” „ 主要应用 „ 信息检索（information retrieval） „ 自然语言大规模的英文词典 „ 二叉Trie树 „ 用每个字母的二进制编码来代表 „ 编码只有0和1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 二叉Trie结构 元素为2、5、9、17、41、45、63 0(<32) 1(>32) 0(<16) 1(>16) 0(<8) 0(<4) 1(>48) 1(>8) 1(>4) 2 5 9 17 41 1(>40) 63 45 0(<44) 1(>44) 0(<48) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 英文字符树——26叉Trie „ 一棵子树代表具有相同前缀的关键码的集合 存单词 and、ant、bad、bee a n d t b a d e e and ant bad bee “an”子树代表具有 相同前缀an-的关 键码集合{and， ant}

字符树的改进(续) Trie字符树的特点 存储单词 an, and ant bad bee Trie结构也不是平衡的 ■t子树下的分支比z子树下的多 26个分支因子庞大的26叉树 bad bee 北大驰恤鑫 孔帖●叙肌有 申些究 北大恤血_邮c前有,轨成邮邮究 PATRICIA结构 PATRICIA结构图 a"Practical Algorithm To Retrieve Information Coded In Alphanumeric D Morrision发明的Irie结构变体 IXxxx Ixxxx iXxxx 根据关键码二进制位的编码来划分 LXxx lxxx 二叉Trie树 1010xx 1011xx MIOIxx 17:01000141;10100145:10110163;ill 真太恤鑫张陪。权所有,成即究 学单 压缩 PATRICIA结构 PATRICIA的特点 ■改进后的压缩 PATRICIA树是满二叉树 Lxxx lox lxXx 每个内部结点都代表一个位的比较 必然产生两个子结点 CXXx Dulux 次检索不超过关键码的位个数 编码:2:00105:0001019:001001 17:0100014l:101001 101101 63: llllll

2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 字符树的改进（续） 存储单词an、and、ant、bad、bee a n d t b a e and ant bad bee an * 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 Trie字符树的特点 „ Trie结构也不是平衡的 „ t子树下的分支比z子树下的多 „ 26个分支因子——庞大的26叉树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 PATRICIA 结构 „ “Practical Algorithm To Retrieve Information Coded In Alphanumeric” „ D.Morrision发明的Trie结构变体 „ 根据关键码二进制位的编码来划分 „ 二叉Trie树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 PATRICIA 结构图 101xxx 10xxxx 0000xx 001xxx 0001xx 编码： 2：000010 5：000101 9：001001 17：010001 41：101001 45：101101 63：111111 0 1 1 2 2 3 0xxxxx 1xxxxx 00xxxx 01xxxx 11xxxx 000xxx 2 5 9 17 41 63 3 1010xx 1011xx 45 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 压缩PATRICIA 结构 17 01xxxx 10xxxx 001xxx 0000xx 0001xx 编码：2：000010 5：000101 9：001001 17：010001 41：101001 45：101101 63：111111 0 1 1 2 3 3 0xxxxx 1xxxxx 00xxxx 11xxxx 2 5 9 41 63 45 1011xx 1010xx 000xxx 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 PATRICIA的特点 „ 改进后的压缩PATRICIA树是满二叉树 „ 每个内部结点都代表一个位的比较 „ 必然产生两个子结点 „ 一次检索不超过关键码的位个数

后缀树( Suffix tree MALAYALAM$的后缀 后辍树是表示一个字符串S所有后缀申的树 MALAYALAM 结点表示开始的字符(或压缩字符串) ALAYALAM 边标注为子串—该字符申在原串中的起止位置 S LAYALA M 所有根到树叶结点的路径,可以表示率S的所有后氧 AYALAM YALAM 压Tre,得到字符串的后树 M 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 对后缀串排序 后缀树 s· MALAYALAMS ALA M ALAM 12345678910 ALAYALAM ALAYALAM AYALAM AYALAM LAYALAM MALAYALAM MALAYALAM YALAM YALAM 北京大学值歌张写所有即究 边信息 s· MALAYALAMS 建树算法 2345678910 ■对于长度为n的语料建立后缀树,直 接的方法时间复杂度为o(n*n) 1973年 Weiner提出线性时间算法 1976年 McCreigh提出更节约内存 的算法 1995年 Ukkonen提出线性时间建 树算法

3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 后缀树(Suffix Tree) „ 后缀树是表示一个字符串 S 所有后缀串的树 „ 结点表示开始的字符(或压缩字符串) „ 边标注为子串——该字符串在原串中的起止位置 „ 边表示不同字符分支 „ 所有根到树叶结点的路径，可以表示串 S 的所有后缀串 „ 通俗地说： „ 一个字符串的所有后缀 „ 这些后缀组成Trie „ 压缩Trie，得到字符串的后缀树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 MALAYALAM$ 的后缀 „ M A L A Y A L A M „ A L A Y A L A M „ L A Y A L A M „ A Y A L A M „ Y A L A M „ A L A M „ L A M „ A M „ M „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 对后缀串排序 „ A L A M „ A L A Y A L A M „ A M „ A Y A L A M „ L A M „ L A Y A L A M „ M A L A Y A L A M „ M „ Y A L A M „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 S = M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10 YA $ LAM$ M $ ALAYALAM$ $M YALAM$ $M YALAM$ $M YALAM$ A AL LA 6 2 8 47 3 1 9 5 10 后缀树 „ A L A M „ A L A Y A L A M „ A M „ A Y A L A M „ L A M „ L A Y A L A M „ M A L A Y A L A M „ M „ Y A L A M „ $ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 (10, (5 10) , 10) (1, 1) (10, 10 ( ) 2, 10) (3, 4) (5, 10) (9, 10) (2, 2) (5, 10) (9, 10) (3, 4) (9, 10) (5, 10) 6 2 8 4 7 31 9 5 10 边信息 S = M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 建树算法 „ 对于长度为n的语料建立后缀树，直 接的方法时间复杂度为O（n*n） „ 1973年Weiner提出线性时间算法 „ 1976年McCreigh提出更节约内存 的算法 „ 1995年Ukkonen提出线性时间建 树算法

GsT通用后缀树( Generalized) 对于长度为n的字符串建立后缀树, WINDOWS INDIGOS 1234567 1234567 直接的方法时间复杂度为o(n*n) 1973年 Weiner提出线性时间算法 ·1976年 Mccreigh提出更节约内存 的算法 1995年 Ukkonen提出线性时间建 树算法 123)(L,4) 8只岛。 北大物些 有,轴即叠究 帖·有,轨盘即彭究 单词粒度的后缀树 后缀树的应用 “ I know you know$” ■查找字符串中的子串 ■统计S中出现T的次数 ■找出S中最长的重复子串 出现了两次以上的子串 know 两个字符串的公共子串 最长共同前缀(LcP) 回文串 北京大学值歌张写所有即究 后缀树的应用 后缀数组 ■中文切词 字符串S的后缀数组SA 关联分析 发现经常共同出现的短语 对s的所有后缀的指针排序 ■频繁模式挖掘 即后缀树叶结点的字典序 STC聚类 m后缀树ST=后缀数组SA+ ■基因/蛋白序列对比/分类 LcP数组

4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 z 对于长度为n的字符串建立后缀树， 直接的方法时间复杂度为O（n*n） z 1973年Weiner提出线性时间算法 z 1976年McCreigh提出更节约内存 的算法 z 1995年Ukkonen提出线性时间建 树算法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 GST——通用后缀树(Generalized) $ O ND W I $OG D $OGI OW$ $OG ND $OGI OW$ $OGI OW$ $W $ INDOW$ $ (2, 3) (1, 4) (2, 5) (2, 4) (2, 1) (1, 2) (2, 2) (1, 3) (1, 5) (2, 6) (1, 6) (1, 1) (1, 7) (2, 7) WINDOW$ INDIGO$ 1234567 1234567 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 单词粒度的后缀树 z “I know you know $ ” 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 后缀树的应用 „ 查找字符串中的子串 „ 统计S中出现T的次数 „ 找出S中最长的重复子串 „ 出现了两次以上的子串 „ 两个字符串的公共子串 „ 最长共同前缀(LCP) „ 回文串 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 后缀树的应用 „ 中文切词 „ 关联分析 „ 发现经常共同出现的短语 „ 频繁模式挖掘 „ STC 聚类 „ 基因/蛋白序列对比/分类 „ …… 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 后缀数组 „ 字符串S的后缀数组SA „ 对S的所有后缀的指针排序 „ 即后缀树叶结点的字典序 „ 后缀树ST = 后缀数组SA + LCP数组

数组( Suffix Array) 代价分析 6 ALAMS MALAYALAM [2 ALAYALAMS 目标长n=S,模式长m=/P 23456789 空间代价 [62|843195101P 建数据结构时间代价 后缀数组 B112010o]9 查找子串时间代价 最长公共 SA O(m log n 后緞2和8共事 LcP总是相邻的 北大物些 有,轴即叠究 物啦 铭权有,轨量邮多究 后级树小结 122二叉树结构的改进 后缀树和后缀数组提供了很好的 最佳二叉排序树 全索引结构 平衡的二叉搜索树 适合于各种字符串算法 伸展树 ■大量后缀树的变种 尽力减少其空间消耗 北京大学值歌张写所有即究 ASL(n) 最佳二叉搜索树的动态规划 ■最佳子结构、重复子结构 任何子树都是最佳二又搜索树 动态规划过程 第一步:构造包含1个结点的最佳二叉搜索树 5D3○H 第二步构造包含2个结点的最佳二叉搜索树 找t(0,2),t1,3),…,tn-2,n) 再构造包含3,4,…个结点的最佳二叉搜索树 最后构造t(0,n 5

5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 数组(Suffix Array) 10 $ 5 YALAM$ 9 M$ 1 MALAYALAM$ 3 LAYALAM$ 7 LAM$ 4 AYALAM$ 8 AM$ 2 ALAYALAM$ 6 ALAM$ M A L A Y A L A M $ 1 2 3 4 5 6 7 8 9 10 6 2 8 4 7 3 1 9 5 10 后缀数组 3 1 1 0 2 0 1 0 0 - 最长公共前缀数组 后缀6和2共享 “ALA” 后缀2和8共享 “A” LCP总是相邻的 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 代价分析 „ 目标长n=|S|，模式长m=|P|) „ 空间代价 „ ST 20n „ SA 4n „ 建数据结构时间代价 „ ST O(n) „ SA O(nlogn) „ 查找子串时间代价 „ ST O(m) • SA O(m log n) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 后缀树小结 „ 后缀树和后缀数组提供了很好的 全索引结构 „ 适合于各种字符串算法 „ 大量后缀树的变种 „ 尽力减少其空间消耗 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 12.2 二叉树结构的改进 „ 最佳二叉排序树 „ 平衡的二叉搜索树 „ 伸展树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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 = = ⎡ ⎤ = ++ ′ ⎢ ⎥ ⎣ ⎦ ∑ ∑ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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)