字典树（Trie）

字典树（Trie）

syndi

2019 年 05 月 05 日

963 次浏览

暂无评论

1953字数

1. 什么是字典树

Trie树，又称字典树、前缀树，是一种树形结构，典型的应用场景是在一个海量数据集中快速查找某一个数据，类似功能的高效数据结构还有哈希表，不过哈希表受制于哈希函数的选取以及哈希表的容量，性能可能会有波动，而字典树就不会有这个问题。

字典树的优点是：最大程度上减少查找时无谓的字符比较，以减少时间复杂度。

下面具体介绍什么是字典树，以存储字符串为例。

首先字典树中每个节点只存储一个字符，但与二叉树相比，存储字符串的字典树节点有26个子节点，因为总共有26个英文字母，字典树的根节点不存储数据，然后根节点向下伸展出26个子节点分别表示一个字符串中第一个字符分别是26个字母的场景，然后这26个子节点又分别向下伸展26个子节点表示字符串的第二个字符。可以看出字典树所耗费的空间是非常大的，基本上是指数级增长，这也说明了字典树的一个性质：空间换时间。

一颗字典树

2. 字典树的操作

现在讨论字典树的各种操作，前面说字典树最主要的作用就是海量数据集查找，所以插入和查找是最重要的两个操作。

插入。首先假设有一个空字典树，root向下的26个指针全都指向NULL。现在要插入"apple"，首先取出第一个字符'a'，然后在字典树第一层找'a'所对应的节点是否存在，如果不存在则建立节点'a'。接下来以节点'a'为基准查找字符'p'是否存在，依此类推向下查找建立直到建立出一条'a' 'p' 'p' 'l' 'e'的路径，最终在'e'处设一个标志表示'a' 'p' 'p' 'l' 'e'是一条完整的路径，即存入了"apple"。

查找。可以想到查找操作相当之简单，依次在树里查找对应的字母即可。可知在字典树中查找一个字符串的时间复杂度为O(S)，S为这个字符串的长度。

3. 字典树实现

#define R 26  // 26个小写字母

typedef struct prefixTreeNode {
    struct prefixTreeNode* links[R];  // 每个节点26个分叉
    int isEnd;  // 0 or 1
} Node;

void nodeInit(Node** pRoot) {
    *pRoot = (Node *)malloc(sizeof(Node));
    for (int i = 0; i < R; i++) {
        (*pRoot)->links[i] = NULL;
    }
    (*pRoot)->isEnd = 0;
}

void prefixTreeInsert(Node* root, char* str) {
    Node* cur = root;

    while (*str) {  // 取出str中每个字符
        if (cur->links[*str - 'a'] == NULL) {  // 如果这个字符不存在
            nodeInit(&(cur->links[*str - 'a']));
        }
        cur = cur->links[*str - 'a'];  // cur前进到下一层    
        str++;
    }
    cur->isEnd = 1;
}

int prefixTreeSearch(Node* root, char* str) {
    Node* cur = root;

    while (*str) {
        if (cur->links[*str - 'a'] == NULL) {
            return 0;
        }
        else {
            cur = cur->links[*str - 'a'];
            str++;
        }
    }
    return cur->isEnd == 1;
}