漫画：什么是前缀树（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
}
}