栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法与数据结构——算法基础——前缀树(java)(b站左程云课程笔记总结)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法与数据结构——算法基础——前缀树(java)(b站左程云课程笔记总结)

前缀树

经典前缀树方式:在路径上赋值

public static class TrieNode {
    public int path;//通过的次数
    public int end;//以该节点为结尾的次数
    public TrieNode[] nexts;//字符种类多的话使用HashMap nexts;

    public TrieNode() {
        path = 0;
        end = 0;
        //nexts[0]==null 没有走向'a'的路
        //nexts[0]!=null 有走向'a'的路
        //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;
        int index=0;
        for(int i=0;i
            index=chs[i]-'a';
            if(node.nexts[index]==null){
                node.nexts[index]=new TrieNode();
            }
            node=node.nexts[index];
            node.path++;
        }
        node.end++;
    }
    
    //查询一个字符串加入过几次
    public int search(String word){
        if(word==null){
            return 0;
        }
        char[] chs=word.toCharArray();
        TrieNode node=root;
        int index=0;
        for(int i=0;i
            index=chs[i]-'a';
            if(node.nexts[index]==null){
                return 0;
            }
            node=node.nexts[index];
        }
        return node.end;
    }
    
    
    //所有加入的字符串,有几个是以pre这个字符串作为前缀的
    public int prefixNumber(String pre){
        if(pre==null){
            return 0;
        }
        char[] chs=pre.toCharArray();
        TrieNode node=root;
        int index=0;
        for(int i=0;i
            index=chs[i]-'a';
            if(node.nexts[index]==null){
                return 0;
            }
            node=node.nexts[index];
        }
        return node.path;
    }
    
    //删除
    public void delete(String word){
        if(search(word)!=0){//确定树中有word才删除
            char[] chs=word.toCharArray();
            TrieNode node=root;
            node.pass--;
            int index=0;
            for(int i=0;i
                index=chs[i]-'a';
                if(--node.nexts[index].pass==0){//注意这种情况
                    node.nexts[index]=null;//gc
                    return;
                }
                node=node.nexts[index];
            }
            node.end--;
        }
    }
}

前缀树功能:
  1. 查询字符串的时间复杂度为O(k),k为字符串的长度(与哈希表一样查询时间复杂度为常数级别)
  2. 查询前缀(P值)(哈希表没法实现)
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/981156.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号