计算机软考程序员常考基础必知必会（42）-中华考试网

计算机软考程序员常考基础必知必会（42）

2016-4-20编辑:ljnbset

trie树

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

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

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

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