Trie 树是一种用于快速检索的多叉树结构,经常用于统计和排序大量的字符串（但又不限于字符串），所以经常被搜索引擎系统用于文本词频统计。本文首先介绍 Trie 树的定义、原理及具体实现，然后结合 hihocoder 上的题目做一些具体实践。

定义和原理

Trie树又称字典树，单词查找树，是一种树形结构，是一种哈系树的变种，也是一种用于快速检索的多叉树结构。它有三个基本特征：

• 根节点不包含字符，除根节点外每个节点都只包含一个字符
• 从根节点到某个节点，路径上经过的字符连起来就是对应的字符串
• 每个节点的所有字节点所包含的字符都不相同

除此之外，Trie 树一般包含两个基本操作：

• InsertTrie 将字符串记录到 Trie 树中，顺便统计词频
• SearchTrie 查询 Trie 树中公共字符串出现的次数

此外还有个基本方法，CreateNode，用于建立 Trie 树的节点并初始化。有了这些方法，Trie 树就可以构建成功。

对于文本词频的统计，也可以对相同长度的词生成 hash 表，不过此时查找的复杂度要达到 $O(M)$，M 为词的数目。而 Trie 树在性能上高于哈希表，其插入和查询的复杂度是 $O(N)$，N 为词的长度。不过Trie树的内存消耗非常大，达到 $26^N$ 级别（用左儿子右兄弟的方法建树可能会好点），这就是空间换时间的思想，换句话说是利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

代码实现

• Trie树节点定义

  1#define MAX 26
  2typedef struct Node{
  3    int count;
  4    struct Node *next[MAX];
  5}TrieNode;
  

  ``
  这里的宏定义MAX代表26个字母表。

• Trie树节点初始化 CreateNode

   1// 创建新节点
   2TrieNode* CreateNode(){
   3    int i=0;
   4    TrieNode *p = (TrieNode*)malloc(sizeof(TrieNode));
   5    p->count=1;
   6    for(i=0; i<MAX; i++){
   7        p->next[i]=NULL;
   8    }
   9    return p;
  10}
  

  CreateNode` 是 Trie 树节点的创建初始化函数，并返回节点指针。

• Trie树插入操作 $O(N)$

   1// 插入字典树
   2void InsertTrie(TrieNode** pRoot, char *s){
   3    TrieNode *p = NULL;
   4    // 基本不太可能出现*pRoot为NULL，因为Trie树根节点一定存在
   5    if (*pRoot == NULL){
   6        *pRoot = CreateNode();
   7    }
   8    p = *pRoot;
   9    int i=0,index;
  10    while(s[i] != '\0'){
  11        index = s[i++] - 'a';
  12        if(p->next[index] == NULL){
  13            // 新路径要创建新节点
  14            p->next[index] = CreateNode();
  15        }else{
  16            // 旧路径需要统计次数
  17            p->next[index]->count++;
  18        }
  19        p = p->next[index];
  20    }
  21}
  

• Trie树的查询操作 $O(N)$

   1// 查找字典树
   2int SearchTrie(TrieNode** pRoot, char *s){
   3    TrieNode *p = NULL;
   4    // 基本不太可能出现的情况
   5    if(*pRoot == NULL){
   6        return 0;
   7    }
   8    p = *pRoot;
   9    int i=0,index;
  10    while(s[i] != '\0'){
  11        index = s[i++] - 'a';
  12        // 未知字符说明不存在
  13        if (p->next[index] == NULL){
  14            return 0;
  15        }else{
  16            p = p->next[index];
  17        }
  18    }
  19    return p->count;
  20}
  

解题报告

• HihoCoder

  1. 第二周： Trie树 | 源码

     注意点：

     1. Trie 树的根节点不包含字符，不能为空的。插入和搜索操作中的判别是为了代码的健壮性。

参考文献

1. 维基百科之字典树