Trie树

Trie树，也叫“字典树”。

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

Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

根节点不包含任何信息，每个节点表示一个字符串中的字符，从根节点到子树中任意节点的一条路径表示一个字符串。

实现一颗Trie树

• 两个操作：

  • 将字符串集合构造成Trie树。

  • 在Trie树中查询一个字符串。

• 存储Trie树：

  Trie树是一个多叉树，可以使用数组、有序数组、散列表、跳表和红黑树等存储当前节点的子节点。

性能分析：

• 构造Trie树的时间复杂度为：O(n)，n表示所有字符串长度和。

• 查找字符串的时间复杂度是O(K)，K表示要查找的字符串的长度。

• Trie树内存消耗比较大。

• 可以使用缩点优化对Trie树的内存消耗进行优化。对只有一个子节点的节点，如果这个节点不是一个串的结束节点，可以将此节点与子节点合并。

局限性

• 字符串中包含的字符集不能太大，如果字符集太大，存储空间可能会浪费很多。即使可以优化，也要牺牲查询、插入的效率。

• 字符串前缀重合要比较多。

• 重新构造一个Tree树比较复杂，难以保证没有Bug。

• 用到了指针，对缓存不友好。

使用场景

• 搜索关键词提示