這章節會介紹一個專門來處理String的資料結構，Tries。

假如我們需要儲存String，並且要讓add, get等功能有效率，可以用什麼資料結構來儲存呢？

前面我們學過BST和Hash Table，其實都可以達到很不錯的效率。但有沒有辦法更快？

這時候就要來介紹一下Tries，Tries是從Retrieval Tree中間的字母擷取出來的，其原理如下：

Tries也是一種樹狀結構，只是不會限定是binary；可以發現它把一個String中的每個char都放成一個node，所以從root開始從第一個char走，當走到藍底的node時代表這是一個當前有儲存的String(ex: sad)，反之白底就是走到目前為止還不是有儲存的String(ex: sa)。

實際在實作Tries的時候會類似下面的做法，每個Node除了儲存自己代表的char和是否為一個String的結尾，下一個char的儲存方式不會是單純的Node，而會是一個包含所有char的Map，在相對應的char中再儲存下一個Node：

上面的表示方式有點不好看，之後的圖片會用以下的方式代表：

仔細思考就會發現原本Node儲存的char有點多餘，因為在DataIndexedCharMap中就可以得知是哪個char了。所以若把實作的概念帶進來，Tries會長得像以下這樣：

而這樣Tries的實作下，add跟get的方法效率會是如何？我們知道若用BST的話會是Θ(logN)，Hash Table若在能夠完全平均分佈在各個bucket的情況下會是Θ(1)，而Tries也會是Θ(1)，或者應該說是

Θ(L)，L是要存進的String的字母長度，但在asymptotics的分析中，常數項可以簡化為1。

剛剛的實作其實還不是完美的，因為我們會浪費很多記憶體空間去存DataIndexedCharMap字母需要佔用的坑，然後這些坑絕大部分都會是null！

能把DataIndexedCharMap的實作換掉嗎？其實也很容易，只要任何能夠實作Map的資料結構都能做到，比如BST和Hash Table：

但相對的肯定就會比原來搞一個容納所有字母的方法慢一點了，比如要儲存的String有L個字母，那應用BST的Tries效率是O(logL)，而Hash Table會是O(L)。

接下來要介紹Tries真正強大的地方了，它不只是儲存String能夠達到很好的效能，更可以在String的特別操作上擁有優勢，那就是處理prefix的能力！

首先我們來看一下若要有collect的功能可以怎麼搞：

我們可能會需要寫一個func叫做colHelp，它會幫我們判斷遍歷到的node是否為結尾，以及幫我們拼出目前為止的String：

所以走過”a”後就會是這樣，x[]中會放入”a”，然後下一個node呼叫的colHelp第一個參數會是”aw”：

以此類推，走遍所有node就可以完成collect方法。

剛剛只是暖胃用的湯，接下來是前菜，來看看keysWithPrefix怎麼做：

跟剛剛collect其實差不多，主要差在我們會先找到prefix的node在哪裡，然後以此為根基去找出所有相同prefix的String。

湯跟前菜吃完了，要進入主菜囉！

為什麼要討論什麼prefix的問題勒？是因為prefix可以做到一個很酷的功能，那就是auto complete！我們在估狗搜尋的時候，常常只打出前幾個字，下面就會跳出一排相關的搜尋選項，這個功能就是auto complete。

要做到這個功能，除了剛剛討論的prefix演算法外，只要在外加上一個每個String的權重值，就可以做到了：

只是這樣會有一個致命的缺點，那就是萬一我們所有相同prefix的String有好幾百萬幾千萬個，那就效率很差了。

所以除了有每個String的權重值外，只要多加上相同prefix當前最佳權重值是多少，那就可以解決要找出所有相同prefix的String後再找出前幾權重值，直接把最佳權重值記錄下來並比較即可：

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License