如圖，每條路徑上保存一個字母，從根節點開始進行dfs，每遍歷到一個標記節點（圖中的紅點），從根節點到當前節點路徑上所有字母連起來即為一個單詞
上圖中存儲了 abc, abcd, b, bcd, efg, hij.
對于Trie樹主要有三種操作：
- 新建一個結點
- 插入一個單詞
- 在trie樹中查找單詞
trie樹中每次插入一個結點的時間復雜度是 O( strlen( str ) )
建立trie樹的時間復雜度為 O( ∑strlen( str[i] ) )
對于每個單詞，查詢的時間復雜度為 O( strlen( str ) )Templates:
Struct:
struct node
{
int flag; //The end of a word
node* next[26];
};
新建結點：
node* newnode()
{
node* p = new node;
p->flag = 0;
for( int i = 0; i < 26; i++ )
p->next[i] = NULL;
return p;
}
插入單詞：
void trie_insert( node* root, char* s )
{
node* p = root;
int len = strlen( s );
int tmp;
for( int i = 0; i < len; i++ )
{
tmp = s[i] - 'a';
if( p->next[tmp] == NULL )
p->next[tmp] = newnode();
p = p->next[tmp];
}
p->flag = 1;
}
查詢：
int trie_search( node* root, char* s )
{
node* p = root;
int len = strlen( s );
int tmp;
for( int i = 0; i < len; i++ )
{
tmp = s[i] - 'a';
if( p->next[tmp] == NULL ) //not matched
return 0;
p = p->next[tmp];
}
if( p->flag ) //match && it is a word which has been stored
return 1;
return 0;
}
posted on 2016-08-31 09:35
Vontroy 閱讀(391)
評論(0) 編輯 收藏 引用 所屬分類:
字符串