常见数据结构的实现（三）：第一种前缀树
前面两篇文章分别介绍了跳跃表和二叉堆的实现，那么这篇文章将要分析前缀树的实现了。。
常见数据结构的实现（一）：跳跃表
常见数据结构的实现（二）：二叉堆
介绍
前缀树是应用于字符串相关场景的多路树，也叫做字典树。前缀树的原理就是使用同一块内存来存储多个字符串的公共前缀，减少查询时间，提高运行效率。
按照惯例，下面的图是我自己绘制的前缀树：
prefix_tree_1.png
简单说明一下：
- 节点‘#’表示根节点（其实根节点不需要保存字符）
- 对于每个节点，其所有子节点保存的字符都不相同
- 从根节点到任意其他节点的路径上，所有节点的字符拼接起来，就是该节点对应的字符串
- 如果节点保存的元素为红色，则表示其对应的字符串存在，否则不存在。一般地，我们称这些节点为终止节点，否则为非终止节点
分析
按照上面的图，所有节点包含以下属性：
- 保存的字符
- 表示是否为终止节点的变量
- 表示在前缀树中，以该节点对应字符串为前缀的字符串的数目
- 指向所有子节点的引用
这里必须要说明一下，第一种前缀树使用数组保存指向子节点的引用，那么数组大小如何确定呢？数组的大小就是字符集的大小（因为对于每个节点，子节点保存的字符都不相同），我们事先必须指定使用的字符集。假设使用的是26个小写英文字母组成的字符集，因此字符集的首字符是‘a’，大小是26。
那么我们可以如下构建节点类和前缀树类：
//前缀树（字典树）的第一种实现
public class PrefixTree_1 {
private final TreeNode root;
private static final char START = 'a';//字符集的首字符
private static final int SIZE = 26;//字符集的大小
private Stack<TreeNode> stack;//保存查询时遍历的节点
//节点类
private class TreeNode{
public char character;//节点保存的字符
public int count;//以根节点到此节点路径上的字符串为前缀的单词数目
public boolean end;//终止节点为true（表示存在根节点到此节点路径上的字符串），非终止节点为false
public TreeNode[] children;
public TreeNode(char character) {
this.character = character;
this.count = 0;
this.end = false;
this.children = new TreeNode[SIZE];
}
}
public PrefixTree_1() {
this.root = new TreeNode('#');//根节点保存'#'字符，且不是终止节点
this.stack = new Stack<>();
}
}
- stack表示查询操作时保存查询路径上节点的栈，Stack类可以自己实现
这个设计中，每个字符串在前缀树中最多只能保存一个，不存在重复的字符串。
下面介绍查找、添加、删除操作的实现
查找操作
当前缀树中存在指定字符串时，查找操作应该返回true，否则返回false。具体地说，对于字符串中的每个字符，都存在对应的节点，并且最后一个字符对应的节点是终止节点。只要前面两个条件中有一个不满足，也就是说某个字符不存在对应节点或者最后一个字符对应的节点不是终止节点，那么字符串不存在。
下面贴出查找操作的代码：
//查找字符串
//string只包含字符集内的字符，即不为null且不为空串
//stack保存string在前缀树中的最长前缀对应的所有节点
private boolean search(String string) {
stack.clear();
int index;
TreeNode node = root;
//从前向后依次查找string中的字符
for (int i = 0; i < string.length(); i++) {
index = string.charAt(i) - START;//当前字符在字符集中的位置
if (node.children[index] == null)
return false;
node = node.children[index];
stack.push(node);//对应节点入栈
}
return node.end;//终止节点表示存在此字符串，非终止节点表示不存在
}
从中看出，for循环里面的if语句就是判断每个字符对应的节点是否存在，return语句判断最后一个字符对应的节点是否为终止节点。stack保存查询路径上的节点，但是根节点除外，因此stack的大小就是字符串在前缀树中的最长前缀子字符串的长度（在添加操作中需要用到这点）。
添加操作
只有当字符串不存在时，才能执行添加操作。上面分析的两个条件只要有一个不满足，就说明字符串不存在。较为普遍的情况是，字符串中的某些字符不存在对应的节点，那么就需要添加这些节点，并且设置最后的节点为终止节点。而在另一种情况下，只需要执行前面情况下的最后一步操作即可。
//添加字符串
//若字符串已存在，则返回
public void insert(String string) {
if (string == null || string.length() == 0 || search(string))
return;
//字符串不存在，有两种情况
TreeNode node = stack.isEmpty() ? root : stack.peek();//指向最长前缀的最后一个字符，若不存在，则指向root
if (stack.length() != string.length()) {//字符串在前缀树中的最长前缀不是其自身，构造新节点，标记节点，更新计数
int index;
for (int i = stack.length(); i < string.length(); i++) {//从最长前缀的下一个字符开始
index = string.charAt(i) - START;//当前字符在字符集中的位置
node.children[index] = new TreeNode(string.charAt(i));//构造新节点
node = node.children[index];
stack.push(node);//可以看作一边构造新的节点，一边遍历新的节点
}
}
node.end = true;//string最后一个字符对应的节点成为新的终止节点
while (!stack.isEmpty()) {
node = stack.pop();
node.count++;//更新计数
}
root.count++;
return;
}
整个操作可以分为：当字符串不存在时，添加新节点，然后设置终止节点，最后更新所有节点的计数。
删除操作
删除操作执行的条件与添加操作相反，执行过程是从下向上删除不必要的节点。可以肯定的是，删除操作肯定会使字符串最后一个字符对应的节点变成非终止节点。如何判断某个节点是否为不必要的节点？其实很简单，当它没有子节点并且本身不是终止节点时，也就是说前缀树中不存在以该节点对应字符串为前缀的字符串，那么这个节点是可以被删除的。
//删除字符串
//若字符串不存在，则返回
public void delete(String string) {
if (string == null || string.length() == 0 || !search(string))
return;
//字符串存在，标记节点，更新计数，删除不必要的节点
TreeNode node, temp;
stack.peek().end = false;//stack不为空，string最后一个字符对应的节点成为新的非终止节点
while (!stack.isEmpty()) {
node = stack.pop();
node.count--;//更新计数
if (node.count == 0) {//若当前节点不是终止节点且没有子节点（count为0），则删除
temp = stack.isEmpty() ? root : stack.peek();
temp.children[node.character-START] = null;//删除节点
}
}
root.count--;
return;
}
执行逻辑非常简洁，稍微思考下就能理解了。。
后记
第一种前缀树的实现差不多都分析完了，主要的操作就是三种：查找、添加、删除。其他的操作可以基于这三种之上来实现。稍微分析下可以知道：在这种实现中，前缀树的结构与添加、删除元素的顺序无关。
那么作为前缀树的第一种实现，肯定存在其他的实现方式。所以这里提出一个问题，希望大家思考下：这种实现方式有什么缺点？如何解决这些问题？
如果觉得文章某些地方写得不够详细、流畅或者有误的话，那么你可以提出建议。后面我会介绍其他一些常用数据结构的实现，希望大家继续关注哦~~~如果觉得我写的不错的话，那就给这篇文章点个赞吧，谢谢！
欣赏美可以使人愉悦~~
