Trie树

Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。下图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。
Trie树
从上图可以归纳出Trie树的基本性质：
1.根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
2.从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符互不相同。
通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树（Prefix Tree）。

Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

优点

1.插入和查询的效率很高，都为O(m)，其中 m 是待插入/查询的字符串的长度。
2.Trie树中不同的关键字不会产生冲突。
3.Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。
4.Trie树不用求 hash 值，对短字符串有更快的速度。通常，求hash值也是需要遍历字符串的。
5.Trie树可以对关键字按字典序排序。

补充：关于查询，hash 表时间复杂度是O(1)，但哈希搜索的效率通常取决于 hash 函数的好坏。一个不好的 hash 函数导致很多的冲突，效率并不一定比Trie树高。

缺点

1.当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。
2.空间消耗比较大。

Trie树的应用

1.字符串检索
检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较：
如果沿路比较发现不同的字符，则表示该字符串在集合中不存在。
如果所有字符全部比较完且全部相同，还需判断最后一个节点的标志位（标记该节点是否代表一个关键字）。

struct trie_node
{
    bool isKey;   // 标记该节点是否代表一个关键字
    trie_node *children[26]; // 各个子节点 
};

2.词频统计
Trie树常被搜索引擎系统用于文本词频统计。
思路：为了实现词频统计，修改节点结构，用一个整型变量count来计数。对每一个关键字执行插入操作，若已存在则计数加1，若不存在则插入后count置1。

struct trie_node
{
    int count;   // 记录该节点代表关键字的频数
    trie_node *children[26]; // 各个子节点 
};

注意：哈希表也可应用在字符串检索和词频统计中。

3.字符串排序
Trie树可以对大量字符串按字典序进行排序。
思路也很简单：遍历一次所有关键字，将它们全部插入Trie树，树的每个结点的所有儿子很显然地按照字母表排序，然后先序遍历输出Trie树中所有关键字即可。

4.前缀匹配
例如找出一个字符串集合中所有以ab开头的字符串。只需用所有字符串构造一个Trie树，然后输出以a->b->开头的路径上的关键字即可。
Trie树前缀匹配常用于搜索提示。例如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

5.作为其他数据结构和算法的辅助结构
如后缀树，AC自动机等。

Trie树的C++代码实现

假设所有的关键字都由 a-z 的字母组成。对于Trie树一般只实现插入和搜索操作。这段代码可以用来检索单词和统计词频。

#include <stdio.h>
#define ALPHABET_SIZE 26

struct trie_node{
    int count;   //记录该节点代表关键字的频数
    trie_node *children[ALPHABET_SIZE]; // 各个子节点
};

//typedef struct trie_node{//C语言写法
//    int count;   //记录该节点代表关键字的频数
//    struct trie_node *children[ALPHABET_SIZE]; // 各个子节点
//}*trie;
//或者如下写法：
//typedef struct trie_node *trie；
//struct trie_node{
//    int count;   //记录该节点代表关键字的频数
//    trie children[ALPHABET_SIZE]; // 各个子节点
//};

trie_node *create_trie_node(){
    trie_node *pNode = new trie_node();
    pNode->count = 0;
    for(int i=0; i<ALPHABET_SIZE; ++i){
    	pNode->children[i] = NULL;
    }

    return pNode;
}

void trie_insert(trie_node *root, char *key){
    trie_node *node = root;
    char *p = key;
    while(*p)//遍历单个字符串中所有字符
    {
        if(node->children[*p-'a'] == NULL)
        {
            node->children[*p-'a'] = create_trie_node();
        }
        node = node->children[*p-'a'];
        p++;
    }//该字符串最后一个字符插入Trie中，*p='\0',即*p=0
    node->count += 1;//将最后一个字符节点中的count计数加1
}

// 查询，不存在返回0，存在返回出现的次数
int trie_search(trie_node *root, char *key){
    trie_node *node = root;
    char *p = key;
    while(*p && node!=NULL)
    {
        node = node->children[*p-'a'];
        p++;
    }//循环终止条件: 1.*p=0 2.*p=0,node==NULL

    if(node == NULL)//查询的字符串不在Trie的关键字中,*p可能为0，也可能不为0
        return 0;
    else
        return node->count;//此时node!=NULL,必然是*p=0
}

int main()
{
    // 关键字集合
    char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
    trie_node *root = create_trie_node();

    // 创建Trie树
    for(int i = 0; i < 8; i++){
        trie_insert(root, keys[i]);
    }

    // 检索字符串
    char s[2][32] = {"Present in trie", "Not present in trie"};
    printf("%s --- %s\n", "the", trie_search(root, "the")>0?s[0]:s[1]);
    printf("%s --- %s\n", "these", trie_search(root, "these")>0?s[0]:s[1]);
    printf("%s --- %s\n", "their", trie_search(root, "their")>0?s[0]:s[1]);
    printf("%s --- %s\n", "thaw", trie_search(root, "thaw")>0?s[0]:s[1]);
    return 0;
}

参考博客

Trie树

Trie树

优点

缺点

Trie树的应用

Trie树的C++代码实现

相关推荐