trieツリー

作者:yx_th 000記事ソース:Cherish_yimi(http://www.cnblogs.com/cherish_yimi/)転載は明記してください.ご協力ありがとうございます.キーワード:trie trieツリーデータ構造
先日勉強してセットとtrieツリーを調べましたが、ここでtrieをまとめます.本文は1本の最も簡単な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の4つの文字列が格納され、文字列であればノードの末尾にマークされます.後続文字のないbranchブランチがNULLl TrieTrieを指す利点の例
小文字からなる平均長さが10のn個の単語が知られており、ある列が別の列である接頭辞サブ列が存在するか否かを判断する.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はなぜ確立とクエリーを同時に実行できないのかを説明します.例えば、シリアルがあります.91911456入力があります.もし同時に確立とクエリーを実行するなら、プロセスはクエリー911で、いいえ、それから9、91、911で、クエリー911456で、それから9114、91145、911456ではありません.プログラムは記憶機能がなく、911が入力データに現れたことを知りません.したがってhashでは、すべてのサブストリングを格納し、forループクエリを使用する必要があります.
trieツリーは、911に格納した後、911が現れた文字列であることを記録し、911456に格納する過程で発見して答えを出力することができる.逆にしてもいいです.まず911456に保存して、911に保存する時、ポインタが最後の1を指している時、プログラムはこの1がすでに存在していることを発見して、911が必ずある文字列の接頭辞であることを説明して、この思想は私がpkuの上の3630の中で発見したので、詳しくは本文のセットの“入門の練習”を参照してください.
l Trieの簡単な実現(挿入、照会)
 


View Code

 1 /*
 2 trie ：
 3   trie             
 4 */ 
 5 #include<iostream>
 6 using namespace std;
 7 
 8 struct trie
 9 {
10    bool is;//         
11    trie *next[26];//     26    
12    trie():is(false)
13     {
14       memset(next,0,sizeof(next));
15     }
16 };
17 
18 trie *root;
19 
20 void insert(const char *word)
21 {
22   trie *p=root;
23   while(*word)
24   {
25     if(p->next[*word-'a']==NULL)//               
26      {
27         trie *temp=new trie();
28         p->next[*word-'a']=temp;
29      } 
30      p=p->next[*word-'a'];
31      word++;
32   }
33   p->is=true;//                     
34 }
35 
36 int search(const char *word)
37 {
38    trie *p=root;
39    while(*word&&p)
40    {
41      p=p->next[*word-'a'];
42      word++;
43    }
44   return (p&&p->is);//         word    p!=null    P->is！=0   
45 }                    //              p                
46 
47 void deletet(trie *root)
48 {
49     int i;
50     for(i=0;i<26;++i)
51     {
52       if(root->next[i]!=NULL)
53        deletet(root->next[i]);//       
54     }
55     delete root;
56 }
57 
58 int main()
59 {
60    char ch[80];
61    int i;
62    root=new trie();
63    for(i=0;i<4;++i)//      
64     {
65       cin>>ch;
66       insert(ch);
67     }
68    while(1)//      
69    {
70      cin>>ch;
71      cout<<search(ch)<<endl;
72    }
73    system("pause");
74    return 0;
75 }