目录
前缀树：把一个“最小”单位的数据看成一个节点到另一个节点的路径，每个节点有两个属性，一个是所有数据经过这个节点的次数pass，一个是这个节点作为结束位置的次数end。
例如，一个数组["abc","abd","ab","kst"]，看它怎么用前缀树表示：
（1）首先有一个节点，指向null
（2）看"abc"，怎么生成前缀树
a.首先是a，第一个节点没有a路径，先生成a路径，到下一个节点，经过了第一个节点，所以第一个节点的p++，但是第一个节点不是终止位置，所以e仍=0；
而a路径指向的那个节点，因为也到达了它，所以它的p++，它也不是终止，因为它还要往后生成b路径，所以它的e=0
b.然后是b，
c.然后是c，c是"abc"的终止，所以e=1
（3）"abd" "ab"如下：
比如有一个字符串数组，里面所有的数据都是26个字母组成的值，那么这个数组可以用纯暴力或者前缀树实现。
先有一个节点类，这个类有三个属性，一个是pass，一个是end，还有一个是指针，即指向下一个几点的指针，因为有26个字符，所以一个节点可以往外有26个指针：
public class Node{
private int pass;
private int end;
private Node[] next;
public Node(){
pass = 0;
end = 0;
next = new Node[26]; //每个节点都有26个长度，26个路径，它的下一个路径可以是26中任意一个
}
}然后再生成前缀树，提供插入数据、删除、查找、查找前缀多少方法：
public class Tire{
private Node root;
public Tire(){
root = new Node();
}
//加入数据，比如往字符串数据中加入一个串“hji”
public void insert(String str){
if(str == null){
return;
}
char[] chars = str.toCharArray();
Node node = root;
node.pass++;
for(int i=0;i<chars.length;i++){
//当前节点是否有这个char的路径，比如节点是不是有h这个路径
int path = chars[i] - 'a'; //i代表表的字符，比如h到a的ascii
if(node.next[path] == null){
node.next[path] = new Node();
}
node = node.next[path];
node.pass++;
}
node.end++;
}
//查找数据加了几次
public int search(String str){
if(str == null){
return 0;
}
Node node = root;
int path = 0;
char[] chars = str.toCharArray();
for (int i=0;i<chars.length;i++){
path = chars[i] - 'a';
if(node.next[path] != null){
node = node.next[path];
}else{
return 0;
}
}
return node.end;
}
//删除数据
public void delete(String str){
if(search(str) == 0){
return;
}
Node node = root;
node.pass--;
int path = 0;
char[] chars = str.toCharArray();
for(int i=0;i<chars.length;i++){
path = chars[i] - 'a';
if(--node.next[path].pass == 0){
node.next[path] = null;
return;
}
node = node.next[path];
}
node.end--;
}
//加入的字符串中，多少是以str做前缀的
public int preNum(String pre){
if(pre == null){
return 0;
}
Node node = root;
char[] chars = pre.toCharArray();
int path = 0;
for (int i=0;i<chars.length;i++){
path = chars[i] - 'a';
if(node.next[path] == null){
return 0 ;
}
node = node.next[path];
}
return node.pass;
}
}方式一只限制26个字符，如果字符出现“12fddg”这种就不够用了，所以可以改善一下节点类，使指向下个节点的指针个数不受“只能有26个”这个限制：
public class Node{
private int pass;
private int end;
private HashMap<Character,Node> hashMap;
public Node(){
pass = 0;
end = 0;
hashMap = new HashMap<>();
}
}那么前缀树相应改变，其实同方式一实现一样：
public class TireTree{
private Node root;
public TireTree(){
root = new Node();
}
//插入
public void insert(String str){
if(StringUtils.isBlank(str)){
return;
}
Node node = root;
char[] chars = str.toCharArray();
for(int i=0;i<chars.length;i++){
if(node.hashMap.get(chars[i]) == null){
node.hashMap.put(chars[i],new Node());
}
node = node.hashMap.get(chars[i]);
node.pass++;
}
node.end++;
}
//查找存在几个
public int search(String str){
if(str == null){
return 0;
}
char[] chars = str.toCharArray();
Node node = root;
for(int i=0;i<chars.length;i++){
if(node == null){
return 0;
}
node = node.hashMap.get(chars[i]);
}
return node.pass;
}
//删除
public void delete(String str){
if(search(str) == 0){
return;
}
char[] chars = str.toCharArray();
Node node = root;
node.pass--;
for(int i=0;i<chars.length;i++){
if(--node.pass == 0){
node.hashMap.put(chars[i],null);
return;
}
node = node.hashMap.get(chars[i]);
}
node.end--;
}
//多少字符串以pre为前缀
public int preNum(String pre){
if(pre == null){
return 0;
}
Node node = root;
char[] chars = pre.toCharArray();
for(int i=0;i<chars.length;i++){
if(node.hashMap.get(chars[i]) == null){
return 0;
}
node = node.hashMap.get(chars[i]);
}
return node.pass;
}
}时间复杂度：
可以发现，不论是增删查哪个方法，都只和插入字符多少有关。比如插入，从树来看，就是走了str字符个数的路程。查找前缀是一样的，走了pre字符个数的路程。
我们可以用数组实现：
public class Violence{
private ArrayList arrayList;
public Violence(){
arrayList = new ArrayList();
}
public void insert(String str){
if(str == null){
return;
}
arrayList.add(str);
}
public int search(String str){
if(str == null){
return 0;
}
int num = 0;
for (int i=0;i<arrayList.size();i++){
if(arrayList.get(i) == str){
num++;
}
}
return num;
}
public void delete(String str){
if(search(str) == 0){
return;
}
arrayList.remove(str);
}
public int preNum(String str){
if(str == null){
return 0;
}
int num = 0;
for(int i=0;i<arrayList.size();i++){
if(((String)arrayList.get(i)).indexOf(str) == 0){
num++;
}
}
return num;
}
}时间复杂度：虽然ArrayList的add方法或者remove方法，时间复杂度分别是O(1)和O(N)，但是对于查找前缀方法，需要循环整个array数组，查找是否是pre开头，不如前缀树方法时间复杂度好。