Trie树可以:

  • 压缩存储大量的字符串
  • 快速找出具有相同前缀的字符串
  • 快速按字典序对字符串进行排序
  • …

主要操作

Trie树的主要操作包括:

  1. insert: 插入字符串。
  2. search: 查询某字符串是否存在。
  3. startsWith: 查询包含某前缀的字符串。
    • [str]: 返回所有包含该前缀的字符串。
    • bool: 返回是否存在。

实现

Trie树的实现和普通树的实现类似，可以用数组或链表实现。 这里的例子是链表实现的，如下是树节点的定义。

class TrieNode {
public:
    TrieNode* m_childs[26] = { nullptr };
    bool m_is_end;  // 是否是单词边界
    char m_c;
};

Trie树的定义如下:

class Trie {
public:
    Trie();
    void insert(string word);
    bool search(string word);
    bool startsWith(string prefix);

protected:
    TrieNode* root;
};