# Trie树

`Trie`树，也叫“字典树”。

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

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

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

## 实现一颗`Trie`树

* 两个操作：
  * 将字符串集合构造成`Trie`树。
  * 在`Trie`树中查询一个字符串。
* 存储`Trie`树：

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

## 性能分析：

* 构造`Trie`树的时间复杂度为：`O(n)`，n表示所有字符串长度和。
* 查找字符串的时间复杂度是`O(K)`，`K`表示要查找的字符串的长度。
* `Trie`树内存消耗比较大。
* 可以使用缩点优化对`Trie`树的内存消耗进行优化。对只有一个子节点的节点，如果这个节点不是一个串的结束节点，可以将此节点与子节点合并。

## 局限性

* 字符串中包含的字符集不能太大，如果字符集太大，存储空间可能会浪费很多。即使可以优化，也要牺牲查询、插入的效率。
* 字符串前缀重合要比较多。
* 重新构造一个`Tree`树比较复杂，难以保证没有`Bug`。
* 用到了指针，对缓存不友好。

## 使用场景

* 搜索关键词提示
