字典树（Trie）

Grisses · 2023-01-12 10:47:19 · 个人记录

一、是什么

字典树是一种处理字符串和数字（本质的将其化为字符串）的树状结构，并且是多叉树。

二、节点

每个节点有信息：val,t[]。其中 val 是节点储存的各种权值，t[] 储存该节点各个子节点的编号。

三、边

在边上储存的是字符，一个字符串是以路径的形式存储的。

四、实现

1. 插入

如图，在树中，现已储存了一些字符串，如果现在插入一个 abc。那么首先，从根节点开始递归，指向第一个字符 a 所对应的节点的边是存在的，所以沿着此边向下。同样，b 所对应的边也存在。然后我们发现第三个字符 c 所对应的点不存在，所以我们新建一个节点 16 来储存 c。最后，修改节点 16 的权值（否则无法判断是一个完整的字符串还是某字符串的前缀）。

      int Insert(int q,char *s){
          int len=strlen(s);//获取长度
          for(int i=0;i<len;i++){//模拟递归
              if(c[q].t[s[i]-'a']==-1)c[q].t[s[i]-'a']=Build();//没有就新建
              q=c[q].t[s[i]-'a'];//向下递归
          }
          c[q].val=1;//标记（此处如何标记以题目要求执行）
          return q;
      }

2.查询

依然是递归，同动态开点线段树，如果指向为空即表明无此字符串，返回 0 即可。递归到底后，检查标记（防止只是个前缀），返回结果即可。

    bool Search(int q,char *s){
        int len=strlen(s);//获取长度
        for(int i=0;i<len;i++){//模拟递归
            if(c[q].t[s[i]-'a']==-1)return 0;//没有这个串
            q=c[q].t[s[i]-'a'];
        }
        return c[q].val;//检查
    }