一、前缀树定义
1）单个字符串中，字符从前到后的加到一棵多叉树上
2）字符放在边上，节点上有专属的数据项（常见的是 pass 和 end 值）
3）样本增加形式，每个字符串都从根节点开始加，如果没有路就新建，如果有路就复用
4）增加时，沿途节点的 pass 值加 1，每个字符串完结时来到的节点 end 值加 1
作用：能够更加不便的实现前缀相干的查问
二、简版的前缀树
只能寄存 26 个小写字母组成的字符串
/**
* 字符品种：只有 26 个小写字母
*
* @author Java 和算法学习：周一
*/
public static class Node1 {
// 以后节点被通过了几次
private int pass;
// 有多少个字符串以以后节点结尾
private int end;
// 以后节点所有的子节点
private Node1[] nexts;
// 节点只寄存 26 个小写字母
public Node1() {
pass = 0;
end = 0;
// node[i] == null，节点不存在
nexts = new Node1[26];
}
}
public static class Trie1 {
private Node1 root;
public Trie1() {root = new Node1();
}
/**
* 向前缀树中增加一个字符串
*/
public void insert(String word) {if (word == null) {return;}
// 正在增加字符的节点
Node1 node = root;
// 曾经有字符通过该节点，批改节点 pass 值
node.pass++;
int path = 0;
// 以后单词挨个字符的增加到前缀树上
char[] chars = word.toCharArray();
for (char aChar : chars) {
// 以后字符应该走的门路
path = aChar - 'a';
// 以后节点的 path 门路对应节点不存在，则新建
if (node.nexts[path] == null) {node.nexts[path] = new Node1();}
// 以后节点的 path 门路对应节点必定曾经存在了
// 所以以后节点来到 path 门路对应节点
node = node.nexts[path];
// 曾经有字符达到该节点，批改 pass 值
node.pass++;
}
// 字符增加结束，批改最初节点的 end 值
node.end++;
}
/**
* word 单词之前加过多少次
*/
public int search(String word) {if (word == null) {return 0;}
int index = 0;
char[] chars = word.toCharArray();
// 从根节点开始找
Node1 node = root;
for (char aChar : chars) {
// 以后字符应该走的门路
index = aChar - 'a';
// 以后节点的 index 门路对应节点不存在，间接返回
if (node.nexts[index] == null) {return 0;}
// 以后节点的 index 门路对应节点存在，则以后查找节点来到 index 门路对应节点
node = node.nexts[index];
}
// 最初以后节点的 end 值即是此单词加过的次数
return node.end;
}
/**
* 所有曾经退出的字符串中，有多少是以 pre 为前缀的
*/
public int prefixNumber(String pre) {if (pre == null) {return 0;}
int index = 0;
// 从根节点开始找
Node1 node = root;
// 挨个字符找
char[] chars = pre.toCharArray();
for (char aChar : chars) {
// 以后字符应该走的门路
index = aChar - 'a';
// 以后节点的 index 门路对应节点不存在，间接返回
if (node.nexts[index] == null) {return 0;}
// 以后节点的 index 门路对应节点存在，则以后查找节点来到 index 门路对应节点
node = node.nexts[index];
}
// 最初以后查找节点所处节点的 pass 值即是以 pre 为前缀的数量
return node.pass;
}
/**
* 在前缀树中删除某个字符串
*/
public void delete(String word) {
// 字符串存在才执行删除逻辑
if (search(word) != 0) {
// 从根节点开始
Node1 node = root;
// 批改根节点 pass 值
node.pass--;
int index = 0;
char[] chars = word.toCharArray();
for (char aChar : chars) {
// 以后字符应该走的门路
index = aChar - 'a';
// 以后节点 index 门路对应节点的 pass 值减一
if (--node.nexts[index].pass == 0) {
// 减一后如果为 0，表明没有字符串再通过此节点
// 将此节点 index 门路对应节点置空，帮忙 GC
node.nexts[index] = null;
return;
}
// 减一后不为 0，表明还有字符串通过此节点
// 则以后节点挪动到 index 门路对应的节点
node = node.nexts[index];
}
// 最初批改节点所在位置 end 值
node.end--;
}
}
}
三、通用的前缀树
不限定寄存的内容
/**
* 字符品种：不肯定只有 26 个小写字母
*
* @author Java 和算法学习：周一
*/
public static class Node2 {
// 以后节点被通过了几次
private int pass;
// 有多少个字符串以以后节点结尾
private int end;
// 以后节点所有的子节点，Key 为节点对应字符串字符转换为整型后的 ASCII 码值
private HashMap<Integer, Node2> nexts;
public Node2() {
pass = 0;
end = 0;
nexts = new HashMap<>();}
}
public static class Trie2 {
private Node2 root;
public Trie2() {root = new Node2();
}
/**
* 向前缀树中增加一个字符串，此字符串不肯定全是小写字母
*/
public void insert(String str) {if (str == null) {return;}
// 正在增加字符串的节点
Node2 node = root;
// 曾经有字符通过该节点，批改节点 pass 值
node.pass++;
int index = 0;
// 以后字符串挨个字符的增加到前缀树上
char[] chars = str.toCharArray();
for (char aChar : chars) {
index = aChar;
// 以后节点的 index 门路对应节点不存在，则新建
if (!node.nexts.containsKey(index)) {node.nexts.put(index, new Node2());
}
// 以后节点的 index 门路对应节点曾经存在了
// 所以以后节点来到 index 门路对应节点
node = node.nexts.get(index);
// 曾经有字符达到该节点，批改 pass 值
node.pass++;
}
// 字符串增加结束，批改最初节点的 end 值
node.end++;
}
/**
* 字符串之前加过多少次
*/
public int search(String str) {if (str == null) {return 0;}
int index = 0;
char[] chars = str.toCharArray();
// 从根节点开始找
Node2 node = root;
for (char aChar : chars) {
// 以后字符应该走的门路
index = aChar;
// 以后节点的 index 门路对应节点不存在，间接返回
if (!node.nexts.containsKey(index)) {return 0;}
// 以后节点的 index 门路对应节点存在，则以后查找节点来到 index 门路对应节点
node = node.nexts.get(index);
}
// 最初以后节点的 end 值即是此字符串加过的次数
return node.end;
}
/**
* 所有曾经退出的字符串中，有多少是以 pre 为前缀的
*/
public int prefixNumber(String pre) {if (pre == null) {return 0;}
int index = 0;
// 从根节点开始找
Node2 node = root;
// 挨个字符找
char[] chars = pre.toCharArray();
for (char aChar : chars) {
// 以后字符应该走的门路
index = aChar;
// 以后节点的 index 门路对应节点不存在，间接返回
if (!node.nexts.containsKey(index)) {return 0;}
// 以后节点的 index 门路对应节点存在，则以后查找节点来到 index 门路对应节点
node = node.nexts.get(index);
}
// 最初以后节点的 pass 值即是以 pre 为前缀的数量
return node.pass;
}
/**
* 在前缀树中删除某个字符串
*/
public void delete(String str) {
// 字符串存在才执行删除逻辑
if (search(str) != 0) {
// 从根节点开始
Node2 node = root;
// 批改根节点 pass 值
node.pass--;
int index = 0;
char[] chars = str.toCharArray();
for (char aChar : chars) {
// 以后字符应该走的门路
index = aChar;
// 以后节点 index 门路对应节点的 pass 值减一
if (--node.nexts.get(index).pass == 0) {
// 减一后如果为 0，表明没有字符串再通过此节点
// 将此节点 index 门路对应节点置空
node.nexts.remove(index);
return;
}
// 减一后不为 0，表明还有字符串通过此节点
// 则以后节点挪动到 index 门路对应的节点
node = node.nexts.get(index);
}
// 最初批改节点所在位置 end 值
node.end--;
}
}
}
以上两种前缀树都只实现了最根本的性能，当理论我的项目中遇到相似的需要，能够在此基础上增加须要的性能即可，相当于提供了一个模板。
本文所有代码 Github 获取