什麼是字首樹——打開了我的新思路

本文轉載自【微信公眾號： 五角錢的程式設計師 ，ID:xianglin965】

來自專輯

美團面試面經真題

點選上方“五角錢的程式設計師”，選擇“設為星標”

第一時間關注技術乾貨！

一起

學習、成長、溫情的熱愛生活

今天繼續來講面試，已經出了將近十個美團java一面真題系列文章了，今天來講一講字首樹，相信大多數小夥伴對這個字首樹是很陌生的，有些甚至都沒有聽說過“字首樹”這個詞，說實話我也是看面經才知道這個詞的

1。 字首樹的概述

字首樹又名字典樹，單詞查詢樹，Trie樹，是一種多路樹形結構，是雜湊樹的變種，和hash效率有一拼，是一種用於快速檢索的多叉樹結構。

典型應用是用於統計和排序大量的字串（但不僅限於字串），所以經常被搜尋引擎系統用於文字詞頻統計。它的優點是：最大限度地減少無謂的字串比較，查詢效率比雜湊表高。

Trie的核心思想是空間換時間。利用字串的公共字首來降低查詢時間的開銷以達到提高效率的目的。

Trie樹也有它的缺點，Trie樹的記憶體消耗非常大。

性質：不同字串的相同字首只儲存一份。

操作：查詢，插入，刪除。

舉個栗子

：給出一組單詞，inn， int， at， age， adv，ant， adv 我們可以得到下面的Trie：

從上面可以發現一些Trie樹的特性：

如要查詢int，順著路徑i -> in -> int就找到了。

1）根節點不包含字元，除根節點外的每一個子節點都包含一個字元。

2）從根節點到某一節點的路徑上的字元連線起來，就是該節點對應的字串。

3）每個節點的所有子節點包含的字元都不相同。

4）每條邊對應一個字母。每個節點對應一項字首。葉節點對應最長字首，即單詞本身。

單詞inn與單詞int有共同的字首“in”， 因此他們共享左邊的一條分支，root->i->in。同理，ate， age， adv， 和ant共享字首“a”，所以他們共享從根節點到節點“a”的邊。

查詢操縱非常簡單

。

比搭建Trie的基本演算法也很簡單，無非是逐一把每則單詞的每個字母插入Trie。插入前先看字首是否存在。如果存在，就共享，否則建立對應的節點和邊。比如要插入單詞add，就有下面幾步：

考察字首“a”，發現邊a已經存在。於是順著邊a走到節點a。

考察剩下的字串“dd”的字首“d”，發現從節點a出發，已經有邊d存在。於是順著邊d走到節點ad

考察最後一個字元“d”，這下從節點ad出發沒有邊d了，於是建立節點ad的子節點add，並把邊ad->add標記為d。

2。 字首樹的應用場景

（1）字串的快速檢索

字典樹的查詢時間複雜度是O（logL），L是字串的長度。所以效率還是比較高的。字典樹的效率比hash表高。

hash表：

透過hash函式把所有的單詞分別hash成key值，查詢的時候直接透過hash函式即可，都知道hash表的效率是非常高的為O（1），當然這是對於如果我們hash函式選取的好，計算量少，且衝突少，那單詞查詢速度肯定是非常快的。那如果hash函式的計算量相對大呢，且衝突律高呢？這些都是要考慮的因素。

還有就是hash表不支援動態查詢，什麼叫動態查詢，當我們要查詢單詞apple時，hash表必須等待使用者把單詞apple輸入完畢才能hash查詢。當你輸入到appl時肯定不可能hash吧。

字典樹（tries樹）：

對於單詞查詢這種，還是用字典樹比較好，但也是有前提的，空間大小允許，字典樹的空間相比較hash還是比較浪費的，畢竟hash可以用bit陣列。

（2）字串排序

從上圖我們很容易看出單詞是排序的，先遍歷字母序在前面。

減少了沒必要的公共子串。

（3）最長公共字首

inn和int的最長公共字首是in，遍歷字典樹到字母n時，此時這些單詞的公共字首是in。

（4）自動匹配字首顯示字尾

我們使用辭典或者是搜尋引擎的時候，輸入appl，後面會自動顯示一堆字首是appl的東東吧。

那麼有可能是透過字典樹實現的，前面也說了字典樹可以找到公共字首，我們只需要把剩餘的字尾遍歷顯示出來即可。

3。 字首樹的java實現

節點

import java。util。Arrays；

public class TreeNode{

//經過這個節點的字串的個數（以這個節點為字首的字串的個數）

public int path；

//以這個節點結束的字串的個數（有多少個字串有這條路徑的char組成）

public int end；

//對應著小寫的a-z的26個字母（如果要更多可以使用hashmap

public TreeNode［］ next；

public TreeNode（）{

path =0；

end =0；

next =new TreeNode［26］；

}

@Override

public StringtoString（） {

return “TreeNode{” +

“path=” + path +

“， end=” + end +

“， next=” + Arrays。toString（next） +

‘}’；

}

}

字首樹（增加，查詢字串數量，查詢字首數量）

public class TrieTree {

public TreeNode root；

public TrieTree（）{

root=new TreeNode（）；

}

/**在字首樹中插入字串

* 這種++的方法，導致，一個node，有多少個end，就有多少個相同的字串

* 一個node，有多少個path，就有多少個字串經過（root的path代表有多少個字串）（字串末尾的node的path也會++）

* @param string 被插入的字串（以前插入過的也可以插入）

*/

public void insertString（Stringstring）{

if（string==null||string。length（）==0）{

return；

}

int length=string。length（）；

TreeNode nowNode=root；

for（int i=0；i

char now=string。charAt（i）；

int index=now-‘a’；

//index為字元now所處的位置

if（nowNode。next［index］==null）{

nowNode。next［index］=new TreeNode（）；

}

//先對當前node的path++，再轉移到下一個node

nowNode。path++；

nowNode=nowNode。next［index］；

}

//在最後的node，path和end++

nowNode。path++；

nowNode。end++；

}

/**返回這個字首樹總共插入了多少個字串

* @return

*/

public int size（）{

return root。path；

}

/**字首樹查詢總共插入這個字串多少次，如果沒插入過，則返回0

* @param string

* @return

*/

public int getStringNum（Stringstring）{

if（string==null||string。length（）==0）{

return 0；

}

int length=string。length（）；

TreeNode nowNode=root；

for（int i=0；i

char now=string。charAt（i）；

int index=now-‘a’；

//如果沒有這個節點，說明不存在，直接返回0

if（nowNode。next［index］==null）{

return 0；

}

nowNode=nowNode。next［index］；

}

//此時nowNode已經處於最後一個節點

return nowNode。end；

}

/**字首樹查詢以這個字串為字首的字串總共多少個（包括以他為結尾的）

* @param string 字首

* @return

*/

public int getPrefixNum（Stringstring）{

if（string==null||string。length（）==0）{

return 0；

}

int length=string。length（）；

TreeNode nowNode=root；

for（int i=0；i

char now=string。charAt（i）；

int index=now-‘a’；

//如果沒有這個節點，說明字首不存在，直接返回0

if（nowNode。next［index］==null）{

return 0；

}

nowNode=nowNode。next［index］；

}

//此時nowNode已經處於字首的最後一個節點

return nowNode。path；

}

}

測試：

public class Main {

public static void main（String［］ args）{

TrieTree tree=new TrieTree（）；

tree。insertString（“aa”）；

tree。insertString（“aa”）；

tree。insertString（“ab”）；

tree。insertString（“ba”）；

//System。out。println（tree。root）；

//System。out。println（tree。size（））；

//System。out。println（tree。getStringNum（“aa”））；

//System。out。println（tree。getStringNum（“ab”））；

//System。out。println（tree。getStringNum（“ac”））；

System。out。println（tree。getPrefixNum（“a”））；

System。out。println（tree。getPrefixNum（“b”））；

System。out。println（tree。getPrefixNum（“c”））；

}

}

輸出：

本文轉載自【微信公眾號： 五角錢的程式設計師 ，ID:xianglin965】