Trie樹既可用于一般的字典搜索，也可用于索引查找。對(duì)于給定的一個(gè)字符串a(chǎn)1,a2,a3,...,an.則
采用TRIE樹搜索經(jīng)過n次搜索即可完成一次查找。不過好像還是沒有B樹的搜索效率高，B樹搜索算法復(fù)雜度為logt(n+1/2).當(dāng)t趨向大，搜索效率變得高效。怪不得DB2的訪問內(nèi)存設(shè)置為虛擬內(nèi)存的一個(gè)PAGE大小，而且?guī)袚Q頻率降低，無需經(jīng)常的PAGE切換。
|
// trie.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//
#include "stdafx.h"
#include <stdio.h>
#include <iostream>
//#include <ciostream.h>
#include <string.h>
using namespace std;
const int num_chars = 26;
class Trie {
public:
Trie();
Trie(Trie& tr);
virtual ~Trie();
int trie_search(const char* word, char* entry ) const;
int insert(const char* word, const char* entry);
int remove(const char* word, char* entry);
protected:
struct Trie_node
{
char* data;
Trie_node* branch[num_chars];
Trie_node();
};
Trie_node* root;
};
Trie::Trie_node::Trie_node()
{
data = NULL;
for (int i=0; i<num_chars; ++i)
branch[i] = NULL;
}
Trie::Trie():root(NULL)
{
}
Trie::~Trie()
{
}
int Trie::trie_search(const char* word, char* entry ) const
{
int position = 0;
char char_code;
Trie_node *location = root;
while( location!=NULL && *word!=0 )
{
if (*word>='A' && *word<='Z')
char_code = *word-'A';
else if (*word>='a' && *word<='z')
char_code = *word-'a';
else return 0;
location = location->branch[char_code];
position++;
word++;
}
if ( location != NULL && location->data != NULL )
{
strcpy(entry,location->data);
return 1;
}
else return 0;
}
int Trie::insert(const char* word, const char* entry)
{
int result = 1, position = 0;
if ( root == NULL ) root = new Trie_node;
char char_code;
Trie_node *location = root;
while( location!=NULL && *word!=0 )
{
if (*word>='A' && *word<='Z')
char_code = *word-'A';
else if (*word>='a' && *word<='z')
char_code = *word-'a';
else return 0;
if( location->branch[char_code] == NULL )
location->branch[char_code] = new Trie_node;
location = location->branch[char_code];
position++;
word++;
}
if (location->data != NULL)
result = 0;
else {
location->data = new char[strlen(entry)+1];
strcpy(location->data, entry);
}
return result;
}
int main()
{
Trie t;
char entry[100];
t.insert("aa", "DET");
t.insert("abacus","NOUN");
t.insert("abalone","NOUN");
t.insert("abandon","VERB");
t.insert("abandoned","ADJ");
t.insert("abashed","ADJ");
t.insert("abate","VERB");
t.insert("this", "PRON");
if (t.trie_search("this", entry))
cout<<"'this' was found. pos: "<<entry<<endl;
if (t.trie_search("abate", entry))
cout<<"'abate' is found. pos: "<<entry<<endl;
if (t.trie_search("baby", entry))
cout<<"'baby' is found. pos: "<<entry<<endl;
else
cout<<"'baby' does not exist at all!"<<endl;
if (t.trie_search("aa", entry))
cout<<"'aa was found. pos: "<<entry<<endl;
}
|
10.3 Trie樹
當(dāng)關(guān)鍵碼是可變長(zhǎng)時(shí)，Trie樹是一種特別有用的索引結(jié)構(gòu)。
10.3.1 Trie樹的定義
Trie樹是一棵度 m ≥ 2 的樹，它的每一層分支不是靠整個(gè)關(guān)鍵碼的值來確定，而是由關(guān)鍵碼的一個(gè)分量來確定。
如下圖所示Trie樹，關(guān)鍵碼由英文字母組成。它包括兩類結(jié)點(diǎn)：元素結(jié)點(diǎn)和分支結(jié)點(diǎn)。元素結(jié)點(diǎn)包含整個(gè)key數(shù)據(jù)；分支結(jié)點(diǎn)有27個(gè)指針，其中有一個(gè)空白字符‘b’，用來終結(jié)關(guān)鍵碼；其它用來標(biāo)識(shí)‘a(chǎn)’, ‘b’,..., ‘z’等26個(gè)英文字母。
在第0層，所有的關(guān)鍵碼根據(jù)它們第0位字符, 被劃分到互不相交的27個(gè)類中。
因此，root→brch.link[i] 指向一棵子Trie樹，該子Trie樹上所包含的所有關(guān)鍵碼都是以第 i 個(gè)英文字母開頭。
若某一關(guān)鍵碼第 j 位字母在英文字母表中順序?yàn)?i ( i = 0, 1, ?, 26 ), 則它在Trie樹的第 j 層分支結(jié)點(diǎn)中從第 i 個(gè)指針向下找第 j+1 位字母所在結(jié)點(diǎn)。當(dāng)一棵子Trie樹上只有一個(gè)關(guān)鍵碼時(shí)，就由一個(gè)元素結(jié)點(diǎn)來代替。在這個(gè)結(jié)點(diǎn)中包含有關(guān)鍵碼，以及其它相關(guān)的信息，如對(duì)應(yīng)數(shù)據(jù)對(duì)象的存放地址等。
Trie樹的類定義：
const int MaxKeySize = 25; //關(guān)鍵碼最大位數(shù)
typedef struct { //關(guān)鍵碼類型
char ch[MaxKeySize]; //關(guān)鍵碼存放數(shù)組
int currentSize; //關(guān)鍵碼當(dāng)前位數(shù)
} KeyType;
class TrieNode { //Trie樹結(jié)點(diǎn)類定義
friend class Trie;
protected:
enum { branch, element } NodeType; //結(jié)點(diǎn)類型
union NodeType { //根據(jù)結(jié)點(diǎn)類型的兩種結(jié)構(gòu)
struct { //分支結(jié)點(diǎn)
int num; //本結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)
TrieNode *link[27]; //指針數(shù)組
} brch;
struct { //元素結(jié)點(diǎn)
KeyType key; //關(guān)鍵碼
recordNode *recptr; //指向數(shù)據(jù)對(duì)象指針
} elem;
}
}
class Trie { //Trie樹的類定義
private:
TrieNode *root, *current;
public:
RecordNode* Search ( const keyType & );
int Insert ( const KeyType & );
int Delete ( const KeyType & );
}
10.3.2 Trie樹的搜索
為了在Trie樹上進(jìn)行搜索，要求把關(guān)鍵碼分解成一些字符元素, 并根據(jù)這些字符向下進(jìn)行分支。
函數(shù) Search 設(shè)定 current = NULL, 表示不指示任何一個(gè)分支結(jié)點(diǎn), 如果 current 指向一個(gè)元素結(jié)點(diǎn) elem，則 current→elem.key 是 current 所指結(jié)點(diǎn)中的關(guān)鍵碼。
Trie樹的搜索算法：
RecordNode* Trie::Search ( const KeyType & x ) {
k = x.key;
concatenate ( k, ‘b’ );
current = root;
int i = 0; //掃描初始化
while ( current != NULL && current→NodeType != element && i <= x.ch[i] ) {
current = current→brch.link[ord (x.ch[i])];
i = i++;
};
if ( current != NULL && current→NodeType == element && current→elem.key == x )
return current→recptr;
else
return NULL;
}
經(jīng)驗(yàn)證，Trie樹的搜索算法在最壞情況下搜索的時(shí)間代價(jià)是 O(l)。其中, l 是Trie樹的層數(shù)(包括分支結(jié)點(diǎn)和元素結(jié)點(diǎn)在內(nèi))。
在用作索引時(shí)，Trie樹的所有結(jié)點(diǎn)都駐留在磁盤上。搜索時(shí)最多做 l 次磁盤存取。
當(dāng)結(jié)點(diǎn)駐留在磁盤上時(shí)，不能使用C++的指針 (pointer) 類型, 因?yàn)镃++不允許指針的輸入 / 輸出。在結(jié)點(diǎn)中的 link 指針可改用整型(integer) 實(shí)現(xiàn)。
10.3.3 在Trie樹上的插入和刪除
示例：插入關(guān)鍵碼bobwhite和bluejay。
a. 插入 x = bobwhite 時(shí)，首先搜索Trie樹尋找 bobwhite 所在的結(jié)點(diǎn)。
b. 如果找到結(jié)點(diǎn), 并發(fā)現(xiàn)該結(jié)點(diǎn)的 link[‘o’] = NULL。x不在Trie樹中, 可以在該處插入。插入結(jié)果參看圖。
c. 插入 x = bluejay時(shí)，用Trie樹搜索算法可找到包含有 bluebird 的元素結(jié)點(diǎn)，關(guān)鍵碼bluebird 和 bluejay 是兩個(gè)不同的值，它們?cè)诘?個(gè)字母處不匹配。從 Trie樹沿搜索路徑，在第4層分支。插入結(jié)果參看圖。
在Trie樹上插入bobwhite和bluejay后的結(jié)果 ：
示例：考慮在上圖所示Trie樹中刪除bobwhite。此時(shí)，只要將該結(jié)點(diǎn)link[‘o’]置為0 (NULL)即可，Trie樹的其它部分不需要改變。
考慮刪除 bluejay。刪除之后在標(biāo)記為δ3 的子Trie樹中只剩下一個(gè)關(guān)鍵碼，這表明可以刪去結(jié)點(diǎn)δ3 ，同時(shí)結(jié)點(diǎn) ρ 向上移動(dòng)一層。對(duì)結(jié)點(diǎn)δ2 和δ1 可以做同樣的工作，最后到達(dá)結(jié)點(diǎn)б。因?yàn)橐鸳?為根的子Trie樹中有多個(gè)關(guān)鍵碼，所以它不能刪去，令該結(jié)點(diǎn)link[‘l’] = ρ即可。
為便于Trie樹的刪除, 在每個(gè)分支結(jié)點(diǎn)中設(shè)置了一個(gè) num 數(shù)據(jù)成員，它記載了結(jié)點(diǎn)中子女的數(shù)目。
Trie,又稱單詞查找樹,是一種樹形結(jié)構(gòu)，用于保存大量的字符串。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來節(jié)約存儲(chǔ)空間。
性質(zhì)
它有3個(gè)基本性質(zhì)：
- 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。
- 從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
- 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。
例子
這是一個(gè)Trie結(jié)構(gòu)的例子：
在這個(gè)Trie結(jié)構(gòu)中，保存了t、to、te、tea、ten、i、in、inn這8個(gè)字符串，僅占用8個(gè)字節(jié)（不包括指針占用的空間）。
