请选择 进入手机版 | 继续访问电脑版

字典树Tire的一个小总结

[复制链接]
丶禁飞 发表于 2021-1-1 10:33:46 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
https://blog.csdn.net/king_cannon_fodder/article/details/77175620
https://blog.csdn.net/qq_41650771/article/details/81590101
https://blog.csdn.net/u013588639/article/details/38406453
前一段时间呢学习了一下字典树,发现字典树在办理某些问题上是非常方便的(与STL中的map有些相似的地方),下面是我对字典树做的一些总结,也不算做总结,写出了自己对字典树的一些相识而已。
字典树(Trie树),单词查找树大概前缀树,是一种用于快速检索的多叉树布局,如英文字母的字典树是一个26叉树或52叉树,数字的字典树是一个10叉树。Trie树的键由节点在树中的位置决定的,一个节点的所有子节点都有相同的前缀,根结点对应的是空字符串。
Trie树优点是最大限度地淘汰无谓的字符串比力,查询效率比力高。核心思想是空间换时间,使用字符串的公共前缀来低落查询时间的开销以到达提高效率的目的。(以只有小写字母为例)
 
(1) 插入、查找的时间复杂度均为O(N),此中N为字符串长度。
(2) 空间复杂度是26^n级别的,非常巨大(可接纳二维数组实现改善)。
 
它有3个根本性质:
 
根节点不包罗字符,除根节点外每一个节点都只包罗一个字符。
从根节点到某一节点,路径上颠末的字符毗连起来,为该节点对应的字符串。
每个节点的所有子节点包罗的字符都不相同。
 
Trie树的实现
(1)使用链表来创建立。可以省下很大的空间,却增加了时间复杂度。
(2)使用二维数组来创建
 
插入步调:
 
首先判断字符是否存在,不存在就新建一个节点,存在的话就共享,判断下一个字符,判断到最后一个字符,并标记一下竣事。
(根据详细要求,采取差别的标记方法)。
 
查询步调:
 
跟插入雷同,判断字符是否存在,若存在,继续判断下一个字符,若不存在,返回0。
 
Trie树的应用:
 
(1)字符串的检索
 
(2)求字符串的最长公共子序列
 
(3)将字符串举行排序
 
(4)字符串的频率统计
 
(5)字符串的前缀匹配
 
(6)作为其他数据布局和算法的辅助布局。
 
代码实现:
 
(1)链表实现:
 
 
 
typedef struct node
{
    int cnt;
    node *next[26];
};
node root;
void CreateTrie(char *str)  // 创建Trie树
{
    int len=strlen(str);
    node *p=&root;
    node *q;;
    for (int i=0;i< len;i++)
    {
        int id=str-&#39;a&#39;;
        if (p->next[id]==NULL)
        {
            q=(node*)malloc(sizeof(node));
            q->cnt=1;
            for (int j=0;jnext[j]=NULL;
            p->next[id]=q;
            p=p->next[id];
        }
        else
        {
            p->next[id]->cnt++;
            p=p->next[id];
        }
    }
}
int FindTire(char *str) // 查询
{
    int len=strlen(str);
    node *p=&root;
    for (int i=0;i< len;i++)
    {
        int id=str-&#39;a&#39;;
        p=p->next[id];
        if (p==NULL)
            return 0;
    }
    return p->cnt;
}
void DeleteTire(node *root)  // Trie树的销毁
{
    for (int i=0;inext!=NULL)
            DeleteTire(root->next);
    free(root);
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
 
下图是对单词hat、hap、my、new、npc建立的一个字典树
     
很容易明确,如果有两个单词拥有相同的前缀,比方hat、hap,”ha”只需新建一次。

 
(2)数组实现:
 
 
 

int chara[200001][26];
int vis[200001];  // 用来标记前缀出现的次数 
int e=1;  // 出现的新节点的个数
void Insert(char *str)  //  建立Trie树
{
    int len=strlen(str);
    int i,p=1;
    for (int i=0;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )