公司做外地网站,怎样创建网站吉洋大鼓,黄页网络的推广网站有哪些软件,wordpress生成静态页MiYu原创, 转帖请注明 : 转载自 ______________白白の屋 文章作者#xff1a;yx_th000 文章来源#xff1a;Cherish_yimi (http://www.cnblogs.com/cherish_yimi/) 转载请注明#xff0c;谢谢合作。关键词#xff1a;trie trie树 数据结构前几天学习了并查集和trie树yx_th000 文章来源Cherish_yimi (http://www.cnblogs.com/cherish_yimi/) 转载请注明谢谢合作。关键词trie trie树 数据结构 前几天学习了并查集和trie树这里总结一下trie。 本文讨论一棵最简单的trie树基于英文26个字母组成的字符串讨论插入字符串、判断前缀是否存在、查找字符串等基本操作至于trie树的删除单个节点实在是少见故在此不做详解。l Trie原理Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。l Trie性质好多人说trie的根节点不包含任何字符信息我所习惯的trie根节点却是包含信息的而且认为这样也方便下面说一下它的性质 (基于本文所讨论的简单trie树)1. 字符的种数决定每个节点的出度即branch数组(空间换时间思想)2. branch数组的下标代表字符相对于a的相对位置3. 采用标记的方法确定是否为字符串。4. 插入、查找的复杂度均为O(len),len为字符串长度l Trie的示意图如图所示该trie树存有abc、d、da、dda四个字符串如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULLl TrieTrie的优点举例已知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为什么不能将建立与查询同时执行例如有串911911456输入如果要同时执行建立与查询过程就是查询911没有然后存入9、91、911查询911456没有然后存入9114、91145、911456而程序没有记忆功能并不知道911在输入数据中出现过。所以用hash必须先存入所有子串然后for循环查询。而trie树便可以存入911后已经记录911为出现的字符串在存入911456的过程中就能发现而输出答案倒过来亦可以先存入911456在存入911时当指针指向最后一个1时程序会发现这个1已经存在说明911必定是某个字符串的前缀该思想是我在做pku上的3630中发现的详见本文配套的“入门练习”。l Trie的简单实现(插入、查询) 1 2#include iostream 3using namespace std; 4 5const int branchNum 26; //声明常量 6int i; 7 8struct Trie_node 9{10 bool isStr; //记录此处是否构成一个串。11 Trie_node *next[branchNum];//指向各个子树的指针,下标0-25代表26字符12 Trie_node():isStr(false)13 {14 memset(next,NULL,sizeof(next));15 }16};1718class Trie19{20public:21 Trie();22 void insert(const char* word);23 bool search(char* word); 24 void deleteTrie(Trie_node *root);25private:26 Trie_node* root;27};2829Trie::Trie()30{31 root new Trie_node();32}3334void Trie::insert(const char* word)35{36 Trie_node *location root;37 while(*word)38 {39 if(location-next[*word-a] NULL)//不存在则建立40 {41 Trie_node *tmp new Trie_node();42 location-next[*word-a] tmp;43 } 44 location location-next[*word-a]; //每插入一步相当于有一个新串经过指针要向下移动45 word;46 }47 location-isStr true; //到达尾部,标记一个串48}4950bool Trie::search(char *word)51{52 Trie_node *location root;53 while(*word location)54 {55 location location-next[*word-a];56 word;57 }58 return(location!NULL location-isStr);59}6061void Trie::deleteTrie(Trie_node *root)62{63 for(i 0; i branchNum; i)64 {65 if(root-next[i] ! NULL)66 {67 deleteTrie(root-next[i]);68 }69 }70 delete root;71}7273void main() //简单测试74{75 Trie t;76 t.insert(a); 77 t.insert(abandon);78 char * c abandoned;79 t.insert(c);80 t.insert(abashed);81 if(t.search(abashed))82 printf(true\n);83} 转载于:https://www.cnblogs.com/MiYu/archive/2010/10/23/1859515.html
