字典树 · 翼仔的博客

定义链接到标题

字典树（Trie），是一个像字典一样的树，又称前缀树。

可以高效的查询某个字符串是否在一组给定的字符串中，或者说查询某个单词是否在字典中。

字典树的查询时间复杂度可以认为是 $O(l)$，其中 $l$ 为待查询单词的长度。

引入链接到标题

字典树示意图：

bAGz3DrkXeP5vch

可以发现，这棵字典树用边来代表字母，而根结点到树上面某一个节点的路径就代表一个字符串，例如 $1\rightarrow 4\rightarrow 8\rightarrow 12$ 表示的就是字符串 caa，如果结点 $12$ 对应的 end_ 字段的值为 $true$，说明 caa 是字典树中一个完整的字符串，否则只是一个前缀。

trie 的结构非常好懂，我们用 $\delta(u,c)$ 表示结点 $u$ 的 $c$ 字符指向的下一个结点，或着说是结点 $u$ 代表的字符串后面添加一个字符 $c$ 形成的字符串的结点。（ $c$ 的取值范围和字符集大小有关，不一定是 $0\sim 26$ 。）

字典树的实现链接到标题

这里放一个简单的前缀树的类的实现，

struct Trie {
  int nex[10000][26], cnt; // nex 的第一维度表示前缀树的结点数量，与上面的图相对应
  bool end[10000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }

  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

也可以使用 new 动态创建前缀树，例如：

class Trie {
  private:
    vector<Trie *> vec;
    bool is_end;

  public:
  	Trie() : vec(26), is_end(false) {
        for (int i = 0; i < 26; ++i) {
  			vec[i] = nullptr;
  		}
  	}
  	void insert(string word) {
  		Trie *node = this;
  		for (int i = 0; i < word.size(); ++i) {
  			if (node->vec[word[i] - 'a'] != nullptr) {
  				node = node->vec[word[i] - 'a'];
  			} else {
  				node->vec[word[i] - 'a'] = new Trie();
  				node = node->vec[word[i] - 'a'];
  			}
  		}
  		node->is_end = true;
  	}
}