（1）字典樹（Trie樹）

　　Trie是個簡單但實用的數據結構，通常用于實現字典查詢。我們做即時響應用戶輸入的AJAX搜索框時，就是Trie開始。本質上，Trie是一顆存儲多個字符串的樹。相鄰節點間的邊代表一個字符，這樣樹的每條分支代表一則子串，而樹的葉節點則代表完整的字符串。和普通樹不同的地方是，相同的字符串前綴共享同一條分支。還是例子最清楚。給出一組單詞，inn, int, at, age, adv, ant, 我們可以得到下面的Trie：

可以看出：

• 每條邊對應一個字母。
• 每個節點對應一項前綴。葉節點對應最長前綴，即單詞本身。
• 單詞inn與單詞int有共同的前綴“in”, 因此他們共享左邊的一條分支，root->i->in。同理，ate, age, adv, 和ant共享前綴"a"，所以他們共享從根節點到節點"a"的邊。
• 查詢非常簡單。比如要查找int，順著路徑i -> in -> int就找到了。
• 搭建Trie的基本算法也很簡單，無非是逐一把每則單詞的每個字母插入Trie。插入前先看前綴是否存在。如果存在，就共享，否則創建對應的節點和邊。比如要插入單詞add，就有下面幾步：
• 考察前綴"a"，發現邊a已經存在。于是順著邊a走到節點a。
• 考察剩下的字符串"dd"的前綴"d"，發現從節點a出發，已經有邊d存在。于是順著邊d走到節點ad
• 考察最后一個字符"d"，這下從節點ad出發沒有邊d了，于是創建節點ad的子節點add，并把邊ad->add標記為d。

（2）后綴樹

?　　所謂后綴樹，就是包含一則字符串所有后綴的壓縮了的字典樹。先說說后綴的定義。給定一長度為n的字符串S=S₁S₂..S_i..S_n，和整數i，1 <= i <= n，子串S_iS_i+1...S_n都是字符串S的后綴。以字符串S=XMADAMYX為例，它的長度為8，所以S[1..8], S[2..8], ... , S[8..8]都算S的后綴，我們一般還把空字串也算成后綴。這樣，我們一共有如下后綴。對于后綴S[i..n]，我們說這項后綴起始于i。

S[1..8], XMADAMYX， 也就是字符串本身，起始位置為1

S[2..8], MADAMYX，起始位置為2

S[3..8], ADAMYX，起始位置為3

S[4..8], DAMYX，起始位置為4

S[5..8], AMYX，起始位置為5

S[6..8], MYX，起始位置為6

S[7..8], YX，起始位置為7

S[8..8], X，起始位置為8

空字串。記為$。

所有這些后綴字符串組成一棵字典樹：

仔細觀察上圖，我們可以看到不少值得壓縮的地方。比如藍框標注的分支都是獨苗，沒有必要用單獨的節點同邊表示。如果我們允許任意一條邊里包含多個字母，就可以把這種沒有分叉的路徑壓縮到一條邊。另外每條邊已經包含了足夠的后綴信息，我們就不用再給節點標注字符串信息了。我們只需要在葉節點上標注上每項后綴的起始位置。于是我們得到下圖：

這樣的結構丟失了某些后綴。比如后綴X在上圖中消失了，因為它正好是字符串XMADAMYX的前綴。為了避免這種情況，我們也規定每項后綴不能是其它后綴的前綴。要解決這個問題其實挺簡單，在待處理的子串后加一個空字串就行了。例如我們處理XMADAMYX前，先把XMADAMYX變為 XMADAMYX$，于是就得到suffix tree。

這就形成一棵后綴樹了。關于如何建立一棵后綴樹，已有很成熟的算法，能在o(n)時間內解決。

（3）廣義后綴樹

　　傳統的后綴樹只能處理一個單詞的所有后綴。廣義后綴樹存儲任意多個單詞的所有后綴。例如字符串“abab”和“baba”，首先將它們使用特殊結束符鏈接起來，如表示成“abab$baba#”,然后求連接后的新字符的后綴樹，遍歷所得后綴樹，如遇到特殊字符，如“$”,"#"等則去掉以該節點為跟的子樹，最后所得后綴樹即為原字符串組的廣義后綴樹。其實質是將兩個字符串的所有后綴，即：abab$,bab$,ab$,b$,baba#,aba#,ba#,a#,組成字典樹，再進行壓縮處理。廣義后綴樹的一個常應用就是判斷兩個字符串的相識度。

總結

以上是生活随笔為你收集整理的字典树(trie树)、后缀树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。