TrieTree(字典树)

简介

Trie Tree,前缀树或字典树，是一种有序树，用于保存关联数组。

其中的键通常是字符串。

与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。Trie 树的名称来源于搜索引擎中的专有名词的 retrieval

应用场景

• 搜索引擎的 suggest 功能;

比如包含 6 个单词的 Trie 树：

1
2
3
4
5
6

- `("abc")`
- `("xy")`
- `("xyz")`
- `("abb")`
- `("xyzb"),`
- `("word")`

Trie 树有两种实现策略，

• 第一种使用数组;
• 第二种是使用 Map，
• 使用数组的方式需要对存储的字符和数组的 index 之间要有明确的映射规则，这样便于查询，比如如果想做中文的 suggest

参考

1. 深入理解 Trie 树