10. 前缀树（trie）
8.1 前缀树概念
1. 前缀树概念
1）单个字符串中，字符从前到后的加到一棵多叉树上
2）字符放在路上，节点上有专属的数据项
数据项pass：有多少路径经过了这个点
数据项end：有多少路径是以这个点结尾
3）所有样本都这样添加，如果没有路就新建，如有路就复用
4）沿途节点的pass值增加1，每个字符串结束时来到的节点end值增加1
2. 前缀树使用范围
求在一个字符数组中，某一个字符串出现的次数（查看数中有没有这一分支，如果有是否end不为0）
求在一个字符数组中，包含某一个字符串出现的次数（查看数中有没有这一分支，如果有是否pass不为0）
8.2 前缀树
1. 题目
建立前缀树，并且完成增删字符串的功能
2. 思路
- 每个节点至少有三部分组成，pass，end，Nodes，需要注意，对于长度为n的字符串，节点要有n+1个。
数据项pass：有多少路径经过了这个点
数据项end：有多少路径是以这个点结尾
节点项next：存放26个节点，每个位置代表一个字母new Node[26];
- 添加
给所有路径上的节点加1，如果没有的话，就建立个新的节点加进去。最后一位end+1。
- 查找
查找路径，直到节点为空或者找到的位置end为0或者找到的位置end大于0（完成）
- 查找部分
查找部分路径，如果pass > 0，找到。
- 删除
删除路径，找到某个pass为0的地方，删除。或者如果找到最后end大于0，end--。
3. 代码
节点：
class Node {
int pass;
int end;
Node[] nexts;
public Node(){
this.pass = 0;
this.end = 0;
nexts = new Node[26];
}
}
TrieTree初始化：
private Node root;
public TrieTree(){
root = new Node();
}
插入：
public void insert(String word){
if(word == null){
return;
}
char[] str = word.toCharArray();
Node cur = root;
// 从上往下遍历，有就加，没有就新建
for (int i = 0; i < str.length; i++) {
cur.pass++;
// System.out.println(cur.pass+" "+ str[i]+" "+cur.end);
int curIndex = str[i]-'a';
if(cur.nexts[curIndex] == null){
cur.nexts[curIndex] = new Node();
}
cur = cur.nexts[curIndex];
}
cur.pass++;
cur.end++;
}
查询：
// 查看这个单词出现了几次
public int search(String word){
if(word == null){
return 0;
}
char[] str = word.toCharArray();
Node cur = root;
// 从上往下遍历，有就加，没有就新建
for (int i = 0; i < str.length; i++) {
int curIndex = str[i]-'a';
if(cur.nexts[curIndex] == null){
return 0;
}
cur = cur.nexts[curIndex];
}
return cur.end;
}
查询前缀：
// 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
public int prefixNumber(String word){
if(word == null){
return 0;
}
char[] str = word.toCharArray();
Node cur = root;
// 从上往下遍历，有就加，没有就新建
for (int i = 0; i < str.length; i++) {
int curIndex = str[i]-'a';
if(cur.nexts[curIndex] == null){
return 0;
}
cur = cur.nexts[curIndex];
}
return cur.pass;
}
删除：
// 删除某个字符串
public void delete(String word){
// 如果删除的字符存在
if(search(word) != 0){
char[] str = word.toCharArray();
Node cur = root;
// 从上往下遍历，
for (int i = 0; i < str.length; i++) {
cur.pass--;
int curIndex = str[i]-'a';
if(cur.nexts[curIndex].pass == 1){
cur.nexts[curIndex] = null;
return;
}
cur = cur.nexts[curIndex];
}
cur.pass--;
cur.end--;
}
}