2011年软考程序员考试复习笔试知识点整理(9)3

 　　(6)trie树

　　Trie树，即Double Array字典查找树，既可用于一般的字典搜索，也可用于索引查找。

　　每个节点相当于DFA的一个状态，终止状态为查找结束。有序查找的过程相当于状态的不断转换

　　对于给定的一个字符串a1,a2,a3,...,an.则

　　采用TRIE树搜索经过n次搜索即可完成一次查找。不过好像还是没有B树的搜索效率高，B树搜索算法复杂度为logt(n+1/2).当t趋向大，搜索效率变得高效。

　　Trie树的优点举例

　　已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法：

　　1. 最容易想到的：即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为O(n^2)。

　　2. 使用hash：我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)* O(1)= O(n)。

　　3. 使用trie：因为当查询如字符串abc是否为某个字符串的前缀时，显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len)，而建立+查询在trie中是可以同时执行的，建立的过程也就可以成为查询的过程，hash就不能实现这个功能。所以总的复杂度为O(n*len)，实际查询的复杂度只是O(len)。

　　解释一下hash为什么不能将建立与查询同时执行，例如有串：911，911456输入，如果要同时执行建立与查询，过程就是查询911，没有，然后存入9、91、911，查询911456，没有然后存入9114、91145、911456，而程序没有记忆功能，并不知道911在输入数据中出现过。所以用hash必须先存入所有子串，然后for循环查询。

　　而trie树便可以，存入911后，已经记录911为出现的字符串，在存入911456的过程中就能发现而输出答案;倒过来亦可以，先存入911456，在存入911时，当指针指向最后一个1时，程序会发现这个1已经存在，说明911必定是某个字符串的前缀，该思想是我在做pku上的3630中发现的，详见本文配套的"入门练习"。

　　小结

　　B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点;

　　B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点;所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中;

　　B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

　　B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3;