34Trie树：如何实现搜索引擎的搜索关键词提示功能

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

我们经常使用搜索引擎的搜索关键词提示功能，如下图所示：

那么它底层使用的是什么数据结构呢？具体是怎么实现的呢？

什么是“Trie 树”？

Trie 树，也叫“字典树”。它是一个树形结构，一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

当然，这样的问题有很多中解决方法，比如散列表、红黑树、一些字符串匹配算法。但是Trie 树解决这个问题时有着独特的优势。并且 Trie树能解决的问题不限于此。下面我们看看 Trie 树究竟长上面样子？

假设有how，hi，her，hello，so，see这6个字符串，希望在里面多次查找某个字符串是否存在。但若每次查找，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那效率就比较低，有没有高效的方法呢？

这时可以先对这6个字符串做预处理，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。如下图所示：

其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。

当需要在 Trie 树中查找一个字符串时，比如查找字符串“her”，将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。如下面的绿色路径就是 Trie 树中匹配的路径。

假如要查找的字符串是“he“呢？从根节点开始匹配，下面绿色的路径是字符串”he“匹配的路径。但是路径的最后一个节点”e“并不是红色的。也就是说，”he“是某个字符串的前缀子串，并不能完全匹配任何字符串。

如何实现一棵 Trie 树？

Trie 树主要有两个操作，一个是将字符串集合构造成 Trie 树。也就是将字符串插入到 Trie 树的过程。另一个是在 Trie 树中查询一个字符串。

那么如何存储一个Trie 树？Trie 树是一个多叉树。最经典的存储方式是借助散列表的思想，通过一个下标与字符一一映射的数组，来存储子节点的指针。如下图所示：

假设字符串中只有从 a 到 z 这26个小写字母，在数组中下标为 0 的位置，存储指向子节点 a 的指针，下标为 1 的位置存储指向子节点 b 的指针，以此类推，下标为 25 的位置，存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在，就在对应的下标的位置存储 null。

class TrieNode {
  char data;
  TrieNode children[26];
}

当我们在 Trie 树中查找字符串时，可以通过字符的 ASCII 码减去 ”a“ 的ASCII码，迅速找到匹配的子节点的指针。比如，d 的 ASCII 码减去 a 的 ASCII 码就是 3，那子节点 d 的指针就存储在数组中下标为 3 的位置中。

对应的代码如下：

public class Trie {
  private TrieNode root = new TrieNode('/'); // 存储无意义字符

  // 往Trie树中插入一个字符串
  public void insert(char[] text) {
    TrieNode p = root;
    for (int i = 0; i < text.length; ++i) {
      int index = text[i] - 'a';
      if (p.children[index] == null) {
        TrieNode newNode = new TrieNode(text[i]);
        p.children[index] = newNode;
      }
      p = p.children[index];
    }
    p.isEndingChar = true;
  }

  // 在Trie树中查找一个字符串
  public boolean find(char[] pattern) {
    TrieNode p = root;
    for (int i = 0; i < pattern.length; ++i) {
      int index = pattern[i] - 'a';
      if (p.children[index] == null) {
        return false; // 不存在pattern
      }
      p = p.children[index];
    }
    if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
    else return true; // 找到pattern
  }

  public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
    public boolean isEndingChar = false;
    public TrieNode(char data) {
      this.data = data;
    }
  }
}

那么在Trie 树中，查找某个字符串的时间复杂度是多少？构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 $O(n)$（n表示所有字符串的长度和）。假设要查询的字符串长度是 k，那只需要比对大约 k个节点，就能完成查询操作。也就是说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 $O(k)$，k 表示要查找的字符串的长度。所以Trie 树适合那种频繁地查询某些字符串。

Trie 树真的很耗内存吗？

由 Trie树的实现和时间复杂度分析，可以知道 Trie树是独特的、高效的字符串匹配算法。但是对于 Trie树，经常有人说它非常耗内存，是一种空间换时间的思路。

刚才我们说Trie存储的时候，采用的是数组存储一个节点的子节点的指针。如果字符串中包含从 a 到 z这26个字符，那每个节点都要存储一个长度为26的数组，数组中的每个元素存储一个8字节指针。而且，即便一个节点只有很少的子节点，远小于26个，也要维护一个长度为26的数组。

之前说过，Trie 树的本质是避免重复存储一组字符串的相同前缀子串，但是现在每个字符（对应一个节点）的存储远远大于 1 个字节。并且如果字符串中不仅包含小写字母，好包含大写字母、数组、甚至是中文，那需要的存储空间就更多了。在重复的前缀并不多的情况下，Trie 树不但不能节省内存，还有可能会浪费更多的内存。

Trie 树尽管有可能很浪费内存，但是确实非常高效。那能够解决内存问题么？可以将每个节点中的数组换成其他数据结构，如有序数组、跳表、散列表、红黑树等，来存储一个节点的子节点指针。这样会稍微牺牲一点查询的效率。

假设用有序数组，数组中的指针按照所指向的字节点中的字符大小顺序排列。查询时，可以通过二分查找的方法，快速查找到某个字符应该匹配的子节点的指针。但是向 Trie 树中插入一个字符串时，为了维护数组中数据的有序性，就会稍微慢了点。

实际上，Trie 树的变体很多，都可以在一定程度上解决内存消耗的问题。比如缩点优化，就是对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并。这样可以节省空间，但却增加了编码难度。

Trie 树与散列表、红黑树的比较

实际上，字符串的匹配问题，就是数据的查找问题。前面讲的支持动态数据高效操作的数据结构，如散列表、红黑树、跳表等，都可以实现在一组字符串中查找字符串的功能。这里说下散列表和红黑树两种数据结构，跟Trie的比较，看看它们各自的优缺点和应用场景。

在一组字符串中查找字符串，Trie树实际上表现的并不好。它对要处理的字符串有及其苛刻的要求。

字符串中包含的字符集不能太大。若太大，则浪费很多存储空间。即便可以优化，但也要付出牺牲查询、插入效率的代价。
要求字符串的前缀重合比较多，不然空间消耗会变大很多。
若要用Trie树解决问题，工程上需要自己从零开始实现一个 Trie树，还要保证没bug。这在工程上是将简单问题复杂化。
用指针串起来的数据块是不连续的，而Trie树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

所以，针对一组字符串中查找字符串的问题，工程上常用红黑树或者散列表来实现，可以直接相应的库即可。

实际上，Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie 树比较适合的是查找前缀匹配的字符串，也就是类似开篇问题的那种场景。

解答开篇

如何利用 Trie 树，实现搜索关键词的提示功能？

我们将由用户的热门搜索关键词组成的关键词库构建成一个 Trie 树。当用户输入其中某个单词时，把这个词作为一个前缀子串在 Trie 树中匹配。例如，假设词库里只有 hello、her、hi、how、so、see 这 6 个关键词。当用户输入了字母 h 的时候，我们就把以 h 为前缀的 hello、her、hi、how 展示在搜索提示框内。当用户继续键入字母 e 的时候，我们就把以 he 为前缀的 hello、her 展示在搜索提示框内。这就是搜索关键词提示的最基本的算法原理。

当然，这是最基本的实现原理，并且搜索引擎的搜索关键词提示功能也比较复杂。

实际上，Trie 树的这个应用可以扩展到更加广泛的一个应用上，就是自动输入补全，比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。

内容小结

Trie 树是一种解决字符串快速匹配问题的数据结构。如果用来构建 Trie 树的这一组字符串中，前缀重复的情况不是很多，那 Trie 树这种数据结构总体上来讲是比较费内存的，是一种空间换时间的解决问题思路。

尽管比较耗费内存，但是对内存不敏感或者内存消耗在接受范围内的情况下，在 Trie 树中做字符串匹配还是非常高效的，时间复杂度是 O(k)，k 表示要匹配的字符串的长度。

但是，Trie 树的优势并不在于，用它来做动态集合数据的查找，因为，这个工作完全可以用更加合适的散列表或者红黑树来替代。Trie 树最有优势的是查找前缀匹配的字符串，比如搜索引擎中的关键词提示功能这个场景，就比较适合用它来解决，也是 Trie 树比较经典的应用场景。