本文共 1632 字，大约阅读时间需要 5 分钟。
Trie树
9.2.1 Trie树的基本原理
trie树（也叫字典树）是种树形结构。它是词典的一种存储方式，词典中的每一个单词在trie树中表现为一条从根结点出发的路径，路径中边上的字母连起来就形成对应的单词。图9.3就是一棵trie树，其中含有a,abc,bac,bbc,ca五个单词。
其基本性质可以归纳为：
根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符串连接起来，为该节点对应
的字符串。
3.每个节点的所有子节点包含的字符都不相同。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），
所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度
地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询
时间的开销以达到提高效率的目的。 图9.3
9.2.2 Trie树的基本操作
Trie树的基本操作有，插入、查找和删除，删除这个操作不常用到，在这里只讲一下关于Trie树的插入与查找操作。
节点的基本结构：
struct trie { int num; //记录到达这里的字符串有多少个。 bool terminal; //如果terminal==true ，则当前节点为该字符串最后一个字符。 struct trie *next[sonnum]; //记录下一个节点 };
void init_trie(trie &p) //创建一个新节点
{
p = (trie)malloc( sizeof(node) );
for(int i = 0; i < 26; i++)
p->next[i] = null;
p->terminal = false;
p->num = 0;
}
假设字符串为str且只包含小写英文字母，Trie树的根节点为root。令i=0，p=root。
插入操作：
1.取str[i]，判断p->next[str[i]-97]是否为空，若为空则建立结点temp，并将p->next[str[i]-97]指向temp，然后p指向temp；若不为空，则p=p->next[str[i]-97]；
2.i++，继续取str[i]，循环1中的操作，直到遇到结束符'\0'，此时将当前结点p中的terminal置为true。
代码实现：
void insert(char str[])
{
int i = 0;
trie *p = root;
while(str[i] != '\0')
{
if( ! p->next[str[i]-'a'])
{
trie *q;
init_trie(q);
p->next[str[i]-'a'] = q;
}
p= p->next[str[i]-'a'];
p->num++;
i++;
}
p->terminal = true;
}
查找操作：
查找操作与插入操作步骤一样，但不需要插入而是查找每个字符是否在trie树里。
取str[i]，判断p->next[str[i]-’a’]是否为空，若空则表示查找失败，否则，i++，p=p->next[str[i]-’a’],继续取str[i]，判断p->next[str[i]-’a’]是否为空，直到遇到结束符'\0'，表示查找成功，字符串str在trie树里。
int find(trie p,char str[])
{
int k = 0;
while(str[k] != '\0' && p->next[str[k]-'a'])
{
p = p->next[str[k]-'a'];
k++;
}
if(str[k] == '\0')
return 1;//找到了字符串str
return 0;//没找到
}
9.2.3 Trie树的复杂度分析
Trie树的插入查找操作的时间复杂度为 ，空间复杂度为 数量级，其中 为字符串的长度。
转载地址：http://qsali.baihongyu.com/