声明：以下介绍均基于本人理解

概述

  • 字典树(Trie)，像字典一样的树

属性

  • 树：一棵有根的树
  • 结点：一般以类似键值对的形式存在，即包含两个成员信息：字符(key)作为结点标识，数值(value)作为标识出现的频率
  • 应用：检索字符串(例如字符串本身或其前缀、后缀等)

模板

数组结构存储

数组结构示例图

数组结构示例

代码(数组树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <string>
class Trie {
public:
    int nex[100000][26] = {0};
    bool exist[100000] = {false};
    int cnt = 0;
    Trie() {
    }

    void insert(string word) {
        int p = 0;
        for (int i = 0; i < word.size(); i++) {
            int c = word[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
            p = nex[p][c];
        }
        exist[p] = 1;
    }

    bool search(string word) {
        int p = 0;
        for (int i = 0; i < word.size(); i++) {
            int c = word[i] - 'a';
            if (!nex[p][c]) return 0;
            p = nex[p][c];
        }
        return exist[p];
    }

};

链表结构存储

结点结构示例图

结构体示例

代码(链表树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <string>
class Trie {
public:
    struct Node {
        Node* next[26];
        int freq;
        bool exist = false;
    };
    Node* root;
    Trie() {
        root = new Node();
        root->freq = 0;
        for (int i = 0; i < 26; ++i) {
            root->next[i] = nullptr;
        }
    }

    void insert(string word) {
        auto cur = root;
        for (auto c: word) {
            if (cur->next[c - 'a'] == nullptr) {
                cur->next[c - 'a'] = new Node();
                cur->next[c - 'a']->freq = 1;
                cur = cur->next[c - 'a'];
            } else {
                cur->next[c - 'a']->freq++;
                cur = cur->next[c - 'a'];
            }
        }
        cur->exist = true;
    }

    bool search(string word) {
        auto cur = root;
        for (auto c: word) {
            if (cur->next[c - 'a'] == nullptr) return false;
            cur = cur->next[c - 'a'];
        }
        return cur->exist;
    }

};

复杂度分析

预设所有字符串总长度为n

  • 构造字典树
    • 空间: O(nK)(对于结构体而言K为结点大小，对于数组而言K = 26)
    • 时间: O(n)
  • 检索
    • 时间：O(n)

题单

参考来源：灵茶山艾府

发散/随想/自身理解(?)

  • 字典树突出有序匹配，对前后缀有特效
  • 应用方面，以结构体示例，若标识不限字符，那么检索的目标即从字符串扩展到某种序列。