1.Trie导引
Trie树是一种基于树的数据结构，又称单词查找树、前缀树，字典树，是一种哈希树的变种。应用于字符串的统计与排序，经常被搜索引擎系统用于文本词频统计。用于存储字符串以便支持快速模式匹配，主要应用在信息检索中，Trie支持的主要查询操作是模式匹配和前缀匹配。Trie树可以看着是一个确定有限状态自动机，有限状态自动机另一篇博文字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽 有介绍。
在计算机科学中，trie，又称前缀树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
Trie 这个术语来自于 retrieval。根据词源学，trie 的发明者 Edward Fredkin 把它读作 /ˈtriː/ "tree"。[1][2] 但是，其他作者把它读作 /ˈtraɪ/ "try"。[1][2][3]（算法导论也叫做做基数树radix树或retrieval 树）
在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。
键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示 trie 的原理。
trie 中的键通常是字符串，但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie 中的键是一串位元，可以用于表示整数或者内存地址。
2.标准Trie
令S是取自字母表∑的s个集合，满足S中不存在一个串是另一个串的前缀。S的一个标准Trie（standard trie）是一颗有序书T，满足如下性质：
- 除了根之外，T中的每个结点标记有∑的一个字符。
- T中一个内部结点的子结点的次序有字母表∑上的规范次序确定。
- T有s个外部结点（叶结点），每个外部结点关联S中的一个串，满足从根到T中一个外部结点v的路径上标记连接产生S中关联的一个串。
下图是串{bear,bell,bid,bull,buy,sell,stock,stop}的标准Trie
#include<algorithm>
#include<iostream>
using namespace std; const int sonnum=,base='a';
struct Trie
{
int num;//to remember how many word can reach here,that is to say,prefix
bool terminal;//If terminal==true ,the current point has no following point
struct Trie *son[sonnum];//the following point
};
Trie *NewTrie()// create a new node
{
Trie *temp=new Trie;
temp->num=;temp->terminal=false;
for(int i=;i<sonnum;++i)temp->son[i]=NULL;
return temp;
}
void Insert(Trie *pnt,char *s,int len)// insert a new word to Trie tree
{
Trie *temp=pnt;
for(int i=;i<len;++i)
{
if(temp->son[s[i]-base]==NULL)
temp->son[s[i]-base]=NewTrie();
else
temp->son[s[i]-base]->num++; temp=temp->son[s[i]-base];
}
temp->terminal=true; } void Delete(Trie *pnt)// delete the whole tree
{
if(pnt!=NULL)
{
for(int i=;i<sonnum;++i)if(pnt->son[i]!=NULL)Delete(pnt->son[i]);
delete pnt;
pnt=NULL;
}
}
Trie* Find(Trie *pnt,char *s,int len)//trie to find the current word
{
Trie *temp=pnt;
for(int i=;i<len;++i)
{
if(temp->son[s[i]-base]!=NULL)
{
cout<<temp->son[s[i]-base]->num<<ends<<s[i]<<endl;//没有打印根节点的num
temp=temp->son[s[i]-base];
}
else return NULL;
}
return temp;
} int main()
{
Trie *root;
root=NewTrie();
Insert(root,"bear",);
Insert(root,"bell",);
Insert(root,"bid",);
Insert(root,"bull",);
Insert(root,"buy",); Trie *res;
res=Find(root,"bear",);
if(res!=NULL)
{
cout<<res->terminal;
}
else
cout<<"not found";
}
输出：
5 b
2 3
1 a
1 r
1 找到了。（代码参考：http://hi.baidu.com/luyade1987/item/7c1977f5e9015cdf6225d224）
存储总长为n,来自大小为d的字母表中s个串的集合S的标准Trie具有如下性质：
- T中每个内部结点最多有d个子结点。
- T有s个外部结点。（显然，有s个串）
- T的高度等于最长串的长度。
- T中的结点书为O(n)。
性能：对于有n个英文字母的串来说，在内部结点中定位指针所需要花费O(d)时间，d为字母表的大小，英文为26。由于在上面的算法中内部结点指针定位使用了数组随机存储方式，因此时间复杂度降为了O(1)。但是如果是中文字，下面在实际应用中会提到。因此我们在这里还是用O(d)。 查找成功的时候恰好走了一条从根结点到叶子结点的路径。因此时间复杂度为O(d*n)。但是，当查找集合X中所有字符串两两都不共享前缀时，trie中出现最坏情况。除根之外，所有内部结点都*一个子结点。此时的查找时间复杂度蜕化为O(d*(n^2))
http://en.wikipedia.org/wiki/Trie
http://blog.csdn.net/v_july_v/article/details/6897097