前缀树
prefix tree, 又叫做 trie。关键Feature如下：
-
树形结构
-
根节点为空
-
结点包含
Node [] nexts;// size 26 int isEnd; //有多少个字符串以当前字符结尾 int pass; // 多少个字符串经过了当前字符 -
常用操作
- insert
- delete
- search //字符串在前缀树中出现的次数
- prefixNumber
一个”word“怎么储存在trie中，自根节点，从上往下阅读。懒得画图了，可去别的博客看看
package data_structure;
/**
* @author yyq
* @create 2023-09-02 11:26
*/
public class Trie {
private Node root=new Node();
public class Node{
Node[] nexts=new Node[26];
int pass=0;//多少条路径经过了此节点
int isEnd=0;//多少条路径以此节点为end
}
public static void main(String[] args) {
Trie t = new Trie();
t.insert("apple");
t.insert("app");
t.insert("bana");
t.insert("b");
t.prefixCount("ap");
t.prefixCount("apple");
t.search("apple");
t.delete("apple");
t.search("apple");
t.prefixCount("ap");
}
public void insert(String word){
System.out.println(word+" inserted");
Node cur = root;
cur.pass++;
for(int i=0;i<word.length();i++){
int chIndex = word.charAt(i)-'a';
if(cur.nexts[chIndex]==null){
cur.nexts[chIndex] = new Node();
}
cur = cur.nexts[chIndex];
cur.pass++;
}
cur.isEnd++;
}
public int search(String word){
Node cur = root;
for(int i=0;i<word.length();i++){
int chIndex = word.charAt(i)-'a';
cur = cur.nexts[chIndex];
if(cur==null){
break;
}
}
int res = cur!=null?cur.isEnd:0;
System.out.println(word + " count: "+ res);
return res;
}
public int prefixCount(String prefix){
Node cur = root;
for(int i=0;i<prefix.length();i++){
int chIndex = prefix.charAt(i) - 'a';
cur = cur.nexts[chIndex];
if(cur==null)break;
}
int res = ( cur==null?0:cur.pass);
System.out.println(prefix+ " count(prefix): "+ res);
return res;
}
public void delete(String word){
if(search(word)>0){
Node cur = root;
cur.pass--;
for(int i=0;i<word.length();i++){
int chIndex = word.charAt(i) - 'a';
cur = cur.nexts[chIndex];
cur.pass--;
}
cur.isEnd--;
System.out.println(word+ " deleted");
}
}
}