作者 |?神奕

來源 | 前端應(yīng)屆生

頭圖 | 下載于視覺中國

出品 | CSDN云計算（ID：CSDNcloud）

在計算機科學(xué)中，trie，又稱前綴樹或字典樹，是一種有序樹，用于保存關(guān)聯(lián)數(shù)組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定。一個節(jié)點的所有子孫都有相同的前綴，也就是這個節(jié)點對應(yīng)的字符串，而根節(jié)點對應(yīng)空字符串。

什么是Trie樹

Trie樹，又叫字典樹、前綴樹（Prefix Tree）、單詞查找樹?或?鍵樹，是一種多叉樹結(jié)構(gòu)。如下圖：

上圖是一棵Trie樹，表示了關(guān)鍵字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。從上圖可以歸納出Trie樹的基本性質(zhì)：

• 根節(jié)點不包含字符，除根節(jié)點外的每一個子節(jié)點都包含一個字符。

• 從根節(jié)點到某一個節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。

• 每個節(jié)點的所有子節(jié)點包含的字符互不相同。

通常在實現(xiàn)的時候，會在節(jié)點結(jié)構(gòu)中設(shè)置一個標(biāo)志，用來標(biāo)記該結(jié)點處是否構(gòu)成一個單詞（關(guān)鍵字）。

可以看出，Trie樹的關(guān)鍵字一般都是字符串，而且Trie樹把每個關(guān)鍵字保存在一條路徑上，而不是一個結(jié)點中。

另外，兩個有公共前綴的關(guān)鍵字，在Trie樹中前綴部分的路徑相同，所以Trie樹又叫做前綴樹（Prefix Tree）。

Trie樹的優(yōu)缺點

Trie樹的核心思想是空間換時間，利用字符串的公共前綴來減少無謂的字符串比較以達(dá)到提高查詢效率的目的。

優(yōu)點：

插入和查詢的效率很高，都為O(m)O(m)，其中?mm?是待插入/查詢的字符串的長度。

關(guān)于查詢，會有人說 hash 表時間復(fù)雜度是O(1)O(1)不是更快？但是，哈希搜索的效率通常取決于 hash 函數(shù)的好壞，若一個壞的 hash 函數(shù)導(dǎo)致很多的沖突，效率并不一定比Trie樹高。

Trie樹中不同的關(guān)鍵字不會產(chǎn)生沖突。

Trie樹只有在允許一個關(guān)鍵字關(guān)聯(lián)多個值的情況下才有類似hash碰撞發(fā)生。

Trie樹不用求 hash 值，對短字符串有更快的速度。通常，求hash值也是需要遍歷字符串的。

Trie樹可以對關(guān)鍵字按字典序排序。

缺點：

當(dāng) hash 函數(shù)很好時，Trie樹的查找效率會低于哈希搜索

空間消耗比較大。

Trie樹的應(yīng)用

1、字符串檢索

檢索/查詢功能是Trie樹最原始的功能。思路就是從根節(jié)點開始一個一個字符進行比較：

• 如果沿路比較，發(fā)現(xiàn)不同的字符，則表示該字符串在集合中不存在。

• 如果所有的字符全部比較完并且全部相同，還需判斷最后一個節(jié)點的標(biāo)志位（標(biāo)記該節(jié)點是否代表一個關(guān)鍵字）。

struct?trie_node {bool?isKey;???//?標(biāo)記該節(jié)點是否代表一個關(guān)鍵字trie_node?*children[26];?//?各個子節(jié)點? };

2、詞頻統(tǒng)計

Trie樹常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計 。

struct?trie_node {int?count;???//?記錄該節(jié)點代表的單詞的個數(shù)trie_node?*children[26];?//?各個子節(jié)點? };

思路：為了實現(xiàn)詞頻統(tǒng)計，我們修改了節(jié)點結(jié)構(gòu)，用一個整型變量count來計數(shù)。對每一個關(guān)鍵字執(zhí)行插入操作，若已存在，計數(shù)加1，若不存在，插入后count置1。

注意：第一、第二種應(yīng)用也都可以用 hash table 來做。

3、字符串排序

Trie樹可以對大量字符串按字典序進行排序，思路也很簡單：遍歷一次所有關(guān)鍵字，將它們?nèi)坎迦雝rie樹，樹的每個結(jié)點的所有兒子很顯然地按照字母表排序，然后先序遍歷輸出Trie樹中所有關(guān)鍵字即可。

4、前綴匹配

例如：找出一個字符串集合中所有以ab開頭的字符串。我們只需要用所有字符串構(gòu)造一個trie樹，然后輸出以a->b->開頭的路徑上的關(guān)鍵字即可。

trie樹前綴匹配常用于搜索提示。如當(dāng)輸入一個網(wǎng)址，可以自動搜索出可能的選擇。當(dāng)沒有完全匹配的搜索結(jié)果，可以返回前綴最相似的可能。

5、作為其他數(shù)據(jù)結(jié)構(gòu)和算法的輔助結(jié)構(gòu)

如后綴樹，AC自動機等。

Trie樹的實現(xiàn)

這里為了方便，我們假設(shè)所有的關(guān)鍵字都由 a-z 的字母組成。

下面是 trie 樹的一種典型實現(xiàn)：

#include?<iostream> #include?<string> using?namespace?std;#define?ALPHABET_SIZE?26typedef?struct?trie_node {int?count;???//?記錄該節(jié)點代表的單詞的個數(shù)trie_node?*children[ALPHABET_SIZE];?//?各個子節(jié)點? }*trie;trie_node*?create_trie_node() {trie_node*?pNode?=?new?trie_node();pNode->count?=?0;for(int?i=0;?i<ALPHABET_SIZE;?++i)pNode->children[i]?=?NULL;return?pNode; }void?trie_insert(trie?root,?char*?key) {trie_node*?node?=?root;char*?p?=?key;while(*p){if(node->children[*p-'a']?==?NULL){node->children[*p-'a']?=?create_trie_node();}node?=?node->children[*p-'a'];++p;}node->count?+=?1; }/***?查詢：不存在返回0，存在返回出現(xiàn)的次數(shù)*/? int?trie_search(trie?root,?char*?key) {trie_node*?node?=?root;char*?p?=?key;while(*p?&&?node!=NULL){node?=?node->children[*p-'a'];++p;}if(node?==?NULL)return?0;elsereturn?node->count; }int?main() {//?關(guān)鍵字集合char?keys[][8]?=?{"the",?"a",?"there",?"answer",?"any",?"by",?"bye",?"their"};trie?root?=?create_trie_node();//?創(chuàng)建trie樹for(int?i?=?0;?i?<?8;?i++)trie_insert(root,?keys[i]);//?檢索字符串char?s[][32]?=?{"Present?in?trie",?"Not?present?in?trie"};printf("%s?---?%s\n",?"the",?trie_search(root,?"the")>0?s[0]:s[1]);printf("%s?---?%s\n",?"these",?trie_search(root,?"these")>0?s[0]:s[1]);printf("%s?---?%s\n",?"their",?trie_search(root,?"their")>0?s[0]:s[1]);printf("%s?---?%s\n",?"thaw",?trie_search(root,?"thaw")>0?s[0]:s[1]);return?0; }

對于Trie樹，我們一般只實現(xiàn)插入和搜索操作。這段代碼可以用來檢索單詞和統(tǒng)計詞頻。

博文鏈接：

blog.csdn.net/lisonglisonglisong/article/details/45584721

CSDN協(xié)同行業(yè)大佬 打造13長熱門知識圖譜及IT成長路線 助力千萬IT人成長，快速實現(xiàn)職場進階！ 更多精彩推薦 ?經(jīng)典永不過時！重溫設(shè)計模式?PassMark 更新排行，蘋果 M1 殺瘋了?干貨！Redis集群工作原理解析點分享點收藏點點贊點在看

總結(jié)

以上是生活随笔為你收集整理的Trie 树是什么样的数据结构？有哪些应用场景？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。