當前位置:成語大全網 - 新華字典 - 鍵樹的概念

鍵樹的概念

如果壹個關鍵字可以表示成字符的序號,即字符串,那麽可以用鍵樹(keyword tree),又稱數字搜索樹(digital search tree)或字符樹,來表示這樣的字符串的集合。鍵樹又稱為數字查找樹(Digital Search Tree)或Trie樹(trie為retrieve中間4個字符),其結構受啟發於壹部大型字典的“書邊標目”。字典中標出首字母是 A,B,C,....Z的單詞所在頁,再對各部分標出第二字母為A,B,C,...Z的單詞所在的頁, ....等等。

鍵樹是壹種特殊的查找樹,它的某個節點不是包含壹個或多個關鍵字,而是只包含組成關鍵字的壹部分(字符或數字),比如:如果關鍵字是數值,則節點中只包含壹個數位;如果關鍵字是單詞,則節點中只包含壹個字母字符。

根結點不代表任何字符,根以下第壹層的結點對應於字符串的第壹個字符,第二層的結點對應於字符串的第二個字符……每個字符串可由壹個特殊的字符如“$”等作為字符串的結束符,用壹個葉子結點來表示該特殊字符。把從根到葉子的路徑上,所有結點(除根以外)對應的字符連接起來,就得到壹個字符串。因此,每個葉子結點對應壹個關鍵字。在葉子結點還可以包含壹個指針,指向該關鍵字所對應的元素。整個字符串集合中的字符串的數目等於葉子結點的數目。如果壹個集合中的關鍵字都具有這樣的字符串特性,那麽,該關鍵字集合就可采用這樣壹棵鍵樹來表示。事實上,還可以賦予“字符串”更廣泛的含義,它可以是任何類型的對象組成的串。常見鍵樹如圖所示: