字符树的改进(续) 存储单词an、and、ant、bad、bee a a bad bee an nd ant 北京大学信息学院 版权所有,转载或翻印必究 Page 16
北京大学信息学院 ©版权所有，转载或翻印必究 Page 16 字符树的改进（续）
字符树中的检索 首先用待查关键码的第一个字符与树林的各个根的字 符相比 然后下一步的检索在前次比较相等的那棵树上进行其 中,用待查关键码的第二个字符与选定的这棵树的根 的各个子结点进行比较, 接着再沿着前次比较相等的分支进行进一步的检索 直到进行到某一层,该层所有结点的字符都与待查关 键码相应位置的字符不同,这说明此关键码在树目录 里没有出现; ■若检索一直进行到树叶,那么就在树目录里找到了给 定的关键码 北京大学信息学院 版权所有,转载或翻印必究 Page 17
北京大学信息学院 ©版权所有，转载或翻印必究 Page 17 字符树中的检索 ◼ 首先用待查关键码的第一个字符与树林的各个根的字 符相比较 ◼ 然后下一步的检索在前次比较相等的那棵树上进行其 中，用待查关键码的第二个字符与选定的这棵树的根 的各个子结点进行比较， ◼ 接着再沿着前次比较相等的分支进行进一步的检索 ◼ ... ◼ 直到进行到某一层，该层所有结点的字符都与待查关 键码相应位置的字符不同，这说明此关键码在树目录 里没有出现； ◼ 若检索一直进行到树叶，那么就在树目录里找到了给 定的关键码
Trie字符树的缺陷 Trie结构显然也不是平衡的 在它存取英文单词的时候,显然t子树下的分支比z子树下的 分支多很多(以t开头的单词比以z开头的单词多很多) 而且,每次有26个分支因子使得树的结构过于庞大,给检索 也带来了不便 ■字母在计算机中是以二进制ASCⅢ码的形式存储的 使用每个字母的二进制编码来代表这个字母 ■关键码就只有编码0和1 而不是a到z的26个字母 二叉Trie树 北京大学信息学院 版权所有,转载或翻印必究 Page 18
北京大学信息学院 ©版权所有，转载或翻印必究 Page 18 Trie字符树的缺陷 ◼ Trie结构显然也不是平衡的 ◼ 在它存取英文单词的时候，显然t子树下的分支比z子树下的 分支多很多（以t开头的单词比以z开头的单词多很多） ◼ 而且，每次有26个分支因子使得树的结构过于庞大，给检索 也带来了不便 ◼ 字母在计算机中是以二进制ASCII码的形式存储的 ◼ 使用每个字母的二进制编码来代表这个字母 ◼ 关键码就只有编码0和1 ◼ 而不是a到z的26个字母 ◼ 二叉Trie树
Trie树的插入 Trie树的插入 首先根据插入纪录的关键码找到需要插入的 结点位置 如果该结点是叶结点,那么就将为其分裂出 两个子结点,分别存储这个纪录和以前的那 个纪录 n如果是内部结点,则在那个分支上应该是空 的,所以直接为该分支建立一个新的叶结点 即可 北京大学信息学院 版权所有,转载或翻印必究 Page 19
北京大学信息学院 ©版权所有，转载或翻印必究 Page 19 Trie树的插入 ◼ Trie树的插入 ◼ 首先根据插入纪录的关键码找到需要插入的 结点位置 ◼ 如果该结点是叶结点，那么就将为其分裂出 两个子结点，分别存储这个纪录和以前的那 个纪录 ◼ 如果是内部结点，则在那个分支上应该是空 的，所以直接为该分支建立一个新的叶结点 即可
Trie树的删除 Trie树的删除 根据插入纪录的关键码找到需要删除的结点 位置 n如果一个被删除结点的父结点没有其他的儿 子,那么就需要合并 否则只需要将此分支设置为空即可 北京大学信息学院 版权所有,转载或翻印必究 Page 20
北京大学信息学院 ©版权所有，转载或翻印必究 Page 20 Trie树的删除 ◼ Trie树的删除 ◼ 根据插入纪录的关键码找到需要删除的结点 位置 ◼ 如果一个被删除结点的父结点没有其他的儿 子，那么就需要合并 ◼ 否则只需要将此分支设置为空即可