PATRICIA结构 为了得到更加平衡的结构, D Morrision发明了 Trie结构的一种变体 PATRICIA Practical algorithm To Retrieve Information Coded In Alphanumeric 它不是对整个关键码大小范围的划分 而是根据关键码每一个二进制位的编码来划分 因为每一位要么是0,要么是1,所以分支因子是2, 生成的树是二叉树 北京大学信息学院 版权所有,转载或翻印必究 Page 21
北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 PATRICIA 结构 ◼ 为了得到更加平衡的结构，D.Morrision发明了 Trie结构的一种变体PATRICIA ◼ “Practical Algorithm To Retrieve Information Coded In Alphanumeric” ◼ 它不是对整个关键码大小范围的划分 ◼ 而是根据关键码每一个二进制位的编码来划分 ◼ 因为每一位要么是0，要么是1，所以分支因子是2， ◼ 生成的树是二叉树
PATRICIA结构图 OXXX xXXXX FOxx 01x10x ixxxX 000xK 2 17 2 63 001 101x 1010xX 1011x 0000xx 000 41 45 2 5 编码:2:0000105:0001019:001001 7:01000141:10100145:10110163:111111 北京大学信息学院 版权所有,转载或翻印必究 Page 22
北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 PATRICIA 结构图
PATRICIA结构图(续) 上图因为最大的数是63,用6位二进制表示即可 每一个结点都有一个标号,表示它是在比较第几位, 然后根据那一位是0还是1来划分左右两个子树 标号为2的结点的右子树一定是编码形式为xx1xxx(x表示该 位或0或1,标号为2说明比较第2位) 在图中检索5的话,5的编码为000101 首先我们比较第0位,从而进入左子树 然后在第1位仍然是0,还是进入左子树 在第2位还是0,仍进入左子树 第3位变成了1,从而进入右子树,就找到了位于叶结点的数 字5 北京大学信息学院 版权所有,转载或翻印必究 Page 23
北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 PATRICIA 结构图（续） ◼ 上图因为最大的数是63，用6位二进制表示即可 ◼ 每一个结点都有一个标号，表示它是在比较第几位， 然后根据那一位是0还是1来划分左右两个子树 ◼ 标号为2的结点的右子树一定是编码形式为xx1xxx （x表示该 位或0或1，标号为2说明比较第2位） ◼ 在图中检索5的话，5的编码为000101 ◼ 首先我们比较第0位，从而进入左子树 ◼ 然后在第1位仍然是0，还是进入左子树 ◼ 在第2位还是0，仍进入左子树 ◼ 第3位变成了1，从而进入右子树，就找到了位于叶结点的数 字5
PATRICIA结构图改进 观察 PATRICIA的图发现有与Tre图类似的情况 在区分2和5、41和45的时候,在第三个二进制 位的比较是不能区别它们的 可以将它省略,得到一棵更为简洁的树 北京大学信息学院 版权所有,转载或翻印必究 Page 24
北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 PATRICIA 结构图改进 ◼ 观察PATRICIA的图发现有与Trie图类似的情况 ◼ 在区分2和5、41和45的时候，在第三个二进制 位的比较是不能区别它们的 ◼ 可以将它省略，得到一棵更为简洁的树
PATRICIA结构图改进(续) OxXX 0 lxx FOxx Olxxxx 10XX 11xx 17 000xo 2 63 1011xX 001xx 1010x 0000xx 0001xx 941 45 2 5 编码:2:00005:0001019:001001 17:01000141:10100145:10110163:111111 北京大学信息学院 版权所有,转载或翻印必究 Page 25
北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 PATRICIA 结构图改进（续）