英文字符树26叉Trie 存单词and、ant、bad、be an”子树代表具有 相同前缀an-的关 a 键码集合{and, ant a e d d and ant bad be 一棵子树代表具有相同前缀的关键码的集合 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 6
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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}
字符树的改进(续) 存储单词an、 and ant bad bee e bad bee d ant 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 7
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 字符树的改进（续） 存储单词an、and、ant、bad、bee a n d t b a e and ant bad bee an *
Trie字符树的特点 Trie结构也不是平衡的 nt子树下的分支比z子树下的多 26个分支因子庞大的26叉树 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 8
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 Trie字符树的特点 Trie结构也不是平衡的 t子树下的分支比z子树下的多 26个分支因子——庞大的26叉树
PATRICIA结构 "Practical Algorithm To Retrieve Information Coded In Alphanumeric' D Morrision发明的Trie结构变体 根据关键码二进制位的编码来划分 二叉Trie树 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 9
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 PATRICIA 结构 “Practical Algorithm To Retrieve Information Coded In Alphanumeric” D.Morrision发明的Trie结构变体 根据关键码二进制位的编码来划分 二叉Trie树
PATRICIA结构图 Xxxxx xxxxx OOxxxx Olxxxx 1Oxxx ixxxx 00Oxxx 0Olxxx lxxx 1010x 101lxx 0000xx 0001x 5 编码:2:0000105:0001019:001001 17:01000141:10100145:10110163:111lll 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 10
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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