[[349418]]

 前言

這次分享的Trie字典樹，是數(shù)據結構專題中的一個分支，認識了解Trie這種樹型數(shù)據結構，對構建算法與數(shù)據結構知識體系有一定的幫助。

我對Trie樹的理解：把字符串都串接起來，消滅不必要的存儲，利用的就是字符串的公共前綴。

其實對于它的理解，你理解了這句話即可👇

利用字符串的公共前綴來減少查詢時間，最大限度的減少無謂的字符串比較，查詢效率比哈希樹高。

如果你還不了解什么是Trie數(shù)據結構的話，或者知道一些，但是對于它具體是如何實現(xiàn)一個簡單Trie樹時，那么這篇文章可能適合你閱讀。

那么圍繞以下幾個點來展開介紹Trie樹👇

• 基本概念
• 基本性質
• 應用場景
• 2個例題

基本概念

首先，我們對Trie樹得做一些基本的了解。Trie樹中文名叫字典樹，前綴樹等，接下來我就以字典樹稱呼。

我們來看下維基百科對它的描述吧⬇️

在計算機科學中，trie，又稱前綴樹或字典樹，是一種有序樹，用于保存關聯(lián)數(shù)組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定。一個節(jié)點的所有子孫都有相同的前綴，也就是這個節(jié)點對應的字符串，而根節(jié)點對應空字符串。一般情況下，不是所有的節(jié)點都有對應的值，只有葉子節(jié)點和部分內部節(jié)點所對應的鍵才有相關的值。

樸實無華的描述，其實我們看一張圖就能看明白了~，我在網上找了一張不錯的圖，具體的出處，這里就不補充了，因為實在找不到原作者~

 

字典樹圖解1

這里需要說明的內容就是，一般而言，應該是用一個點來表示一個字符，這里為了更好的說明，所以我就是用邊來描述字符。

可以發(fā)現(xiàn)，這棵字典樹用邊來代表字母，而從根結點到樹上某一結點的路徑就代表了一個字符串。舉個例子， 1→2→6表示的就是字符串 aba 。

再比如，1→4→8構成的字符串是ca，那么如果在往下拓展的話，我們是不是有 caa,cab，那么他們都會經過1→4→8，這些路徑，說明他們是有一段公共的前綴，這個前綴的內容就是ca，說道這里，我們就知道字典樹利用的就是字符串的前綴來解決問題。

那么具體它有哪些性質的話，我們下文介紹一下~

基本性質

對于上述概念有了一定的理解后，我們接下來就看下Trie樹的基本性質。

可以根據這個，大體上分成三個點來說👇

1. 根節(jié)點不包含字符，除根節(jié)點外，每個節(jié)點只包含一個字符。
2. 從根節(jié)點到某一個節(jié)點，路徑上經過的字符連接起來，為該節(jié)點對應的字符串。
3. 每個節(jié)點的所有子節(jié)點包含的字符串不相同。

接下來我們可以稍微分析一下，可以結合一個圖來看看👇

我們通過拿how,hi,her,hello,so,see這6個字符串構造出來的就是下面圖這個樣子。

 

 

圖解Trie樹

 

第一個性質：

從圖中也可以看出，根節(jié)點是/, 代表的內容也就是空，其他的節(jié)點比如，根節(jié)點下一個層級，有 h和s，分別代表的是兩個字符。

第二個性質：

從根節(jié)點到某一個節(jié)點，路徑上經過的字符連接起來，為該節(jié)點對應的字符串。

比如how表示的就是一個字符串，hi,也表示的是一個字符串，可是你會不會好奇，he和hel為什么不能表示一個字符串呢?

當你想到這里的話，說明你已經看得很仔細，馬上就要掌握它了，確實，從圖中看，我們會發(fā)現(xiàn)有些節(jié)點顏色不同，這是因為，我們預定好以這個深色的節(jié)點代表當前是一個字符串的結尾，想一想，這樣子的作用是啥?

那么實際代碼中，我們應該如何去約定或者做個標記呢，其實只要設置一個標記位即可。

比如下面這樣子👇

const TrieNode = function () { 
  this.next = Object.create(null) 
  this.isEnd = false 
}; 

當前的isEnd變量就表示當前的節(jié)點是不是結束串，當isEnd為True時，表示從根節(jié)點開始，到這個字符，所構成的字符串是存在的，是一個完整的字符串。

第三個性質：

每個節(jié)點的所有子節(jié)點包含的字符串不相同。

很明顯，我們從根節(jié)點開始，依次往下走，會發(fā)現(xiàn)，每個節(jié)點下面的節(jié)點是不相同的，所以依次組成的字符串不可能相同。

應用場景

對Trie樹，有一定了解后，我們就可以看看它有哪些的實際應用場景了。

這里參考的是網上所提供的幾個點👇

在搜索引擎中關鍵詞提示，引擎會自動彈出匹配關鍵詞的下拉框，這種應用場景大家應該都很熟悉。

 

 

下拉框

 

 

那么應該如何利用一種高效的數(shù)據結構存儲呢，這里就符合字典樹的性質，所以可以利用字典樹來構造特定的數(shù)據，達到一種更加快速檢索的效果。

字符串檢索

事先將已知的一些字符串(字典)的有關信息保存到trie樹里，查找另外一些未知字符串是否出現(xiàn)過或者出現(xiàn)頻率，可以舉例子說明情況👇

• 1000萬字符串，其中有些是重復的，需要把重復的全部去掉，保留沒有重復的字符串。
• 給出N 個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現(xiàn)的順序寫出所有不在熟詞表中的生詞。

詞頻統(tǒng)計

給定很長的一個串，統(tǒng)計頻數(shù)出現(xiàn)次數(shù)最多情況，舉個例子👇

• 有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內存限制大小是1M。返回頻數(shù)最高的100個詞。
• 一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞，請給出思想，給出時間復雜度分析。

字符串最長公共前綴

到現(xiàn)在，我們應該知道，Trie樹利用多個字符串的公共前綴來節(jié)省存儲空間，當我們把大量字符串存儲到一棵trie樹上時，我們可以快速得到某些字符串的公共前綴，所以可以利用這個特點來解決一些前綴問題。

非要舉個例子的話，有個例子👇

• 給出N 個小寫英文字母串，以及Q 個詢問，即詢問某兩個串的最長公共前綴的長度是多少?

應用場景還是有很多的，剩下的可以自行去探索，接下來，我們通過實際的題目來看看，如何構造字典樹吧~

2個例子

接下來，我們通過二個題目作為例子，來看看字典樹在實際應用可以解決哪些問題👇

詞典中最長的單詞⭐

鏈接：詞典中最長的單詞

給出一個字符串數(shù)組words組成的一本英語詞典。從中找出最長的一個單詞，該單詞是由words詞典中其他單詞逐步添加一個字母組成。若其中有多個可行的答案，則返回答案中字典序最小的單詞。

若無答案，則返回空字符串。

示例 1：

輸入： 
words = ["w","wo","wor","worl", "world"] 
輸出："world" 
解釋：  
單詞"world"可由"w", "wo", "wor", 和 "worl"添加一個字母組成。 

示例 2：

輸入： 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] 
輸出："apple" 
解釋： 
"apply"和"apple"都能由詞典中的單詞組成。但是"apple"的字典序小于"apply"。 

提示：

這題無非就是找到一個最長的單詞，可以拆分成words數(shù)組中某一部分，最暴力的思路就是去枚舉每一項，但是這樣子的時間復雜度是巨大的， 這個時候，我們是不是可以思考一下，這個問題有哪些地方是共性的呢?

• 沒錯，就是前綴是相同的，從這點來看，是不是就可以利用這個前綴樹，把它數(shù)據存儲下來
• 然后遍歷一遍字典樹，只要這顆樹只有一個分支，則表示它有解，如果存在兩個分支以上的話，則無答案。

復雜度分析

這點應該很好理解，這里就跳過了。

這里的話，我的解法構造字典樹，當然了，也有其他的解法，這里就不展開了，可以看下我的代碼噢～

 

 

最長的串

 

 

代碼點這里☑️

其實你會發(fā)現(xiàn)，構造一個Trie樹的話，是很消耗空間的，有點空間換時間的意思，所以具體得根據實際的題目來解決問題。

實現(xiàn)Trie(前綴樹)⭐⭐

鏈接：實現(xiàn) Trie (前綴樹)

實現(xiàn)一個 Trie (前綴樹)，包含 insert, search, 和 startsWith 這三個操作。

示例:

Trie trie = new Trie(); 
trie.insert("apple"); 
trie.search("apple");   // 返回 true 
trie.search("app");     // 返回 false 
trie.startsWith("app"); // 返回 true 
trie.insert("app");    
trie.search("app");     // 返回 true 

說明:

• 你可以假設所有的輸入都是由小寫字母 a-z 構成的。
• 保證所有輸入均為非空字符串。

這個題目就是典型的寫Trie樹，對于第一次寫這個題目的話，如果沒有思路的話，可以嘗試先看看別人的代碼，看看基本的套路在哪里。

話不多說，可以參考這份代碼，可以看看如何構造一顆字典樹👇

 

 

leetcode-實現(xiàn)Trie樹

 

 

代碼點這里☑️

剩下的刪除操作，還有統(tǒng)計字符串出現(xiàn)的頻率，可以自己來實現(xiàn)一下，這個基本上不難，畫個圖，就知道如何實現(xiàn)啦～

題目是做不完的，做完這些題目后，希望你能對Trie字典樹有所認識，能對它有更加深入的理解~，接下來準備了四道題集，希望對你們有幫助~

詞典中最長的單詞

實現(xiàn) Trie (前綴樹)

單詞搜索 II

Loading question