漫画：什么是前缀树（Trie树）？

————— 第二天 —————

如上图所示，我们在百度输入框输入ap两个字母，下拉菜单就会自动列举出包含该前缀的所有单词，比如api、app、apple等等。

小灰的想法，是要建立一个很大的哈希表，哈希表中的key，是所有单词包含的前缀。

举个例子，有两个单词app和apple，它们的前缀包括a、ap、app、appl、apple，把这些前缀都作为key存储到哈希表中，每一个key对应的value，就是具有这个前缀的单词：

比如app和apple都具有前缀a，那么a所对应的value就是app，apple；再比如appl是apple的前缀，那么appl这个key对应的value就是apple。

————————————

我们利用apple，app，api，banana，bus这5个单词来举例子，构建出一颗前缀树，这颗前缀树就像下图这样：

在这棵树中，每一个节点最多可以拥有26个孩子节点，对应着从a到z这26个英文字母。

在我们给的例子中，apple，app，api这三个单词是字母a开头，banana，bus这两个单词是字母b开头，所以根节点拥有两个孩子，分别对应着以字母a开头的单词和以字母b开头的单词。

apple，app，api这三个单词，第二个字母都是p，所以a孩子节点只拥有一个孩子节点，对应着第二个字母是p的单词。

banana，bus这两个单词，第二个字母分别是a和u，所以b孩子节点拥有两个孩子节点，分别对应着第二个字母是a的单词（banana），以及第二个字母是u的单词（bus）。

以此类推，所有单词的所有字母，共同构成了这个前缀树的所有节点。

假如我们输入查询关键字“ap”，进行前缀查询，前缀树将会如何工作呢？

首先，前缀树会根据关键字中的第一个字母“a”，检查根节点是否有a对应的孩子节点，发现存在该孩子节点：

接下来，根据关键字中的第二个字母“p”，检查a孩子节点是否拥有对应字母p的孩子节点，发现存在该孩子节点：

这样一来，前缀树就判断出当前字典中存在以“ap”为前缀的单词。

假如我们输入查询关键字“bus”，进行精确查询，前缀树将会如何工作呢？

首先，前缀树会根据关键字中的第一个字母“b”，检查根节点是否有b对应的孩子节点，发现存在该孩子节点：

接下来，根据关键字中的第二个字母“u”，检查b孩子节点是否拥有对应字母u的孩子节点，发现存在该孩子节点：

左后，根据关键字中的第三个字母“s”，检查u孩子节点是否拥有对应字母s的孩子节点，发现存在该孩子节点，并且该节点的结束标志位为真：

这样一来，前缀树就判断出当前字典中存在精确匹配“bus”的单词。

假如我们要插入一个新单词“buy”，前缀树如何工作呢？

首先，前缀树会根据关键字中的第一个字母“b”，检查根节点是否有b对应的孩子节点，发现存在该孩子节点：

接下来，根据关键字中的第二个字母“u”，检查b孩子节点是否拥有对应字母u的孩子节点，发现存在该孩子节点：

然后，根据关键字中的第三个字母“y”，检查u孩子节点是否拥有对应字母y的孩子节点，发现并没有这个孩子节点：

最后，创建字母y对应的新孩子节点。由于字母y是单词buy当中的最后一个字母，所以该节点的结束标志位置为“真”：

这样一来，前缀树成功插入了“buy”这个新单词。

class TrieNode { // 存储当前节点的子节点 private TrieNode[] children; // 标记该节点是否是一个单词的结束 private boolean isEndOfWord; public TrieNode() { // 初始化子节点数组，通常为26个字母 children = new TrieNode[26]; isEndOfWord = false; } // 添加一个单词到Trie树中 public void insert(String word) { TrieNode current = this; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; if (current.children[index] == null) { current.children[index] = new TrieNode(); } current = current.children[index]; } current.isEndOfWord = true; } // 从Trie树删除一个单词 public boolean delete(String word) { return delete(this, word, 0); } private boolean delete(TrieNode current, String word, int index) { if (index == word.length()) { if (!current.isEndOfWord) { return false; // 单词不存在于树中 } current.isEndOfWord = false; return canDelete(current); // 返回是否可以删除该节点 } char ch = word.charAt(index); int childIndex = ch - 'a'; TrieNode child = current.children[childIndex]; if (child == null) { return false; // 单词不存在于树中 } boolean canDeleteChild = delete(child, word, index + 1); if (canDeleteChild) { current.children[childIndex] = null; return canDelete(current); } return false; } // 判断节点是否能被删除 private boolean canDelete(TrieNode node) { if(node.isEndOfWord){ return false; } for (TrieNode child : node.children) { if (child != null) { return false; } } return true; } // 检查一个单词是否存在于Trie树中 public boolean search(String word) { TrieNode current = this; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; if (current.children[index] == null) { return false; } current = current.children[index]; } return current.isEndOfWord; } // 检查是否有以给定前缀开头的单词存在 public boolean startsWith(String prefix) { TrieNode current = this; for (int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); int index = ch - 'a'; if (current.children[index] == null) { return false; } current = current.children[index]; } return true; } } public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // 插入一个单词到Trie树中 public void insert(String word) { root.insert(word); } // 从Trie树删除一个单词 public boolean delete(String word) { return root.delete(word); } // 检查一个单词是否存在于Trie树中 public boolean search(String word) { return root.search(word); } // 检查是否有以给定前缀开头的单词存在 public boolean startsWith(String prefix) { return root.startsWith(prefix); } public static void main(String[] args) { Trie trie = new Trie(); trie.insert("apple"); System.out.println(trie.search("apple")); // 输出 true System.out.println(trie.search("app")); // 输出 false System.out.println(trie.startsWith("app")); // 输出 true trie.insert("app"); System.out.println(trie.search("app")); // 输出 true trie.delete("apple"); System.out.println(trie.search("apple")); // 输出 false } }

在该代码中，TrieNode为前缀树的节点类，Trie类负责前缀树的整体操作。

至于前缀树的删除操作，比插入和查找操作要复杂一些，涉及到递归，大家可以阅读代码中的delete方法进行理解。