Trie结构示意图 元素为2、5、9、17、41、45、63 0(<32) 1(>32) 0(<16)∝1(>16)1(48) 0(<48) 0(<8) 1(>40) 17 63 0(<4) (>4) 0(<44 1(>44) 45 北京大学信息学院 版权所有,转载或翻印必究 Page 11
北京大学信息学院 ©版权所有，转载或翻印必究 Page 11 Trie结构示意图
Trie结构应用:“字符树” 存储字典里面的单词 英文的单词是有26个字母组成的 (简单起见,我们忽略大小写) 英文字符树每一个内部结点都有 26个子结点 树的高度为最长字符串长度 北京大学信息学院 版权所有,转载或翻印必究 Page 12
北京大学信息学院 ©版权所有，转载或翻印必究 Page 12 Trie结构 应用：“字符树” ◼ 存储字典里面的单词 ◼ 英文的单词是有26个字母组成的 （简单起见，我们忽略大小写）， ◼ 英文字符树每一个内部结点都有 26个子结点 ◼ 树的高度为最长字符串长度
英文字符树 存储单词and、ant、bad、be a e d e an d bad bee 一棵子树代表具有相同前缀的关键码的集合。例如 “an”子树代表具有相同前缀an-的关键码集合{and, an t 北京大学信息学院 版权所有,转载或翻印必究 Page 13
北京大学信息学院 ©版权所有，转载或翻印必究 Page 13 英文字符树 ◼ 一棵子树代表具有相同前缀的关键码的集合。例如 “an”子树代表具有相同前缀an-的关键码集合{and， ant}
字符树的改进 由于单词可能不等长,所以更好的存储是其内部结点 不存储单词信息,只有叶结点才存储单词信息 存储单词an、and、ant、bad、bee b and ant bad bee 北京大学信息学院 版权所有,转载或翻印必究 Page 14
北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 字符树的改进 ◼ 由于单词可能不等长 ，所以更好的存储是其内部结点 不存储单词信息，只有叶结点才存储单词信息
字符树的改进(续) 观察上图中的bad和be个单词,它们的父结 点都只有一个儿子就是它们自己,也就是说 实际上它们在父结点的时候就已经被区分开了 因为我们真正想做的是要检索每一个单词,不 需要在已经能够区分每个单词的情况下继续进 行分裂结点的动作 北京大学信息学院 版权所有,转载或翻印必究 Page 15
北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 字符树的改进（续） ◼ 观察上图中的bad和bee两个单词，它们的父结 点都只有一个儿子就是它们自己，也就是说， 实际上它们在父结点的时候就已经被区分开了 ◼ 因为我们真正想做的是要检索每一个单词，不 需要在已经能够区分每个单词的情况下继续进 行分裂结点的动作