字典树Tire的一个小总结

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