trie树--详解（转）
l Trie原理
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
l Trie性质
好多人说trie的根节点不包含任何字符信息，我所习惯的trie根节点却是包含信息的，而且认为这样也方便，下面说一下它的性质 (基于本文所讨论的简单trie树)
1.
字符的种数决定每个节点的出度，即branch数组(空间换时间思想)
2. branch数组的下标代表字符相对于a的相对位置
3.
采用标记的方法确定是否为字符串。
4.
插入、查找的复杂度均为O(len),len为字符串长度
l Trie的示意图
如图所示，该trie树存有abc、d、da、dda四个字符串，如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL
l TrieTrie的优点举例
已知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中发现的，详见本文配套的“入门练习”。
AekdyCoin大神在博客中提到Trie可以：
2.查询一个单词是否出现过，如果出现过那么显然他出现的次数cnt>=1...这应该是Tries的最基本运用了..
3.你想过数字也可以拿来这么Hash么？可以看成是一个字符集为10的Trie{'0','1',..'9'},显然<2^31的数字是只有最多10位,那么如此Hash真正做到了O(1)...不过在预处理的时候需要O(log10(N))来处理数字,一个方法是我们可以在输入的时候就用char[]来读-.-，以后再也不土土的写常数很大的Hash表了，就用Trie吧~
4.如果3可以，那么下面就可以随便yy了,比如坐标的Hash...整数的自然是没问题，在<2^31的范围内,显然大不了20位(正负特判)
同三维坐标...
MS是想怎么Hash就怎么Hash...肯定比我以前写的土土的Hash表快多了..
5.实数的Hash,对于给定上限小数点后位的实数来说，乘10^k就可以Hash了,注意可能溢出-_-
6.yy结论,Trie太强大了,以后Hash就靠它了-_-
搞了几个小时，看来以后数字的Hash还是少用Trie为妙..
l Trie的简单实现(插入、查询)
Code
#include <iostream>
#include <cstring>
using namespace std;
const int branchNum = 26; //声明常量
int i;
struct Trie_node
{
bool isStr; //记录此处是否构成一个串。
Trie_node *next[branchNum];//指向各个子树的指针,下标0-25代表26字符
Trie_node():isStr(false)
{
memset(next,NULL,sizeof(next));
}
};
class Trie
{
public:
Trie();
void insert(const char* word);
bool search(char* word);
void deleteTrie(Trie_node *root);
private:
Trie_node* root;
};
Trie::Trie()
{
root = new Trie_node();
}
void Trie::insert(const char* word)
{
Trie_node *location = root;
while(*word)
{
if(location->next[*word-'a'] == NULL)//不存在则建立
{
Trie_node *tmp = new Trie_node();
location->next[*word-'a'] = tmp;
}
location = location->next[*word-'a']; //每插入一步，相当于有一个新串经过，指针要向下移动
word++;
}
location->isStr = true; //到达尾部,标记一个串
}
bool Trie::search(char *word)
{
Trie_node *location = root;
while(*word && location)
{
location = location->next[*word-'a'];
word++;
}
return(location!=NULL && location->isStr);
}
void Trie::deleteTrie(Trie_node *root)
{
for(i = 0; i < branchNum; i++)
{
if(root->next[i] != NULL)
{
deleteTrie(root->next[i]);
}
}
delete root;
}
void main() //简单测试
{
Trie t;
t.insert("a");
t.insert("abandon");
char * c = "abandoned";
t.insert(c);
t.insert("abashed");
if(t.search("abashed"))
printf("true\n");
}
入门练习 ：PKU POJ 3630解题报告