中型网站,被官方认可赚钱软件,免费psd模板素材,网站建设导航栏设计字典树(Trie树)字典树#xff0c;又称单词查找树#xff0c;Trie树#xff0c;是一种树形结构#xff0c;典型应用是用于统计#xff0c;排序和保存大量的字符串#xff0c;所以经常被搜索引擎系统用于文本词频统计。它的优点是#xff1a;利用字符串的公共前缀来节约存… 字典树(Trie树)字典树又称单词查找树Trie树是一种树形结构典型应用是用于统计排序和保存大量的字符串所以经常被搜索引擎系统用于文本词频统计。它的优点是利用字符串的公共前缀来节约存储空间最大限度的减少无谓的字符串比较查询效率比哈希表高。 它有三个基本性质根节点不包含字符除根节点外每一个节点都只包含一个字符从根节点到某一节点路径上经过的字符连接起来为该节点对应的字符串每个节点的所有子节点包含的字符都不相同。 字典树的插入删除和查找都非常简单用一个一重循环即可。 1. 从根节点开始一次搜索 2. 取得要查找关键词的第一个字母并根据该字母选择对应的子树并转到该子树继续进行检索 3. 在相应的子树上取得要查找关键词的第二个字母并进一步选择对应的子树进行检索 4. 迭代过程... 5. 在某个节点处关键词的所有字母已被取出则读取附在该节点上的信息即完成查找 字典树的应用 1.字典树在串的快速检索中的应用。 给出N个单词组成的熟词表以及一篇全用小写英文书写的文章请你按最早出现的顺序写出所有不在熟词表中的生词。 在这道题中我们可以用数组枚举用哈希用字典树先把熟词建一棵树然后读入文章进行比较这种方法效率是比较高的。 2. 字典树在“串”排序方面的应用 给定N个互不相同的仅由一个单词构成的英文名让你将他们按字典序从小到大输出 用字典树进行排序采用数组的方式创建字典树这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可 3. 字典树在最长公共前缀问题的应用 对所有串建立字典树对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数于是问题就转化为最近公共祖先问题。 字典树的基本功能是用来查询某个单词前缀在所有单词中出现次数的一种数据结构它的插入和查询复杂度都为O(len),Len为单词前缀长度但是它的空间复杂度却非常高如果字符集是26个字母那每个节点的度就有26个典型的以空间换时间结构。 基本模版 1、结构体定义 struct node { int flag;//标记变量 int count;//记录字符出现次数 struct node *next[N]; }tree[maxn]; 2、新节点建立 int t0; struct node *creat() { int i; struct node *p; ptree[t]; p-count1; p-flag0; for(i0;iN;i) { p-next[i]NULL; } return p; } 3、插入 void insert(struct node **root,char *s) { int i,k; struct node *p; if(!(p*root)) { p*rootcreat(); } i0; while(s[i]) { ks[i]-a; if(p-next[k]) p-next[k]-count; else p-next[k]creat(); pp-next[k]; } p-flag1; } 4、查找 int search(struct node **root,char *s) { int i0,k; struct node *p; if(!(p*root)) { return 0; } while(s[i]) { ks[i]-a; if(!(p-next[k])) return 0; pp-next[k]; } return p-flag;//return p-count; }
