【字典树】【TRIE】

本质

最多有二十六个节点的树（假设只看小写英文字母）。空间换时间
nex[p]是一个节点，根据c的取值最多有26个分支，nex[p][c]存的是下一个节点

有意思的情况：
为什么Trie的树用数组实现，二叉树用指针实现：

当创建和使用Trie树时，以下是一般的步骤和操作：

• 创建Trie树的节点结构：通常使用一个结构体或类来表示Trie树的节点。这个结构体或类包含一个数组或指针，用于存储子节点的引用或索引，以及其他必要的字段（例如，表示是否是一个字符串的终节点）。
• 插入字符串：要插入一个字符串到Trie树中，需要从根节点开始，逐个字符遍历字符串。对于每个字符，检查是否在当前节点的子节点中存在相应的边。若存在，则移动到对应的子节点；若不存在，则创建一个新的子节点，并移动到该子节点。重复这个过程，直到遍历完整个字符串。最后，将最后一个节点标记为字符串的终节点。
• 搜索字符串：要搜索一个字符串是否在Trie树中存在，同样需要从根节点开始，逐个字符遍历目标字符串。对于每个字符，检查当前节点的子节点是否存在相应的边。若存在，则移动到对应的子节点；若不存在，则说明目标字符串不在Trie树中。如果遍历完目标字符串的所有字符，最后一个节点标记为字符串的终节点，则说明目标字符串存在于Trie树中。
• 删除字符串：要删除一个字符串，可以先执行搜索操作以确保字符串存在于Trie树中。然后，从最后一个节点开始，逐步向上回溯，删除沿途节点和边。如果删除一个节点后，其父节点不再拥有其他子节点且未标记为终节点，则可以进一步删除该父节点。重复这个过程，直到回溯到根节点或遇到一个终节点。
• 应用扩展：Trie树还可以扩展用于其他应用，如前缀匹配、自动补全、字典检索等。这些应用可以基于Trie树的结构和特性进行设计和实现。

如果闲着没事干，可以研究一下压缩Trie

OI Wiki TRIE实现

struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  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];
  }
};

Trie树的应用场景

Trie最典型的应用场景是用于搜索引擎的suggest功能，比如我们在google中，每输入一个英文字母，搜索引擎都会给过我们返回以这个字母为前缀的相关的结果，如下：

Hash和Trie的比较：

作者：Yingjun Wu
链接：https://www.zhihu.com/question/27168319/answer/337652473
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

首先一个问题就是这是静态的数据集还是动态的数据集？也就是说是否用户可以插入新的字符串到这个现有的字符串集合中？如果是静态的数据集，那么用hash吧。数据集大小固定，用perfect hashing或者cuckoohashing可以达到collision概率最小，构建完hash table之后对给定字符串进行查询几乎肯定是一次搞定。然而如果是个动态的数据集，而且新的字符串被不断的插入呢？这个时候用perfect/cuckoo hashing就不合适了。这是因为perfect/cuckoo hashing的一个假设是workload size是提前预知的，在这种假设前提下才能开出足够的空间在设定好hash function的情况下达到collision最小。然而当有大量插入时，perfect/cuckoo hash table的性能就变得不稳定了，因为每次insert都可能需要多次调整内部数据存放的位置。为了降低collision，只能增大hash table，然而resize是perfect/cuckoo hashing最不擅长的，因为必须重新构建hash table，性能非常之差。这时的解决方法是考虑extentiable hashing或者linear hashing。这两种hash table能够很好的动态改变数据结构大小。当然相比于perfect/cuckoo hashing，collision也会相对较多，同时也会带来linear probing的代价。