前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >模拟Trie树结构

模拟Trie树结构

作者头像
用户10604450
发布2024-03-15 14:31:12
880
发布2024-03-15 14:31:12
举报
文章被收录于专栏:练习两年半

Trie树的概念

Trie树是数据结构比较简单的一种。Trie 树的基本用法是高效的存储和查找字符串集合的数据结构。Trie树也叫做字典树,它是一个树形结构。是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串。Trie树本质,利用字符串之间的公共前缀,将重复的前缀合并在一起。

例如:

插入

abcdef

abdef

aced

bcdf

bcff

cdaa

bcdc

abc

1.首先插入abcdef

先判断根节点有没有a这个点作为子节点,没有就创建出来,以此类推,再从a往下走,判断a有没有b这个子节点,没有就创建出来,以此类推,把剩下的插入进来,(存的时候会在结尾的单词后面打上一个标记,表示在这个字母结尾是有一个的单词的)如图:

2.依次插入其他

最终结果

模板:

代码语言:javascript
复制
    static int N=100010;
    static int [][]son=new int[N][26];  //son[][]存储树中每个节点的子节点
    static int []cnt=new int[N];        //记录以每个结点结尾的单词数量
    static int idx;         //当前用的的哪个下标,下标0:既是根节点又是空节点
    //插入操作
    public static void insert(char []str){
        int p=0;//根节点
        for (int i = 0; i < str.length; i++) {//从根节点开始依次遍历
            int x=str[i]-'a';//把当前这个节点的下标取出来
            //如果当前这个点上不存在对应的字母的话,创建出来
            if(son[p][x]==0){
              son[p][x]=++idx;
            }
            //走到下一个点,p可以理解为父节点
            p=son[p][x];
        }
        cnt[p]++; //记录下这个单词出现次数
    }
    //查询操作
   public static int query(char []str){
       int p=0;
       for (int i = 0; i < str.length; i++) {
           int x=str[i]-'a';
           //如果不存在这个子节点的话,说明集合中不存在这个单词
           if(son[p][x]==0) return 0;
           p=son[p][x];
       }
       return cnt[p];
   }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-02-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Trie树的概念
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档