前缀树（Trie）的java实现

前缀树

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");
        }

    }
}