Windless
订阅/Feed
稗田千秋(i@wind.moe)

TRIE 树

稗田千秋
Mar.26 2016 algorithm

字典树(TRIE树,前缀树)是一种树形结构,核心思想是以空间换时间,常用于在相对较低的复杂度内统计和排序大量的字符串。

基本性质

与二叉查找树不同,字典树的键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

结构体结构

如果用数组来存储,当是稀疏数组时无疑浪费了大量空间,于是使用链表来压缩存储空间,其中children是一个指针数组,存放指向各个子节点的指针。

typedef struct node{
    int count;  //统计前缀次数
    struct node *children[TREE_WIDTH];  //指向子节点
    int flag;  //按需使用
}

代码实现

下面给出一种C语言前缀查询的代码,代码大同小异,需要时仅需稍作改动即可食用。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARRAY_SIZE(a) sizeof(a) / sizeof(a[0])
#define CHAR_TO_INDEX(c) c - 'a'
#define MEM(x,y) memset(x,y,sizeof(x))
#define TREE_WIDTH 256

typedef struct node{
    int count;
    struct node *children[TREE_WIDTH];
}TrieNode, *Trie;

TrieNode* create(){
    TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode));
    node->count = 0;
    MEM(node->children, 0);
    return node;
}

void insert(Trie root, char* word){
    Trie node = root;
    char *p = word;
    while (*p){
        if (node->children[CHAR_TO_INDEX(*p)] == NULL)
            node->children[CHAR_TO_INDEX(*p)] = create();
        node = node->children[CHAR_TO_INDEX(*p++)];
        node->count += 1;
    }
}

int search(Trie root, char* word) {
    Trie node = root;
    char *p = word;
    while (*p){
        node = node->children[CHAR_TO_INDEX(*p++)];
        if (node == NULL)
            return 0;
    }
    return node->count;
}

int main() {
    Trie root = create();
    char words[][10] = { "hieda", "no", "chiaki", "handsome", "char", "int", "bool", "double", "not", "doubt" };
    for (int i = 0; i < ARRAY_SIZE(words); i++)
        insert(root, words[i]);
    printf("%d\n", search(root, "c"));
    printf("%d\n", search(root, "chiaki"));
    printf("%d\n", search(root, "result"));
}

下期自动机见w

--END--
文章创建于 2016-03-26 15:58:48,最后更新 2016-03-26 15:58:48
Comment
尝试加载Disqus评论, 失败则会使用基础模式.
    • play_arrow

    About this site

    version:1.02 Alpha
    博客主题: Lime
    联系方式: i@wind.moe
    写作语言: zh_CN & en_US
    博客遵循 CC BY-NC-SA 4.0许可进行创作

    此外,本博客会基于访客的Request Headers记录部分匿名数据用于统计(Logger的源码见Github),包含Referer, User-Agent & IP Address.个人绝不会主动将数据泄露给第三方