关键码空间( key space)分解 不依赖于关键码的插入顺序 树的深度受到关键码精度的影响 ■最坏的情况下,深度等于存储关键码所需要的位数 例如,如果关键码是0到255之间的整数,那么关键码 的精度就是8个二进制位。 如果有两个关键码:10000001000001,它们的前面7位都 是相同的 所以直到第8次划分才能将这两个关键码分开 n这样的搜索树深度也为8,但这是最坏的情况 北京大学信息学院 @版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 关键码空间（key space）分解 ◼ 不依赖于关键码的插入顺序 ◼ 树的深度受到关键码精度的影响 ◼ 最坏的情况下，深度等于存储关键码所需要的位数 ◼ 例如，如果关键码是0到255之间的整数，那么关键码 的精度就是8个二进制位。 ◼ 如果有两个关键码：10000010和10000011，它们的前面7位都 是相同的 ◼ 所以直到第8次划分才能将这两个关键码分开 ◼ 这样的搜索树深度也为8，但这是最坏的情况
基于关键码范围的分解 保证平衡吗? 显然是不行的 如果关键码的分布得很不均衡,将导 致树的结构失衡 一种极端的情况,导致所有的关键码都小 于根结点,那么以该结点为根的子树的右 子树将没有任何的元素 北京大学信息学院 @版权所有,转载或翻印必究 Page 7
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 ◼ 基于关键码范围的分解 ◼ 保证平衡吗？ ◼ 显然是不行的 ◼ 如果关键码的分布得很不均衡，将导 致树的结构失衡 ◼ 一种极端的情况，导致所有的关键码都小 于根结点，那么以该结点为根的子树的右 子树将没有任何的元素
Trie结构 基于关键码分解的数据结构,叫作 Trie结构 “trie”这个词来源于“ retrieva 主要应用 信息检索( information retrieval) 用来存储英文字符串,尤其大规模的 英文词典 自然语言理解系统中经常用到 北京大学信息学院 @版权所有,转载或翻印必究 Page 8
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 Trie结构 ◼ 基于关键码分解的数据结构，叫作 Trie结构 ◼ “trie”这个词来源于“retrieval” ◼ 主要应用 ◼ 信息检索（information retrieval） ◼ 用来存储英文字符串，尤其大规模的 英文词典 ◼ 自然语言理解系统中经常用到
Trie结构的适用情况 a Trie结构主要基于两个原则 有一个固定的关键码集合 对于结点的分层标记 襟锶历毁奇彀霉影樓聞饗蠻葛字母等来 ■例如,元素可以用0-9的数字来标记 在根结点的地方,它分出10个子结点,分别标记0-9 然后每个子结点又可以分出10个结点 如此下去直到所有的元素都能够被区分开 北京大学信息学院 @版权所有,转载或翻印必究 Page 9
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 Trie结构的适用情况 ◼ Trie结构主要基于两个原则 ◼ 有一个固定的关键码集合 ◼ 对于结点的分层标记 ◼ 如果所有的元素都可以使用数字或者字母等来 标记，那么就可以考虑使用Trie结构 ◼ 例如，元素可以用0-9的数字来标记 ◼ 在根结点的地方，它分出10个子结点，分别标记0-9 ◼ 然后每个子结点又可以分出10个结点 ◼ 如此下去直到所有的元素都能够被区分开
Trie结构特点 与B+树一样,基于关键码空间分解 的树结构,其内部结点仅作为占位 符引导检索过程,数据纪录只存储 在叶结点中 Huffman编码树( Huffman coding tree是一种二叉Trie树 北京大学信息学院 版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 Trie结构特点 ◼ 与B+树一样，基于关键码空间分解 的树结构，其内部结点仅作为占位 符引导检索过程，数据纪录只存储 在叶结点中 ◼ Huffman编码树( Huffman coding tree )也是一种二叉Trie树