什么是trie树？

Trie树（前缀树或字典树）是一种用于高效存储和检索字符串的数据结构。其主要特点是通过共享前缀来优化存储和查询。

Trie 树是一种多叉树的结构，每个节点保存一个字符，一条路径表示一个字符串

例如：字符串him、her、cat、no、nova构成的trie树如下图所示
trie树1.png

从图中可以看出 Trie 树包含以下性质：

  • 根节点不包含字符，其他节点包含一个字符。

  • 从根节点到某一节点经过的字符连接起来构成一个字符串。如图中的 him 、 her 、 cat 、 no 、 nova。

  • 一个字符串与 Trie 树中的一条路径对应。

  • 在实现过程中，会在叶节点中设置一个标志，用来表示该节点是否是一个字符串的结尾，本例中用青色填充进行标记。

Trie 树中每个节点存储一个字符，从根节点到叶节点的一条路径存储一个字符串。另外，有公共前缀的字符串，他们的公共前缀会共用节点。如 her、 him 共用 h 节点。
trie树2.png

如何生成tire树？

Trie 树的生成过程，就是不断将字符串插入树中。

以插入字符串 him 、 her 、 cat 、 no 、 nova 为例，过程如下：

  1. 插入him：
    trie树3.gif
  • 根节点不存在子节点 h，因此创建子节点 h。
  • 在节点 h 的基础上插入第二个字符 i。
  • 节点 h 不存在子节点 i，创建子节点 i。
  • 在节点 i 的基础上插入第三个字符 m。
  • 节点 i 不存在子节点 m，创建子节点 m。并将该节点标记为字符串结束标志，完成 him 字符串插入。
  1. 插入her：
    trie树4.gif
  • 根节点存在子节点 h。不用重新创建子节点 h。
  • 在节点 h 的基础上插入第二个字符 e。
  • 节点 h 不存在子节点 e，创建子节点 e。
  • 在节点 e 的基础上插入第三个字符 r。
  • 节点 e 不存在子节点 r，创建子节点 r。并将该节点标记为字符串结束标志，完成 her 字符串插入。
  1. 插入cat：
    trie树5.gif
  • 根节点不存在子节点 c，因此创建子节点 c。
  • 在节点 c 的基础上插入第二个字符 a。
  • 节点 c 不存在子节点 a，创建子节点 a。
  • 在节点 a 的基础上插入第三个字符 t。
  • 节点 a 不存在子节点 t，创建子节点 t。并将该节点标记为字符串结束标志，完成 cat 字符串插入。
  1. 插入no：
    trie树6.gif
  • 根节点不存在子节点 n，因此创建子节点 n。
  • 在节点 n 的基础上插入第二个字符 o。
  • 节点 n 不存在子节点 o，创建子节点 o。并将该节点标记为字符串结束标志，完成 no 字符串插入。
  1. 插入nova：
    trie树7.gif
  • 根节点存在子节点 n，不用重新创建子节点 n。
  • 在节点 n 的基础上插入第二个字符 o。
  • 节点 n 存在子节点 o，不用重新创建子节点 o。
  • 在节点 o 的基础上插入第三个字符 v。
  • 节点 o 不存在子节点 v，创建子节点 v。
  • 在节点 v 的基础上插入第四个字符 a。
  • 节点 v 不存在子节点 a，创建子节点 a。并将该节点标记为字符串结束标志，完成 nova 字符串插入。

如何删除一个字符串？

删除一个字符串需要考虑的地方较多。

  • 情况一：待删除的字符串末尾为叶节点，且与其它字符串无公共前缀。将节点逐一删除即可，例如删除 cat。
    trie树8.png

  • 情况二：待删除字符串末尾不是叶节点。将字符串标志位置为 false 即可，例如删除 no 。
    trie树9.png

  • 情况三：待删除字符串末尾为叶节点，并且中间有其它单词。逐一删除节点，直到待删除节点是另一个字符串的结尾为止，例如删除 nova。
    trie树10.png

  • 情况四：待删除字符串某一节点还有其它子节点。逐一删除节点，如果待删除节点还有其它子节点，则停止删除，例如删除 him。
    trie树11.png

Trie树有什么用？

Trie 树又叫字典树。字典是用来查字的，Trie 树最基本的作用是在树上查找字符串。

例如有 5 个字符串： him 、 her 、 cat 、 no 、 nova 。现在要查找 catch 是否存在。

如果使用暴力的方法，需要用 catch 与这 5 个字符串分别进行匹配，效率较低。

如果将这 5 个字符串存储成 Trie 的结构，只需要顺着路径依次比较，比较完 cat 之后，没有节点与 c 匹配，所以字符串集合中不存在 catch。
trie树12.gif

优缺点

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

  • 优点

插入和查询的效率很高，都为O(m)。其中 m 是待插入/查询的字符串的长度。。

  • 缺点

空间消耗比较大。

代码实现

c++
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Trie {
private:
    vector<Trie*> children; // 每个节点包含 26 个子节点指针（对应 26 个小写字母）
    bool isEnd; // 标记当前节点是否是一个单词的结尾

    // 查找前缀是否存在
    Trie* searchPrefix(string prefix) {
        Trie* node = this; // 从根节点开始
        for (auto ch : prefix) {
            ch -= 'a'; // 将字符转换为索引（a -> 0, b -> 1, ..., z -> 25）
            if (node->children[ch] == nullptr) {
                return nullptr; // 如果字符不存在，返回空指针
            }
            node = node->children[ch]; // 移动到子节点
        }
        return node; // 返回前缀的最后一个节点
    }

public:
    // 构造函数，初始化子节点数组和 isEnd 标志
    Trie() : children(26), isEnd(false) {}

    // 插入一个单词到 Trie 树中
    void insert(string word) {
        Trie* node = this; // 从根节点开始
        for (auto ch : word) {
            ch -= 'a'; // 将字符转换为索引
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie(); // 如果子节点不存在，创建新节点
            }
            node = node->children[ch]; // 移动到子节点
        }
        node->isEnd = true; // 标记单词结尾
    }

    // 查找一个单词是否在 Trie 树中
    bool search(string word) {
        Trie* node = this->searchPrefix(word); // 查找单词的前缀
        return node != nullptr && node->isEnd; // 如果节点存在且是单词结尾，返回 true
    }

    // 查找是否有单词以给定前缀开头
    bool startWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr; // 如果前缀存在，返回 true
    }
};

int main() {
    Trie trie; // 创建 Trie 树对象

    // 插入单词
    trie.insert("a");
    trie.insert("abc");
    trie.insert("aapple");

    // 查找单词 "ab" 是否在 Trie 树中
    cout << trie.search("ab") << endl; // 输出 0（false），因为 "ab" 未被插入

    return 0;
}