數(shù)據(jù)結(jié)構(gòu)與算法之美-35講Trie樹

特別備注

本系列非原創(chuàng)榜轿，文章原文摘自極客時間-數(shù)據(jù)結(jié)構(gòu)算法之美围辙，用于平常學習記錄。如有侵權(quán)动看，請聯(lián)系我刪除铃岔，謝謝茫孔！

搜索引擎的搜索關(guān)鍵詞提示功能隘蝎，我想你應(yīng)該不陌生吧晒哄？為了方便快速輸入睁宰，當你在搜索引擎的搜索框中肪获，輸入要搜索的文字的某一部分的時候，搜索引擎就會自動彈出下拉框柒傻，里面是各種關(guān)鍵詞提示孝赫。你可以直接從下拉框中選擇你要搜索的東西，而不用把所有內(nèi)容都輸入進去红符，一定程度上節(jié)省了我們的搜索時間青柄。

img

盡管這個功能我們幾乎天天在用，作為一名工程師违孝，你是否思考過，它是怎么實現(xiàn)的呢泳赋？它底層使用的是哪種數(shù)據(jù)結(jié)構(gòu)和算法呢雌桑？

像Google、百度這樣的搜索引擎祖今，它們的關(guān)鍵詞提示功能非常全面和精準校坑，肯定做了很多優(yōu)化，但萬變不離其宗千诬，底層最基本的原理就是今天要講的這種數(shù)據(jù)結(jié)構(gòu)：Trie樹耍目。

什么是“Trie樹”？

Trie樹徐绑，也叫“字典樹”邪驮。顧名思義，它是一個樹形結(jié)構(gòu)傲茄。它是一種專門處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)毅访，用來解決在一組字符串集合中快速查找某個字符串的問題。

當然盘榨，這樣一個問題可以有多種解決方法喻粹，比如散列表、紅黑樹草巡，或者我們前面幾節(jié)講到的一些字符串匹配算法守呜，但是，Trie樹在這個問題的解決上山憨，有它特有的優(yōu)點查乒。不僅如此，Trie樹能解決的問題也不限于此郁竟，我們一會兒慢慢分析侣颂。

現(xiàn)在，我們先來看下枪孩，Trie樹到底長什么樣子憔晒。

我舉個簡單的例子來說明一下藻肄。我們有6個字符串，它們分別是：how拒担，hi嘹屯，her，hello从撼，so州弟，see。我們希望在里面多次查找某個字符串是否存在低零。如果每次查找婆翔，都是拿要查找的字符串跟這6個字符串依次進行字符串匹配，那效率就比較低掏婶，有沒有更高效的方法呢啃奴？

這個時候，我們就可以先對這6個字符串做一下預(yù)處理雄妥，組織成Trie樹的結(jié)構(gòu)最蕾，之后每次查找，都是在Trie樹中進行匹配查找老厌。Trie樹的本質(zhì)瘟则，就是利用字符串之間的公共前綴，將重復(fù)的前綴合并在一起枝秤。最后構(gòu)造出來的就是下面這個圖中的樣子醋拧。

img

其中，根節(jié)點不包含任何信息淀弹。每個節(jié)點表示一個字符串中的字符趁仙，從根節(jié)點到紅色節(jié)點的一條路徑表示一個字符串（注意：紅色節(jié)點并不都是葉子節(jié)點）。

為了讓你更容易理解Trie樹是怎么構(gòu)造出來的垦页，我畫了一個Trie樹構(gòu)造的分解過程雀费。構(gòu)造過程的每一步，都相當于往Trie樹中插入一個字符串痊焊。當所有字符串都插入完成之后盏袄，Trie樹就構(gòu)造好了。

img

當我們在Trie樹中查找一個字符串的時候薄啥，比如查找字符串“her”辕羽，那我們將要查找的字符串分割成單個的字符h，e垄惧，r刁愿，然后從Trie樹的根節(jié)點開始匹配。如圖所示到逊，綠色的路徑就是在Trie樹中匹配的路徑铣口。

img

如果我們要查找的是字符串“he”呢滤钱？我們還用上面同樣的方法，從根節(jié)點開始脑题，沿著某條路徑來匹配件缸，如圖所示，綠色的路徑叔遂，是字符串“he”匹配的路徑他炊。但是，路徑的最后一個節(jié)點“e”并不是紅色的已艰。也就是說痊末，“he”是某個字符串的前綴子串，但并不能完全匹配任何字符串哩掺。

img

如何實現(xiàn)一棵Trie樹凿叠？

知道了Trie樹長什么樣子，我們現(xiàn)在來看下疮丛，如何用代碼來實現(xiàn)一個Trie樹幔嫂。

從剛剛Trie樹的介紹來看辆它，Trie樹主要有兩個操作誊薄，一個是將字符串集合構(gòu)造成Trie樹。這個過程分解開來的話锰茉，就是一個將字符串插入到Trie樹的過程呢蔫。另一個是在Trie樹中查詢一個字符串。

了解了Trie樹的兩個主要操作之后飒筑，我們再來看下片吊，如何存儲一個Trie樹？

從前面的圖中协屡，我們可以看出俏脊，Trie樹是一個多叉樹。我們知道肤晓，二叉樹中爷贫，一個節(jié)點的左右子節(jié)點是通過兩個指針來存儲的，如下所示Java代碼补憾。那對于多叉樹來說漫萄，我們怎么存儲一個節(jié)點的所有子節(jié)點的指針呢？

class BinaryTreeNode {
  char data;
  BinaryTreeNode left;
  BinaryTreeNode right;  
}

我先介紹其中一種存儲方式盈匾，也是經(jīng)典的存儲方式腾务，大部分數(shù)據(jù)結(jié)構(gòu)和算法書籍中都是這么講的。還記得我們前面講到的散列表嗎削饵？借助散列表的思想岩瘦，我們通過一個下標與字符一一映射的數(shù)組未巫，來存儲子節(jié)點的指針。這句話稍微有點抽象担钮，不怎么好懂橱赠，我畫了一張圖你可以看看。

img

假設(shè)我們的字符串中只有從a到z這26個小寫字母箫津，我們在數(shù)組中下標為0的位置狭姨，存儲指向子節(jié)點a的指針，下標為1的位置存儲指向子節(jié)點b的指針苏遥，以此類推饼拍，下標為25的位置，存儲的是指向的子節(jié)點z的指針田炭。如果某個字符的子節(jié)點不存在师抄，我們就在對應(yīng)的下標的位置存儲null。

class TrieNode {
  char data;
  TrieNode children[26];
}

當我們在Trie樹中查找字符串的時候教硫，我們就可以通過字符的ASCII碼減去“a”的ASCII碼叨吮，迅速找到匹配的子節(jié)點的指針。比如瞬矩，d的ASCII碼減去a的ASCII碼就是3茶鉴，那子節(jié)點d的指針就存儲在數(shù)組中下標為3的位置中。

描述了這么多景用，有可能你還是有點懵涵叮，我把上面的描述翻譯成了代碼，你可以結(jié)合著一塊看下伞插，應(yīng)該有助于你理解割粮。

public class Trie {
  private TrieNode root = new TrieNode('/'); // 存儲無意義字符

  // 往Trie樹中插入一個字符串
  public void insert(char[] text) {
    TrieNode p = root;
    for (int i = 0; i < text.length; ++i) {
      int index = text[i] - 'a';
      if (p.children[index] == null) {
        TrieNode newNode = new TrieNode(text[i]);
        p.children[index] = newNode;
      }
      p = p.children[index];
    }
    p.isEndingChar = true;
  }

  // 在Trie樹中查找一個字符串
  public boolean find(char[] pattern) {
    TrieNode p = root;
    for (int i = 0; i < pattern.length; ++i) {
      int index = pattern[i] - 'a';
      if (p.children[index] == null) {
        return false; // 不存在pattern
      }
      p = p.children[index];
    }
    if (p.isEndingChar == false) return false; // 不能完全匹配，只是前綴
    else return true; // 找到pattern
  }

  public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
    public boolean isEndingChar = false;
    public TrieNode(char data) {
      this.data = data;
    }
  }
}

Trie樹的實現(xiàn)媚污，你現(xiàn)在應(yīng)該搞懂了∫ㄆ埃現(xiàn)在，我們來看下耗美，在Trie樹中京髓，查找某個字符串的時間復(fù)雜度是多少？

如果要在一組字符串中幽歼，頻繁地查詢某些字符串朵锣，用Trie樹會非常高效。構(gòu)建Trie樹的過程甸私，需要掃描所有的字符串诚些，時間復(fù)雜度是O(n)（n表示所有字符串的長度和）。但是一旦構(gòu)建成功之后，后續(xù)的查詢操作會非常高效诬烹。

每次查詢時妇拯，如果要查詢的字符串長度是k壶唤，那我們只需要比對大約k個節(jié)點曲楚，就能完成查詢操作裂七。跟原本那組字符串的長度和個數(shù)沒有任何關(guān)系。所以說家破，構(gòu)建好Trie樹后颜说，在其中查找字符串的時間復(fù)雜度是O(k)，k表示要查找的字符串的長度汰聋。

Trie樹真的很耗內(nèi)存嗎门粪？

前面我們講了Trie樹的實現(xiàn)，也分析了時間復(fù)雜度∨肜В現(xiàn)在你應(yīng)該知道玄妈，Trie樹是一種非常獨特的、高效的字符串匹配方法髓梅。但是拟蜻，關(guān)于Trie樹，你有沒有聽過這樣一種說法：“Trie樹是非常耗內(nèi)存的枯饿，用的是一種空間換時間的思路”酝锅。這是什么原因呢？

剛剛我們在講Trie樹的實現(xiàn)的時候鸭你，講到用數(shù)組來存儲一個節(jié)點的子節(jié)點的指針屈张。如果字符串中包含從a到z這26個字符擒权，那每個節(jié)點都要存儲一個長度為26的數(shù)組袱巨，并且每個數(shù)組存儲一個8字節(jié)指針（或者是4字節(jié)，這個大小跟CPU碳抄、操作系統(tǒng)愉老、編譯器等有關(guān)）。而且剖效，即便一個節(jié)點只有很少的子節(jié)點嫉入，遠小于26個，比如3璧尸、4個咒林，我們也要維護一個長度為26的數(shù)組。

我們前面講過爷光，Trie樹的本質(zhì)是避免重復(fù)存儲一組字符串的相同前綴子串垫竞，但是現(xiàn)在每個字符（對應(yīng)一個節(jié)點）的存儲遠遠大于1個字節(jié)。按照我們上面舉的例子，數(shù)組長度為26欢瞪，每個元素是8字節(jié)活烙，那每個節(jié)點就會額外需要26*8=208個字節(jié)。而且這還是只包含26個字符的情況遣鼓。

如果字符串中不僅包含小寫字母啸盏，還包含大寫字母、數(shù)字骑祟、甚至是中文回懦，那需要的存儲空間就更多了。所以次企，也就是說粉怕，在某些情況下，Trie樹不一定會節(jié)省存儲空間抒巢。在重復(fù)的前綴并不多的情況下贫贝，Trie樹不但不能節(jié)省內(nèi)存，還有可能會浪費更多的內(nèi)存蛉谜。

當然稚晚，我們不可否認，Trie樹盡管有可能很浪費內(nèi)存型诚，但是確實非常高效客燕。那為了解決這個內(nèi)存問題，我們是否有其他辦法呢狰贯？

我們可以稍微犧牲一點查詢的效率也搓，將每個節(jié)點中的數(shù)組換成其他數(shù)據(jù)結(jié)構(gòu)，來存儲一個節(jié)點的子節(jié)點指針涵紊。用哪種數(shù)據(jù)結(jié)構(gòu)呢傍妒？我們的選擇其實有很多，比如有序數(shù)組摸柄、跳表颤练、散列表、紅黑樹等驱负。

假設(shè)我們用有序數(shù)組嗦玖，數(shù)組中的指針按照所指向的子節(jié)點中的字符的大小順序排列。查詢的時候跃脊，我們可以通過二分查找的方法宇挫，快速查找到某個字符應(yīng)該匹配的子節(jié)點的指針。但是酪术，在往Trie樹中插入一個字符串的時候器瘪，我們?yōu)榱司S護數(shù)組中數(shù)據(jù)的有序性，就會稍微慢了點。

替換成其他數(shù)據(jù)結(jié)構(gòu)的思路是類似的娱局，這里我就不一一分析了彰亥，你可以結(jié)合前面學過的內(nèi)容，自己分析一下衰齐。

實際上任斋，Trie樹的變體有很多，都可以在一定程度上解決內(nèi)存消耗的問題耻涛。比如废酷，縮點優(yōu)化，就是對只有一個子節(jié)點的節(jié)點抹缕，而且此節(jié)點不是一個串的結(jié)束節(jié)點澈蟆，可以將此節(jié)點與子節(jié)點合并。這樣可以節(jié)省空間卓研，但卻增加了編碼難度趴俘。這里我就不展開詳細講解了，你如果感興趣奏赘，可以自行研究下寥闪。

img

Trie樹與散列表、紅黑樹的比較

實際上磨淌，字符串的匹配問題疲憋，籠統(tǒng)上講，其實就是數(shù)據(jù)的查找問題梁只。對于支持動態(tài)數(shù)據(jù)高效操作的數(shù)據(jù)結(jié)構(gòu)缚柳，我們前面已經(jīng)講過好多了，比如散列表搪锣、紅黑樹秋忙、跳表等等。實際上淤翔，這些數(shù)據(jù)結(jié)構(gòu)也可以實現(xiàn)在一組字符串中查找字符串的功能翰绊。我們選了兩種數(shù)據(jù)結(jié)構(gòu)佩谷，散列表和紅黑樹旁壮，跟Trie樹比較一下，看看它們各自的優(yōu)缺點和應(yīng)用場景谐檀。

在剛剛講的這個場景抡谐，在一組字符串中查找字符串，Trie樹實際上表現(xiàn)得并不好桐猬。它對要處理的字符串有及其嚴苛的要求麦撵。

第一，字符串中包含的字符集不能太大。我們前面講到免胃，如果字符集太大音五，那存儲空間可能就會浪費很多。即便可以優(yōu)化羔沙，但也要付出犧牲查詢躺涝、插入效率的代價。

第二扼雏，要求字符串的前綴重合比較多坚嗜，不然空間消耗會變大很多。

第三诗充，如果要用Trie樹解決問題苍蔬，那我們就要自己從零開始實現(xiàn)一個Trie樹，還要保證沒有bug蝴蜓，這個在工程上是將簡單問題復(fù)雜化碟绑，除非必須，一般不建議這樣做茎匠。

第四蜈敢，我們知道，通過指針串起來的數(shù)據(jù)塊是不連續(xù)的汽抚，而Trie樹中用到了指針抓狭，所以，對緩存并不友好造烁，性能上會打個折扣否过。

綜合這幾點，針對在一組字符串中查找字符串的問題惭蟋，我們在工程中苗桂，更傾向于用散列表或者紅黑樹。因為這兩種數(shù)據(jù)結(jié)構(gòu)告组，我們都不需要自己去實現(xiàn)煤伟，直接利用編程語言中提供的現(xiàn)成類庫就行了。

講到這里木缝，你可能要疑惑了便锨，講了半天，我對Trie樹一通否定我碟，還讓你用紅黑樹或者散列表放案，那Trie樹是不是就沒用了呢？是不是今天的內(nèi)容就白學了呢矫俺？

實際上吱殉，Trie樹只是不適合精確匹配查找掸冤，這種問題更適合用散列表或者紅黑樹來解決。Trie樹比較適合的是查找前綴匹配的字符串友雳，也就是類似開篇問題的那種場景稿湿。

解答開篇

Trie樹就講完了，我們來看下開篇提到的問題：如何利用Trie樹押赊，實現(xiàn)搜索關(guān)鍵詞的提示功能缎罢？

我們假設(shè)關(guān)鍵詞庫由用戶的熱門搜索關(guān)鍵詞組成。我們將這個詞庫構(gòu)建成一個Trie樹考杉。當用戶輸入其中某個單詞的時候策精，把這個詞作為一個前綴子串在Trie樹中匹配。為了講解方便崇棠，我們假設(shè)詞庫里只有hello咽袜、her、hi枕稀、how询刹、so、see這6個關(guān)鍵詞萎坷。當用戶輸入了字母h的時候凹联，我們就把以h為前綴的hello、her哆档、hi蔽挠、how展示在搜索提示框內(nèi)。當用戶繼續(xù)鍵入字母e的時候瓜浸，我們就把以he為前綴的hello澳淑、her展示在搜索提示框內(nèi)。這就是搜索關(guān)鍵詞提示的最基本的算法原理插佛。

img

不過杠巡，我講的只是最基本的實現(xiàn)原理，實際上雇寇，搜索引擎的搜索關(guān)鍵詞提示功能遠非我講的這么簡單氢拥。如果再稍微深入一點，你就會想到锨侯，上面的解決辦法遇到下面幾個問題：

• 我剛講的思路是針對英文的搜索關(guān)鍵詞提示嫩海，對于更加復(fù)雜的中文來說，詞庫中的數(shù)據(jù)又該如何構(gòu)建成Trie樹呢识腿？
• 如果詞庫中有很多關(guān)鍵詞出革，在搜索提示的時候，用戶輸入關(guān)鍵詞渡讼，作為前綴在Trie樹中可以匹配的關(guān)鍵詞也有很多骂束，如何選擇展示哪些內(nèi)容呢？
• 像Google這樣的搜索引擎成箫，用戶單詞拼寫錯誤的情況下展箱，Google還是可以使用正確的拼寫來做關(guān)鍵詞提示，這個又是怎么做到的呢蹬昌？

你可以先思考一下如何來解決混驰，如果不會也沒關(guān)系，這些問題皂贩，我們會在實戰(zhàn)篇里具體來講解栖榨。

實際上，Trie樹的這個應(yīng)用可以擴展到更加廣泛的一個應(yīng)用上明刷，就是自動輸入補全婴栽，比如輸入法自動補全功能、IDE代碼編輯器自動補全功能辈末、瀏覽器網(wǎng)址輸入的自動補全功能等等愚争。

內(nèi)容小結(jié)

今天我們講了一種特殊的樹，Trie樹挤聘。Trie樹是一種解決字符串快速匹配問題的數(shù)據(jù)結(jié)構(gòu)轰枝。如果用來構(gòu)建Trie樹的這一組字符串中，前綴重復(fù)的情況不是很多组去，那Trie樹這種數(shù)據(jù)結(jié)構(gòu)總體上來講是比較費內(nèi)存的鞍陨，是一種空間換時間的解決問題思路。

盡管比較耗費內(nèi)存从隆，但是對內(nèi)存不敏感或者內(nèi)存消耗在接受范圍內(nèi)的情況下湾戳，在Trie樹中做字符串匹配還是非常高效的，時間復(fù)雜度是O(k)广料，k表示要匹配的字符串的長度砾脑。

但是，Trie樹的優(yōu)勢并不在于艾杏，用它來做動態(tài)集合數(shù)據(jù)的查找韧衣，因為，這個工作完全可以用更加合適的散列表或者紅黑樹來替代购桑。Trie樹最有優(yōu)勢的是查找前綴匹配的字符串畅铭，比如搜索引擎中的關(guān)鍵詞提示功能這個場景，就比較適合用它來解決勃蜘，也是Trie樹比較經(jīng)典的應(yīng)用場景

特別備注

本系列非原創(chuàng)硕噩，文章原文摘自極客時間-數(shù)據(jù)結(jié)構(gòu)算法之美，用于平常學習記錄缭贡。如有侵權(quán)炉擅，請聯(lián)系我刪除辉懒，謝謝！