字符树的改进(续) 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: llllll2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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树是满二叉树 „ 每个内部结点都代表一个位的比较 „ 必然产生两个子结点 „ 一次检索不超过关键码的位个数