特里簡介

你有沒有想過搜尋引擎是如何工作的？Google 如何在幾毫秒內為你提供數百萬的結果？位於數千英里外的龐大資料庫如何找到你正在搜尋的資訊並將其發回給你？這背後的原因不僅僅是使用更快的網際網路和超級計算機。一些令人著迷的搜尋演算法和資料結構在它背後起作用。其中一個是特里 。

Trie ，也稱為數字樹，有時稱為基數樹或字首樹 （因為它們可以通過字首搜尋），是一種搜尋樹 - 一種有序樹資料結構，用於儲存動態集或關聯陣列，其中鍵是通常是字串它是可以輕鬆實現的資料結構之一。假設你有一個龐大的數百萬字的資料庫。你可以使用 trie 來儲存這些資訊，搜尋這些單詞的複雜性僅取決於我們搜尋的單詞的長度。這意味著它不依賴於我們的資料庫有多大。這不是很棒嗎？

假設我們有一個包含這些詞的字典：

algo
algea
also
tom
to

我們希望將這個字典儲存在記憶體中，以便我們可以輕鬆找到我們正在尋找的單詞。其中一種方法涉及按字典順序排序單詞 - 現實生活中的詞典如何儲存單詞。然後我們可以通過二進位制搜尋找到這個詞。另一種方法是使用字首樹或 Trie ，簡而言之。 Trie 這個詞來自 Re trie val 這個詞。這裡， prefix 表示字串的字首，可以這樣定義：從字串的開頭開始可以建立的所有子字串都稱為字首。例如：‘c’，‘ca’，‘cat’都是字串’cat’的字首。

現在讓我們回到特里。顧名思義，我們將建立一棵樹。首先，我們有一個只有根的空樹：

我們會插入 ‘algo’ 這個詞。我們將建立一個新節點並命名這兩個節點之間的邊緣 ‘a’ 。從新節點開始，我們將建立另一個名為 ’l’的邊，並將其與另一個節點連線。這樣，我們將為 ‘g’ 和 ‘o’ 建立兩個新邊。請注意，我們不會在節點中儲存任何資訊。目前，我們只考慮從這些節點建立新邊。從現在開始，讓我們呼叫名為 ‘x’的邊 - edge-x

現在我們要新增 algea 這個詞。我們需要一個來自 root 的 edge-a ，我們已經擁有了它。所以我們不需要新增新的優勢。同樣，我們有一個從 ‘a’ 到 ’l’ 和 ’l’ 到 ‘g’ 的邊緣。這意味著 ‘alg’ 已經在特里。我們只會新增 edge-e 和 edge-a 。

我們將新增 也 這個詞。我們從 root 獲得字首 ‘al’ 。我們只會新增 ‘so’ 。

讓我們新增 ‘湯姆’ 。這一次，我們從 root 建立了一個新的邊緣，因為我們之前沒有建立任何 tom 的字首。

現在我們應該如何新增 ’to’ ？ ’to’ 完全是 ’tom’ 的字首，所以我們不需要新增任何邊緣。我們可以做的是，我們可以在某些節點中新增結束標記。我們將在那些至少完成一個單詞的節點中放置結束標記。綠色圓圈表示結束標記。trie 看起來像：

你可以輕鬆理解我們新增結束標記的原因。我們可以確定儲存在 trie 中的單詞。字元將位於邊緣，節點將包含結束標記。

現在你可能會問，儲存這樣的單詞的目的是什麼？比方說，你被要求在詞典中找到 ‘alice’ 這個詞。你將穿越特里。你將檢查是否存在來自 root 的 edge-a 。然後從 ‘a’ 檢查，如果有邊緣 l 。在那之後，你將找不到任何 edge-i ，所以你可以得出結論，字典中不存在 alice 這個詞。

如果要求你在字典中找到單詞 ‘alg’ ，你將遍歷 root-> a ， a-> l ， l-> g ，但最後你將找不到綠色節點。所以字典中不存在這個詞。如果你搜尋 tom ，你將最終進入綠色節點，這意味著該詞存在於詞典中。

複雜：

在 trie 中搜尋單詞所需的最大步驟數是我們要查詢的單詞的長度。複雜度為 O（長度） 。插入的複雜性是相同的。實現 trie 所需的記憶體量取決於實現。我們將在另一個例子中看到一個實現，我們可以在一個 trie 中儲存 10 個 6 個 字元（不是單詞，字母）。 ****

使用 Trie：

• 在字典中插入，刪除和搜尋單詞。
• 查明字串是否是另一個字串的字首。
• 要找出有多少個字串有一個共同的字首。
• 根據我們輸入的字首，建議我們手機中的聯絡人姓名。
• 找出兩個字串的’Longest Common Substring’。
• 使用最長的共同祖先找出兩個單詞的共同字首的長度