精华内容
下载资源
问答
  • Trie树

    千次阅读 2020-06-20 15:04:39
    删除3.Trie树的模拟实现 一、什么是Trie树 Trie,又经常叫前缀树,字典树等等。它有很多变种,如后缀树,Radix Tree/Trie,PATRICIA tree,以及bitwise版本的crit-bit tree。当然很多名字的意义其实有

    Trie树

    一、什么是Trie树

    • Trie,又经常叫前缀树,字典树等等。它有很多变种,如后缀树,Radix Tree/Trie,PATRICIA tree,以及bitwise版本的crit-bit tree。当然很多名字的意义其实有交叉。

    在这里插入图片描述

    上图就是由单词at,bee,ben,bt,q组成的Trie树

    1.定义

    • 在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串
    • 与二叉查找树不同,不是直接保存在节点中,而是由节点在树中的位置决定
    • 一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串
    • 一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。
    • trie中的键通常是字符串,但也可以是其它的结构
    • trie的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie中的键是一串位元,可以用于表示整数或者内存地址

    2.基本性质

    • 1,根节点不包含字符,除根节点意外每个节点只包含一个字符。
    • 2,从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
    • 3,每个节点的所有子节点包含的字符串不相同

    3.优点:

    可以最大限度地减少无谓的字符串比较,故可以用于词频统计和大量字符串排序。

    • 跟哈希表比较:
    • 最坏情况时间复杂度比hash表好
    • 没有冲突,除非一个key对应多个值(除key外的其他信息)
    • 自带排序功能(类似Radix Sort),中序遍历trie可以得到排序

    4.缺点:

    • 虽然不同单词共享前缀,但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针(不包含卫星数据)。

    • 每个结点的子树的根节点的组织方式有几种。

    • 1>如果默认包含所有字符集,则查找速度快但浪费空间(特别是靠近树底部叶子)。

    • 2>如果用链接法(如左儿子右兄弟),则节省空间但查找需顺序(部分)遍历链表。

    • 3>alphabet reduction: 减少字符宽度以减少字母集个数。

    • 4>对字符集使用bitmap,再配合链接法。

    • 如果数据存储在外部存储器等较慢位置,Trie会较hash速度慢(hash访问O(1)次外存,Trie访问O(树高))。

    • 长的浮点数等会让链变得很长。可用bitwise trie改进。

    5.bit-wise Trie

    类似于普通的Trie,但是字符集为一个bit位,所以孩子也只有两个。

    可用于地址分配,路由管理等

    虽然是按bit位存储和判断,但因为cache-local和可高度并行,所以性能很高。跟红黑树比,红黑树虽然纸面性能更高,但是因为cache不友好和串行运行多,瓶颈在存储访问延迟而不是CPU速度

    6.压缩Trie

    1.压缩分支条件:

    • 1,Trie基本不变
    • 2,只是查询
    • 3,key跟结点的特定数据无关
    • 4,分支很稀疏

    若允许添加和删除,就可能需要分裂和合并结点。此时可能需要对压缩率和更新(裂,并)频率进行折中。

    7.外存Trie

    某些变种如后缀树适合存储在外部,另外还有B-trie等。

    应用场景

    • (1) 字符串检索
      事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。

    举例:
    1,给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
    2,给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。

    3,1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。

    • (2)文本预测、自动完成,see also,拼写检查
    • (3)词频统计
    • (4)排序

    Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。

    比如给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。

    • (5)字符串最长公共前缀

    Trie树利用多个字符串的公共前缀来节省存储空间,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。

    举例: 给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少?
    解决方案:首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线(Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。
    而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:

    1. 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;
    2. 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;
    • (6)字符串搜索的前缀匹配

    • trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

    • Trie树检索的时间复杂度可以做到n,n是要检索单词的长度,
      如果使用暴力检索,需要指数级O(n2)的时间复杂度。

    • 7) 作为其他数据结构和算法的辅助结构

    如后缀树,AC自动机等

    后缀树可以用于全文搜索

    二、Trie树的基本操作实现

    1.Trie树的原理

    • 利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。
    • 下面以英文单词构建的字典树为例,这棵Trie树中每个结点包括26个孩子结点,因为总共有26个英文字母(假设单词都是小写字母组成)。

    则可声明包含Trie树的结点信息的结构体:

    #define MAX 26
    
    typedef struct TrieNode               //Trie结点声明 
    {
        bool isStr;                      //标记该结点处是否构成单词 
        struct TrieNode *next[MAX];      //儿子分支 
    }Trie;
    

    其中next是一个指针数组,存放着指向各个孩子结点的指针

    如给出字符串"abc",“ab”,“bd”,“dda”,根据该字符串序列构建一棵Trie树。
    则构建的树如下:
    在这里插入图片描述

    • Trie树的根结点不包含任何信息,第一个字符串为"abc",第一个字母为'a',因此根结点中数组next下标为'a'-97的值不为NULL,其他同理,红色结点表示在该处可以构成一个单词
    • 很显然,如果要查找单词"abc"是否存在,查找长度则为O(len),len为要查找的字符串的长度。而若采用一般的逐个匹配查找,则查找长度为O(len*n),n为字符串的个数。显然基于Trie树的查找效率要高很多
    • 但是却是以空间为代价的,比如图中每个结点所占的空间都为(26*4+1)Byte=105Byte,那么这棵Trie树所占的空间则为105*8Byte=840Byte,而普通的逐个查找所占空间只需(3+2+2+3)Byte=10Byte

    2.Trie树的操作

    在Trie树中主要有3个操作,插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况,因此只考虑删除整棵树。

    1.插入

    • 假设存在字符串str,Trie树的根结点为root。i=0,p=root。
    • 1)取str[i],判断p->next[str[i]-97]是否为空,若为空,则建立结点temp,并将p->next[str[i]-97]指向temp,然后p指向temp;若不为空,则p=p->next[str[i]-97];
    • 2)i++,继续取str[i],循环1)中的操作,直到遇到结束符’\0’,此时将当前结点p中的isStr置为true。

    2.查找

    • 假设要查找的字符串为str,Trie树的根结点为root,i=0,p=root

    • 1)取str[i],判断判断p->next[str[i]-97]是否为空,若为空,则返回false;若不为空,则p=p->next[str[i]-97],继续取字符。

    • 2)重复1)中的操作直到遇到结束符'\0',若当前结点p不为空并且isStr为true,则返回true,否则返回false。

    3.删除

    删除可以以递归的形式进行删除

    3.Trie树的模拟实现

    #include <iostream>
    #include<cstdlib>
    #define MAX 26
    using namespace std;
     
    typedef struct TrieNode                     //Trie结点声明 
    {
        bool isStr;                            //标记该结点处是否构成单词 
        struct TrieNode *next[MAX];            //儿子分支 
    }Trie;
     
    void insert(Trie *root,const char *s)     //将单词s插入到字典树中 
    {
        if(root == NULL || *s == '\0')
            return;
        
        int i;
        Trie *p = root;
        while(*s != '\0')
        {
            if(p->next[*s - 'a'] == NULL)        //如果不存在,则建立结点 
            {
                Trie *temp = (Trie *)malloc(sizeof(Trie));
                for(i = 0;i < MAX;i++)
                {
                    temp->next[i] = NULL;
                }
                temp->isStr = false;
                p->next[*s - 'a'] = temp;
                p = p->next[*s - 'a'];   
            }   
            else
            {
                p = p->next[*s - 'a'];
            }
            s++;
        }
        p->isStr = true;                  //单词结束的地方标记此处可以构成一个单词 
    }
     
    int search(Trie *root,const char *s)  //查找某个单词是否已经存在 
    {
        Trie *p = root;
        while(p != NULL && *s != '\0')
        {
            p = p->next[*s - 'a'];
            s++;
        }
        return (p != NULL && p->isStr == true);      //在单词结束处的标记为true时,单词才存在 
    }
     
    void del(Trie *root)                      //释放整个字典树占的堆区空间 
    {
        int i;
        for(i = 0;i < MAX;i++)
        {
            if(root->next[i] != NULL)
            {
                del(root->next[i]);
            }
        }
        free(root);
    }
     
    int main(int argc, char *argv[])
    {
        int i;
        int n,m;                              //n为建立Trie树输入的单词数,m为要查找的单词数 
        char s[100];
        Trie *root = (Trie *)malloc(sizeof(Trie));
        for(i = 0;i < MAX;i++)
        {
            root->next[i] = NULL;
        }
        root->isStr = false;
        scanf("%d",&n);
        getchar();
        for(i = 0;i < n;i++)                 //先建立字典树 
        {
            scanf("%s",s);
            insert(root,s);
        }
        while(scanf("%d",&m) != EOF)
        {
            for(i = 0;i < m;i++)                 //查找 
            {
                scanf("%s",s);
                if(search(root,s) == 1)
                    printf("YES\n");
                else
                    printf("NO\n");
            }
            printf("\n");   
        }
        del(root);                         //释放空间很重要 
        return 0;
    }
    
    展开全文
  • Trie

    2017-03-09 16:17:17
    Trie树,又称字典树,关于它的结构就不详细介绍了。Trie树在单词统计、前缀匹配等很多方面有很大用处。它的主要特点如下: ...我自己用java实现了一个最基本的Trie树,功能有:插入单词,查找单词,删除单词,以

    Trie树,又称字典树,关于它的结构就不详细介绍了。Trie树在单词统计、前缀匹配等很多方面有很大用处。它的主要特点如下:

    • 根节点不包含字符,除根节点外的每一个节点都只包含一个字符。
    • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
    •  每个节点的所有子节点包含的字符都不相同。

    我自己用java实现了一个最基本的Trie树,功能有:插入单词,查找单词,删除单词,以字典序遍历打印出所有出现过的单词及频数。另有几点说明如下:

    • 每个结点存储子结点时不使用固定长度的数组,而使用Map<Character, TrieNode>结构,这样可以处理任意字符集。当然,你还得准备一个char型数组,以字典序存储要处理的所有字符,遍历的时候回用到。顺便提一下,如果你确定处理的只涉及26个英文字母,用一个26个大小的数组来存储子结点是个不错的选择,且比较简单。
    • Node结点中存储哪些值要看实际情况,在本例中存储的是单词的出现次数。你也可以增加一个字段prefixNum,用于存储当前前缀出现次数(即含有当前前缀的单词数)。这个参数是很有用的,而且在删除操作时,只需要从根结点往下判断第一个prefixNum==1的删除即可。自己试一下就明白了。我之所以没采用,主要想练习一下递归算法,好久没用了。Trie树的java实现 - lovewr - 远香清梦
    • 前一点说结点中的数据根据实际情况而定,再举个例子。“题目:给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,求第一次出现在第几个位置。”对于这个题目,显然结点中就存储单词第一次出现的位置(假如当前结点是单词结尾)。
    • import java.util.*;

       

      /**  * Tries数据结构(字典树)  * 这里只是最基本的实现,可判断某个单词是否出现过,单词出现频数等,根据需要可做其它扩展  * @author  *  */ public class Trie {   private TrieNode root;  private char[] characterTable= {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',  // 遍历的时候使用    'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};    public Trie() {   root = new TrieNode();  }    /**   * 插入字符串   * @param word   */  public void insert(String word) {   TrieNode node = root;   word = word.trim();   for (int i = 0; i < word.length(); i++) {    if (!(node.children.containsKey(word.charAt(i)))) {     node.children.put(word.charAt(i), new TrieNode());    }    node = node.children.get(word.charAt(i));   }   node.terminable = true;   node.count ++;  }

       /**   * 查找某个字符串   * @param word   * @return   */  public boolean find(String word) {   TrieNode node = root;   for(int i = 0; i < word.length(); i++) {    if(!(node.children.containsKey(word.charAt(i)))) {     return false;    } else {     node = node.children.get(word.charAt(i));    }   }   return node.terminable;  // 即便该字符串在Trie路径中,也不能说明该单词已存在,因为它有可能是某个子串    } 

       

      /**   * 删除某个字符串(必须是个单词,而不是前缀)   *   * @param word   */  public void delete(String word) {   if(!find(word)) {    System.out.println("no this word.");    return;   }   TrieNode node = root;   deleteStr(node, word);  }    public boolean deleteStr(TrieNode node, String word) {   if(word.length() == 0) {    node.terminable = false;  // 不要忘了这里信息的更新    return node.children.isEmpty();   }   if (deleteStr(node.children.get(word.charAt(0)), word.substring(1))) {    node.children.remove(word.charAt(0));    if (node.children.isEmpty() && node.terminable == false) {  // 注意第二个条件,假如有"abcd"与"abc",删除abcd时,要判断中间路径上是不是另一个子串的结束     return true;    }   }   return false;  }    /**   * 以字典序输出Tire中所有出现的单词及频数   */  public void traverse() {   StringBuffer word = new StringBuffer("");   TrieNode node = root;   traverseTrie(node, word);  }     public void traverseTrie(TrieNode node, StringBuffer word) {   if(node.terminable) {    System.out.println(word + "------" + node.count);     if(node.children.isEmpty()) return;   }   for(int i=0; i<characterTable.length; i++) {    if(!(node.children.containsKey(characterTable[i]))) continue;    traverseTrie(node.children.get(characterTable[i]), word.append(characterTable[i]));    word.deleteCharAt(word.length()-1);   }  }

      }

       

      /**  * Trie结点类  *  * @author  * @param <T>  */ class TrieNode {  public boolean terminable;  // 是不是单词结尾(即叶子节点)  public int count;  // 单词出现频数  public Map<Character, TrieNode> children = null;    public TrieNode() {   terminable = false;    count = 0;    children = new HashMap<Character, TrieNode>();   } }


    展开全文
  • trie

    2013-08-01 10:50:44
    至于trie树删除单个节点实在是少见,故在此不做详解。 Trie原理 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 Trie性质 好多人说trie的根节点不包含...

    本文讨论一棵最简单的trie树,基于英文26个字母组成的字符串,讨论插入字符串、判断前缀是否存在、查找字符串等基本操作;至于trie树的删除单个节点实在是少见,故在此不做详解。

    • Trie原理

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

    • Trie性质

    好多人说trie的根节点不包含任何字符信息,我所习惯的trie根节点却是包含信息的,而且认为这样也方便,下面说一下它的性质 (基于本文所讨论的简单trie树)

    1.    字符的种数决定每个节点的出度,即branch数组(空间换时间思想)

    2.    branch数组的下标代表字符相对于a的相对位置

    3.    采用标记的方法确定是否为字符串。

    4.    插入、查找的复杂度均为O(len),len为字符串长度

    • Trie的示意图

    如图所示,该trie树存有abc、d、da、dda四个字符串,如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL

    • Trie的优点举例

    已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:

    1.    最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n^2)。

    2.    使用hash:我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)* O(1)= O(n)。

    3.    使用trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len),而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(n*len),实际查询的复杂度只是O(len)。

    解释一下hash为什么不能将建立与查询同时执行,例如有串:911,911456输入,如果要同时执行建立与查询,过程就是查询911,没有,然后存入9、91、911,查询911456,没有然后存入9114、91145、911456,而程序没有记忆功能,并不知道911在输入数据中出现过。所以用hash必须先存入所有子串,然后for循环查询。

    而trie树便可以,存入911后,已经记录911为出现的字符串,在存入911456的过程中就能发现而输出答案;倒过来亦可以,先存入911456,在存入911时,当指针指向最后一个1时,程序会发现这个1已经存在,说明911必定是某个字符串的前缀,该思想是我在做pku上的3630中发现的,详见本文配套的“入门练习”。


    Trie学习简单的trie树详解

    Phone List
    Time Limit: 1000MS   Memory Limit: 65536K
    Total Submissions: 5512   Accepted: 1770

    Description

    Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers:

    • Emergency 911
    • Alice 97 625 999
    • Bob 91 12 54 26

    In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.

    Input

    The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

    Output

    For each test case, output "YES" if the list is consistent, or "NO" otherwise.

    Sample Input
    2
    3
    911
    97625999
    91125426
    5
    113
    12340
    123440
    12345
    98346

    Sample Output
    NO
    YES

    方法一:trie

    有了上面学习的思考与总结,3630trie树本以为可以水过,可是学习和做题终究是两回事,我很快写出trie树,然后提交,超时了。

    后来受discuss提示,我大致计算了一下本题trie树的复杂度,号码个数10000,长度10,树的宽度大概有10000,所以总的节点数大概就有100,000级,即要进行十万次new的操作,确实时间耗费很多,估计这样题目的用时要有1秒到2秒左右的样子。

    于是为了纯粹的做题,我将new操作省掉,改为提前申请一个buffer空间,就ac了,时间变为125ms了,不过这样确实挺耗空间的,没办法,为了做题只能用空间换时间。

    代码如下:


     1#include<iostream>
     2using namespace std;
     3int cases, count;
     4int nodenum;
     5
     6struct node
     7{
     8    bool isExist;
     9    node * branch[10];
    10}
    Node[100000];
    11
    12class Trie
    13{
    14private:
    15    node root;
    16public:
    17    Trie(){root = Node[0];}
    18    bool insert(char num[])
    19    {
    20        node *location = &root;
    21        int i = 0;
    22        int len = strlen(num);
    23        while(num[i])
    24        {
    25            if(i==len-1 && location->branch[num[i]-'0'!= NULL) //解决没有按照长度排序而存在的问题
    26            {
    27                return false;
    28            }

    29            if(location->branch[num[i]-'0']==NULL)//没有建立
    30            {
    31                location->branch[num[i]-'0'= &Node[nodenum];
    32                Node[nodenum].isExist = false;
    33                memset(Node[nodenum].branch,NULL,sizeof(Node[nodenum].branch));
    34                nodenum++;
    35            }

    36            if(location->branch[num[i]-'0']->isExist == true)
    37            {
    38                return false;
    39            }

    40            location = location->branch[num[i]-'0'];
    41            i++;
    42        }

    43        location->isExist = true;
    44        return true;
    45    }

    46}
    ;
    47
    48int main()
    49{
    50    scanf("%d",&cases);
    51    while(cases--)
    52    {
    53        nodenum = 1;
    54        bool flag = true;
    55        scanf("%d",&count);
    56        char tel[11];
    57        Trie t;
    58        while(count--)
    59        {
    60            scanf("%s",tel);
    61            if(!t.insert(tel))
    62            {
    63                flag = false;
    64            }

    65        }

    66        if(flag)
    67        {
    68            printf("YES\n");
    69        }

    70        else
    71        {
    72            printf("NO\n");
    73        }

    74    }

    75    return 0;
    76}

    77

    方法二:

        转成数字存储比较,这样的话用long整形就可以,然用除法+取余的方法核对是否是某个数字的前缀,但是这种方法的复杂度显然是O(n^2)呀,所以就不尝试了。

    方法三:

    受大雄提示,可以使用字符串排序比较来做,因为通过排序,前缀子串肯定是与父串挨着的,嘿嘿,这样做,思路简单、代码量少,易理解啊,所以很快ac,下面分析一下复杂度。
        
    理论上使用trie的平均复杂度应该是n*len;其中,len是号码的平均长度,n是号码的个数。使用数组进行字符比较,理论上的复杂度有n*len+logn,排序为logn,然后查询是否存在前缀子串是n*len。所以后者应该时间稍微多一点,提交后果然,耗时188ms

    另外值得一提的是使用数组比较的方法有个好处,那就是地址都是连续的,cpu在寻址时会非常快,而用链式结构(即指针),包括使用数组型的trie树则是跳来跳去的,故会有一些开销吧。

    呵呵,我所崇拜的排序又一次派上用场了。

    代码如下:

     


     1#include<iostream>
     2using namespace std;
     3
     4int cases, count;
     5char tel[10005][11];
     6int i, j;
     7
     8int cmp(const void *a, const void *b)
     9{
    10    return strcmp( (char*)a,(char*)b );
    11}

    12
    13int main()
    14{
    15    scanf("%d",&cases);
    16    while(cases--)
    17    {
    18        bool flag = true;
    19        scanf("%d",&count);
    20        for(i = 0; i < count; i++)
    21        {
    22            scanf("%s",tel[i]);
    23        }

    24        qsort(tel,count,sizeof(char)*11,cmp);
    25        int len1, len2;
    26        for(i = 1; i < count; i++)
    27        {
    28            len1 = strlen(tel[i-1]);
    29            len2 = strlen(tel[i]);
    30            j = 0;
    31            if(len1 <= len2)
    32            {
    33                while(tel[i-1][j] == tel[i][j] && j < len1)
    34                {
    35                    j++;
    36                }

    37                if(j == len1)
    38                {
    39                    flag = false;
    40                }

    41            }

    42            if(!flag)
    43            {
    44                break;
    45            }

    46        }

    47        if(flag)
    48        {
    49            printf("YES\n");
    50        }

    51        else
    52        {
    53            printf("NO\n");
    54        }

    55    }

    56    return 0;
    57}

    58

     Trie的简单实现(插入、查询)

    #include <iostream>
    using namespace std;
    
    const int branchNum = 26; //声明常量 
    int i;
    
    struct Trie_node
    {
        bool isStr; //记录此处是否构成一个串。
        Trie_node *next[branchNum];//指向各个子树的指针,下标0-25代表26字符
        Trie_node():isStr(false)
        {
           memset(next,NULL,sizeof(next));
        }
    };
    
    class Trie
    {
    public:
        Trie();
        void insert(const char* word);
        bool search(char* word); 
        void deleteTrie(Trie_node *root);
    private:
        Trie_node* root;
    };
    
    Trie::Trie()
    {
        root = new Trie_node();
    }
    
    void Trie::insert(const char* word)
    {
        Trie_node *location = root;
        while(*word)
        {
            if(location->next[*word-'a'] == NULL)//不存在则建立
            {
                Trie_node *tmp = new Trie_node();
               location->next[*word-'a'] = tmp;
            }    
           location = location->next[*word-'a']; //每插入一步,相当于有一个新串经过,指针要向下移动
            word++;
       }
        location->isStr = true; //到达尾部,标记一个串
    }
    
    bool Trie::search(char *word)
    {
        Trie_node *location = root;
        while(*word && location)
        {
            location = location->next[*word-'a'];
            word++;
        }
        return(location!=NULL && location->isStr);
    }
    
    void Trie::deleteTrie(Trie_node *root)
    {
        for(i = 0; i < branchNum; i++)
        {
            if(root->next[i] != NULL)
            {
                deleteTrie(root->next[i]);
            }
        }
        delete root;
    }
    
    void main() //简单测试
    {
        Trie t;
        t.insert("a");         
        t.insert("abandon");
        char * c = "abandoned";
        t.insert(c);
        t.insert("abashed");
        if(t.search("abashed"))
            printf("true\n");
    }




    展开全文
  • trie树

    2012-05-22 17:19:27
    至于trie树删除单个节点实在是少见,故在此不做详解。 Trie原理 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 Trie性质 好多人说trie的根节点不...
    
    

        本文讨论一棵最简单的trie树,基于英文26个字母组成的字符串,讨论插入字符串、判断前缀是否存在、查找字符串等基本操作;至于trie树的删除单个节点实在是少见,故在此不做详解。

    • Trie原理

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

    • Trie性质

    好多人说trie的根节点不包含任何字符信息,我所习惯的trie根节点却是包含信息的,而且认为这样也方便,下面说一下它的性质 (基于本文所讨论的简单trie树)

    1.    字符的种数决定每个节点的出度,即branch数组(空间换时间思想)

    2.    branch数组的下标代表字符相对于a的相对位置

    3.    采用标记的方法确定是否为字符串。

    4.    插入、查找的复杂度均为O(len),len为字符串长度

    • Trie的示意图

    如图所示,该trie树存有abc、d、da、dda四个字符串,如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL

    • Trie的优点举例

    已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:

    1.    最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n^2)。

    2.    使用hash:我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(n*len)。查询的复杂度为O(n)* O(1)= O(n)。

    3.    使用trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len),而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(n*len),实际查询的复杂度只是O(len)。

    解释一下hash为什么不能将建立与查询同时执行,例如有串:911,911456输入,如果要同时执行建立与查询,过程就是查询911,没有,然后存入9、91、911,查询911456,没有然后存入9114、91145、911456,而程序没有记忆功能,并不知道911在输入数据中出现过。所以用hash必须先存入所有子串,然后for循环查询。

    而trie树便可以,存入911后,已经记录911为出现的字符串,在存入911456的过程中就能发现而输出答案;倒过来亦可以,先存入911456,在存入911时,当指针指向最后一个1时,程序会发现这个1已经存在,说明911必定是某个字符串的前缀,该思想是我在做pku上的3630中发现的,详见本文配套的“入门练习”。

    •  Trie的简单实现(插入、查询)
    01 #include <iostream>
    02 using namespace std;
    03
    04 const int branchNum = 26; //声明常量 
    05 int i;
    06
    07 struct Trie_node
    08 {
    09     bool isStr; //记录此处是否构成一个串。
    10     Trie_node *next[branchNum];//指向各个子树的指针,下标0-25代表26字符
    11     Trie_node():isStr(false)
    12     {
    13         memset(next,NULL,sizeof(next));
    14     }
    15 };
    16
    17 class Trie
    18 {
    19 public:
    20     Trie();
    21     void insert(const char* word);
    22     bool search(char* word);
    23     void deleteTrie(Trie_node *root);
    24 private:
    25     Trie_node* root;
    26 };
    27
    28 Trie::Trie()
    29 {
    30     root = new Trie_node();
    31 }
    32
    33 void Trie::insert(const char* word)
    34 {
    35     Trie_node *location = root;
    36     while(*word)
    37     {
    38         if(location->next[*word-'a'] == NULL)//不存在则建立
    39         {
    40             Trie_node *tmp = new Trie_node();
    41             location->next[*word-'a'] = tmp;
    42         }
    43         location = location->next[*word-'a']; //每插入一步,相当于有一个新串经过,指针要向下移动
    44         word++;
    45     }
    46     location->isStr = true; //到达尾部,标记一个串
    47 }
    48
    49 bool Trie::search(char *word)
    50 {
    51     Trie_node *location = root;
    52     while(*word && location)
    53     {
    54         location = location->next[*word-'a'];
    55         word++;
    56     }
    57     return(location!=NULL && location->isStr);
    58 }
    59
    60 void Trie::deleteTrie(Trie_node *root)
    61 {
    62     for(i = 0; i < branchNum; i++)
    63     {
    64         if(root->next[i] != NULL)
    65         {
    66             deleteTrie(root->next[i]);
    67         }
    68     }
    69     delete root;
    70 }
    71
    72 void main() //简单测试
    73 {
    74     Trie t;
    75     t.insert("a");
    76     t.insert("abandon");
    77     char * c = "abandoned";
    78     t.insert(c);
    79     t.insert("abashed");
    80     if(t.search("abashed"))
    81         printf("true\n");
    82 }

    展开全文
  • TRIE树

    千次阅读 2008-03-29 13:46:00
    TRIE树,又称键树,可以用来构造字典,适合所有元素都是由字母和数字标记的情形。下面是TRIE树的一种C++实现:#include #include #include using namespace std;const int num_chars = 26;class Trie { protected...
  • trie树字典树的插入和删除

    千次阅读 2016-10-11 14:18:58
    #include #include using namespace std;...typedef struct Trie_node { int count; // 统计单词前缀出现的次数 struct Trie_node* next[26]; // 指向各个子树的指针 bool exist; // 标记该结点处是否构
  • trie树 详解

    2012-04-25 13:12:00
    前几天学习了并查集和trie树,...至于trie树删除单个节点实在是少见,故在此不做详解。lTrie原理Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。lTrie性质好多人说...
  • Trie树,插入,查找,删除,遍历

    千次阅读 2018-09-12 21:54:41
    Trie树的结构如下: 就根据这个图来建立就好了。 就是删除要考虑几种情况: 1.删除中间的红点 2.删除末红点找到前面的支点(如上图,要删除bcd,就要找到b指的节点,再向下删除,像abd,就要从ab指的节点删掉...
  • Trie树—高级树型结构

    2020-04-06 01:16:04
    文章目录Trie树的基本概念Trie树的特点Trie树的数据结构插入查找删除操作Trie树的应用 Trie树的基本概念 Trie 树中文名叫字典树、前缀树等等。这些名字暗示其与字符的处理有关,事实也确实如此,它主要用途就是将...
  • C++数据结构——Trie树

    2020-03-10 00:37:08
    具体的Trie树结构请自行查找,下面只说我自己那部分的理解。 ①Trie树是一棵多叉树,那么管理好子结点对树的性能有很大的...③Trie树不宜随便删除结点,因此我也不提供删除功能,只提供修改功能。 关于Trie树...
  • Python实现Trie树

    2018-06-13 11:00:23
    用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...
  • trie树--详解

    2010-10-19 21:32:00
    trie树--详解文章作者:yx_th000 文章来源:Cherish_yimi (http://www.cnblogs.com/cherish_yimi/) 转载请注明,谢谢合作。...至于trie树删除单个节点实在是少见,故在此不做详解。l Trie原理Trie的核心思
  • //trie树,字典树,前缀树,,都是同一颗树,哈希树的变种 题目链接 ...对于从树的根节点走到每一个黑色节点所经过的路径,...trie树,分别有插入,查询和删除3种操作,插入时,需要把经过的每个节点的所存的num值
  • Trie树也称字典树,因为其效率很高,所以在在字符串查找、前缀匹配等中应用很广泛,其高效率是以空间为代价的。 一.Trie树的原理  利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低...
  • Trie 字典 删除操作

    千次阅读 2014-05-30 20:48:18
    字典删除操作: 1 没找到直接返回 2 找到叶子节点的时候,叶子节点的count标志清零,代表不是叶子节点了 3 如果当前节点没有其他孩子节点的时候,可以删除这个节点 判断是否需是叶子节点,就检查叶子节点的...
  • 字典树(Trie树

    2019-03-05 18:27:13
    字典树(Trie树,单词查找树) 基本要点 根节点不包含字符,除根节点外每一个节点都只包含一个字符; 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串; 每个节点的所有子节点包含的字符...
  • trie树及其优化

    2019-09-02 15:29:24
    trie树,即字典树,是一种基于多字符串匹配的数据结构,该结构由根开始向下走到底,其中由跟到叶节点的一条路径组成了一个字符串。 其匹配的是到目标字符ch2位置,从ch2之前的某个字符ch1开始ch1....ch2为一种目标...
  • 再也不装逼全部扔进类里面写了 疯狂TLE 难受死了 max((a[i]+a[j])a[k])(i,j,k都不相同)max((a[i]+a[j])a[k])(i,j,k都不相同)max( (a[i] + a[j]) ^ a[k] ) (i, j, k都不相同) #include &...
  • trie树--详解

    2015-07-28 11:13:00
    前几天学习了并查集和trie树,这里...至于trie树删除单个节点实在是少见,故在此不做详解。 l Trie原理 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 l...
  • C++/C Trie树算法

    2009-06-10 19:37:18
    用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 363
精华内容 145
关键字:

trie树删除