前缀树

概念

​ Trie 树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。Trie 的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

基本性质

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

实现代码

//前缀树节点结构
public class TrieNode{
    public int pass;//这个节点经过了多少次
    public int end;//以这个节点结尾的字符串个数
    //这个节点后面紧跟着的节点所组成的数组，nexts[0]位置表示‘a’字符，nexts[25]位置为‘z’字符
    public TrieNode[] nexts;
    public TrieNode(){
        //初始pass和end都为0
        pass = 0;
        end = 0;
        //先腾出26个位置
        nexts = new TrieNode[26];
    }
}
//前缀树结构及其操作
public class Trie{
    //初始化树的根节点
    private TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    
    //添加字符串
    public void insert(String word){
        if(word == null){
            return;
        }
        //先转成字符数组
        char[] chs = word.toCharArray();
        //建立遍历节点，先指向根节点，准备往下
        TrieNode node = root;
        //经过根节点，pass+1
        node.pass++;
        //遍历字符数组
        for(int i = 0; i < chs.length; i++){
            //转成字符在 nexts 中的默认位置
            int index = chs[i] - 'a';
            //如果该节点node的nexts中index位置没有节点，说明node下面没有接这个字符，加进去
            if(node.nexts[index] == null){
                node.nexts[index] = new TrieNode();
            }
            //继续往下走，经过下面这个节点，这个节点的pass++
            node = node.nexts[index];
            node.pass++;
        }
        //遍历完数组，此时node来到了这个字符串的最后一个字符，end++
        end++;
    }
    
    //删除字符串
    public void delete(String word){
        //先确保树中有这个字符串
        if(search(word) != 0){
            TrieNode node = root;
            char[] chs = word.toCharArray();
            //经过这个点pass-1
            node.pass--;
            //遍历字符数组
            for(int i = 0; i < chs.length; i++){
                int index = chs[i] - 'a';
                //如果该节点的pass减到了0，后面的就不用看了，直接置空返回
                if(--node.nexts[index].pass == 0){
                    node.nexts[index] = null;
                    return;
                }
                //如果没有减到0，继续往下
                node = node.nexts[index];
            }
            //减到了最后，就将end-1
            node.end--;
        }
    }
    
    //搜索某字符串出现了几次
    public int search(String word){
        if(word == null){
            return 0;
        }
        char[] chs = word.toCharArray();
        TrieNode node = root;
        //顺着字符串找到最后一个字符，返回其end值就可
        for(int i = 0; i < chs.length; i++){
            int index = chs[i] - 'a';
            //如果出现了不在树中的字符，说明没有这个字符串，直接返回0
            if(node.nexts[index] == null){
                return 0;
            }
            //一直往下
            node = node.nexts[index];
        }
        return node.end;
    }
    
    //查询以某字符串为前缀的字符串的数量
    public int prefixNumber(String pre){
        if(pre == null){
            return 0;
        }
        char[] chs = pre.toCharArray();
        TrieNode node = root;
        //跟着给的前缀字符串走，如果能走到最后，返回最后节点的pass值
        for(int i = 0; i < chs.length; i++){
            int index = chs[i] - 'a';
            //如果出现了不存在树中的字符，说明没有以这个字符串为前缀的字符串，直接返回
            if(node.nexts[index] == null){
                return 0;
            }
            //往下走
            node = node.nexts[index];
        }
        return node.pass;
    }
}