数据结构之Trie字典树
什么是Trie字典树
Trie 树，也叫“字典树”或“前缀树”。顾名思义，它是一个树形结构。但与二分搜索树、红黑树等不同的是，Trie 树是一种多叉树，即每个节点可以有 m 个子节点。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
例如，在一个字典中有 个条目，如果使用普通的二分搜索树（不考虑退化），那么在该字典中查询指定条目的时间复杂度是
，如果有100w个条目（
），
大约为20。
而如果使用 Trie 树的话，查询每个条目的时间复杂度，和字典中一共有多少条目无关。时间复杂度为 ，其中
为查询单词的长度，而且绝大多数的单词长度都小于 10。由此可见，使用 Trie 树实现字符串查询，特别是只查询其前缀的情况下，是比普通的树形结构效率要更高的。
那么 Trie 树是如何做到其查询时间复杂度与条目数量无关的呢？这是因为 Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。例如，我们将：how，hi，her，hello，so，see 这6个字符串构造成一颗 Trie 树。那么，最后构造出来的就是下面这个图中的样子：
image.png
其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。
为了更容易理解 Trie 树是怎么构造出来的，我们可以看如下 Trie 树构造的分解过程。构造过程的每一步，都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后，Trie 树就构造好了：
image.png
image.png
当我们在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，那我们将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径：
image.png
之前有提到过， Trie 树是多叉树，那么这个“多叉”是怎么体现的呢？通常来讲，如果你只针对小写字母构造一棵 Trie 树，就像我们上面的例子，那么每个节点中使用一个长度为26的数组来表示其多个子节点即可。如下所示：
class Node {
char data;
Node children[26];
}
而如果我们的需求不仅仅是只包含小写字母，希望这是一棵通用的 Trie 树，那么就需要设计一个能动态变化的子节点容器，使得每个节点有若干指向下个节点的指针。例如，我们可以使用一个 Map 来实现，如下所示：
class Node {
boolean isWord; // 标识是否是单词的结尾
Map<Character, Node> next;
}
Trie字典树基础代码
通过以上的介绍，我们已经了解到了 Trie 树的基本概念。接下来，让我们实现一下 Trie 树的基础功能代码，从代码上对 Trie 树有个直观的认识。具体代码如下：
package tree;
import java.util.Map;
import java.util.TreeMap;
/**
* Trie树
*
* @author 01
* @date 2021-01-28
**/
public class TrieTree {
private final Node root;
private int size;
/**
* Trie树中每个节点的结构
*/
private static class Node {
/**
* 标识是否是单词的结尾
*/
private boolean isWord;
/**
* 使用Map来实现动态存储多个子节点
*/
private final Map<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
public TrieTree() {
root = new Node();
size = 0;
}
/**
* 获取Trie中存储的单词数量
*/
public int getSize() {
return size;
}
/**
* 向Trie中添加一个新的单词word
*/
public void add(String word) {
Node current = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (current.next.get(c) == null) {
// 没有与之对应的子节点，创建一个新的子节点
current.next.put(c, new Node());
}
current = current.next.get(c);
}
if (!current.isWord) {
// 添加的是新的单词，标识该节点是单词的结尾
current.isWord = true;
size++;
}
}
}
Trie字典树的查询
Trie 字典树的查询主要就是查询某个单词是否存在于 Trie 中，其主要逻辑与 add 方法基本上是一样的。代码如下：
/**
* 查询单词word是否在Trie中
*/
public boolean contains(String word){
Node current = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (current.next.get(c) == null) {
return false;
}
current = current.next.get(c);
}
// 只有当最后一个字母所对应的节点标识了是一个单词的结尾，
// 才能认为这个单词存在于Trie中
return current.isWord;
}
Trie字典树的前缀查询
相比于查询某个单词是否存在 Trie 树中，前缀查询的使用范围更广，也是 Trie 树中的主要查询操作。通过前缀查询，我们可以实现像搜索引擎那样的搜索关键词提示功能。实现前缀查询的代码与查询某个单词基本上是一样的，如下所示：
/**
* 查询是否在Trie中有单词以prefix为前缀
*/
public boolean hasPrefix(String prefix) {
Node current = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (current.next.get(c) == null) {
return false;
}
current = current.next.get(c);
}
return true;
}
Trie字典树和简单的模式匹配
接下来，我们尝试使用Trie字典树来解决LeetCode上的一个简单模式匹配的问题，该问题的编号是211：
关于这个问题的详细内容，可以查看以上链接，这里就不做赘述了。对于该问题，具体的实现代码如下：
package tree.trie;
import java.util.Map;
import java.util.TreeMap;
/**
* Leetcode 211. Add and Search Word - Data structure design
* https://leetcode.com/problems/add-and-search-word-data-structure-design/description/
*
* @author 01
*/
public class WordDictionary {
private static class Node {
private boolean isWord;
private final Map<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private final Node root;
/**
* Initialize your data structure here.
*/
public WordDictionary() {
root = new Node();
}
/**
* Adds a word into the data structure.
*/
public void addWord(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
cur.isWord = true;
}
/**
* Returns if the word is in the data structure.
* A word could contain the dot character '.' to represent any one letter.
*/
public boolean search(String word) {
return match(root, word, 0);
}
private boolean match(Node node, String word, int index) {
// 递归到底了，返回该节点是否是一个单词
if (index == word.length()) {
return node.isWord;
}
char c = word.charAt(index);
if (c != '.') {
if (node.next.get(c) == null) {
return false;
}
// 递归继续匹配下一个字母
return match(node.next.get(c), word, index + 1);
} else {
// 包含通配符，需要遍历匹配全部子节点
for (char nextChar : node.next.keySet()) {
if (match(node.next.get(nextChar), word, index + 1)) {
return true;
}
}
return false;
}
}
}
Trie字典树和字符串映射
最后，我们再来解决一个LeetCode上的677号问题，该问题的链接如下：
对于该问题我们就是要将Trie字典树作为一个映射，每个单词就是一个 key，对应着一个 value，该 value 只存在于单词最后一个字母对应的节点。如下图所示：
image.png
有了这个形象的概念后，代码编写起来就简单了，所以也建议各位实现算法和数据结构时可以尝试多画图。对于该问题的具体实现代码如下：
package tree.trie;
import java.util.Map;
import java.util.TreeMap;
/**
* 键值映射
* https://leetcode-cn.com/problems/map-sum-pairs/
*
* @author 01
*/
public class MapSum {
private static class Node {
private int value;
private final Map<Character, Node> next;
public Node(int value) {
this.value = value;
next = new TreeMap<>();
}
public Node() {
this(0);
}
}
private final Node root;
/**
* Initialize your data structure here.
*/
public MapSum() {
root = new Node();
}
public void insert(String key, int val) {
Node cur = root;
for (int i = 0; i < key.length(); i++) {
char c = key.charAt(i);
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
cur.value = val;
}
public int sum(String prefix) {
Node cur = root;
// 找到这个前缀最后一个字母所对应的节点
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null) {
return 0;
}
cur = cur.next.get(c);
}
// 对该节点所有路径下的子节点的value进行求和
return sum(cur);
}
private int sum(Node node) {
int res = node.value;
// 遍历所有子节点
for (char c : node.next.keySet()) {
// 对每个子节点路径上的value进行递归求和
res += sum(node.next.get(c));
}
return res;
}
}
