圖解：數(shù)據(jù)結(jié)構(gòu)中的6種「樹(shù)」，大鵬問(wèn)你心中有數(shù)嗎？
數(shù)據(jù)結(jié)構(gòu)這門(mén)課程是計(jì)算機(jī)相關(guān)專業(yè)的基礎(chǔ)課，數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)、組織方式。
我們?cè)趯W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)候，會(huì)遇到各種各樣的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，比如堆棧、隊(duì)列、數(shù)組、鏈表、樹(shù)...這些基本的數(shù)據(jù)結(jié)構(gòu)類型有各自的特點(diǎn)，不同數(shù)據(jù)結(jié)構(gòu)適用于解決不同場(chǎng)景下的問(wèn)題。
樹(shù)形結(jié)構(gòu)相比數(shù)組、鏈表、堆棧這些數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，稍微復(fù)雜一點(diǎn)點(diǎn)，但樹(shù)形結(jié)構(gòu)可以用于解決很多實(shí)際問(wèn)題，因?yàn)楝F(xiàn)實(shí)世界事物之間的關(guān)系往往不是線性關(guān)聯(lián)的，而「樹(shù)」恰好適合描述這種非線性關(guān)系。
今天就帶大家一起學(xué)習(xí)下，數(shù)據(jù)結(jié)構(gòu)中的各種「樹(shù)」，這也是面試中經(jīng)常考察的內(nèi)容，手撕二叉樹(shù)是常規(guī)套路，對(duì)候選人也很有區(qū)分度，學(xué)完這篇文章，相信大家都會(huì)心中有「樹(shù)」了。
從樹(shù)說(shuō)起
什么是樹(shù)？現(xiàn)實(shí)中的樹(shù)大家都見(jiàn)過(guò)，在數(shù)據(jù)結(jié)構(gòu)中也有樹(shù)，此樹(shù)非彼樹(shù)，不過(guò)數(shù)據(jù)結(jié)構(gòu)的樹(shù)和現(xiàn)實(shí)中的樹(shù)在形態(tài)上確實(shí)有點(diǎn)相像。
樹(shù)是非線性的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合，它是由n個(gè)有限節(jié)點(diǎn)組成的具有層次關(guān)系的集合。在數(shù)據(jù)結(jié)構(gòu)中樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，那我們先來(lái)了解下，什么是線性與非線性數(shù)據(jù)結(jié)構(gòu)？
線性結(jié)構(gòu)
「線性結(jié)構(gòu)」是一個(gè)有序數(shù)據(jù)元素的集合。其中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的，常用的線性結(jié)構(gòu)有：線性表，棧，隊(duì)列，雙端隊(duì)列，數(shù)組，串。
可以想象，所謂的線性結(jié)構(gòu)數(shù)據(jù)組織形式，就像一條線段一樣筆直，元素之間首尾相接。比如現(xiàn)實(shí)中的火車進(jìn)站、食堂打飯排隊(duì)的隊(duì)列。
非線性結(jié)構(gòu)
簡(jiǎn)而言之，線性結(jié)構(gòu)的對(duì)立面就是「非線性結(jié)構(gòu)」。
樹(shù)
線性結(jié)構(gòu)中節(jié)點(diǎn)是首位相接一對(duì)一關(guān)系，在樹(shù)結(jié)構(gòu)中節(jié)點(diǎn)之間不再是簡(jiǎn)單的一對(duì)一關(guān)系，而是較為復(fù)雜的一對(duì)多的關(guān)系，一個(gè)節(jié)點(diǎn)可以與多個(gè)節(jié)點(diǎn)發(fā)生關(guān)聯(lián)，樹(shù)是一種層次化的數(shù)據(jù)組織形式，樹(shù)在現(xiàn)實(shí)中是可以找到例子的，比如現(xiàn)實(shí)中的族譜，親戚之間的關(guān)系是層次關(guān)聯(lián)的樹(shù)形關(guān)系。
數(shù)據(jù)結(jié)構(gòu)中的「樹(shù)」的名字由來(lái)，是因?yàn)槿绻压?jié)點(diǎn)之間的關(guān)系直觀展示出來(lái)，由于長(zhǎng)得和現(xiàn)實(shí)世界中的樹(shù)很像，由此得名。如圖：
樹(shù)的關(guān)鍵概念
人們對(duì)樹(shù)形結(jié)構(gòu)的研究比較深入，為了方便研究樹(shù)的各種性質(zhì)，抽象出了一些樹(shù)相關(guān)的概念，以便清晰簡(jiǎn)介的描述一顆樹(shù)。下面幾個(gè)基礎(chǔ)概念必須了解，否則你當(dāng)你刷LeetCode樹(shù)相關(guān)題目時(shí)候，或者面試官向你描述問(wèn)題時(shí)，你會(huì)連題目都看不懂事什么意思。
先來(lái)上一個(gè)圖解，下面的術(shù)語(yǔ)和概念對(duì)照著看，更容易理解。
?什么是節(jié)點(diǎn)的度？
?
度很好理解，直觀來(lái)說(shuō)，數(shù)一下節(jié)點(diǎn)有幾個(gè)分叉就說(shuō)這個(gè)節(jié)點(diǎn)的度是多少。
?什么是根節(jié)點(diǎn)？
?
在一顆樹(shù)形結(jié)構(gòu)中，最頂層的那個(gè)節(jié)點(diǎn)就是根節(jié)點(diǎn)了，所有的子節(jié)點(diǎn)都源自它發(fā)散開(kāi)來(lái)。
?什么是父節(jié)點(diǎn)？
?
樹(shù)的父子關(guān)系和現(xiàn)實(shí)中很相似，若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)。
?什么是葉子節(jié)點(diǎn)？
?
直觀來(lái)看葉子節(jié)點(diǎn)都位于樹(shù)的最底層，就是沒(méi)有分叉的節(jié)點(diǎn)，嚴(yán)格的定義是度為 0 的節(jié)點(diǎn)叫葉子節(jié)點(diǎn)。
?什么是節(jié)點(diǎn)的高度？
?
高度是從葉子節(jié)點(diǎn)開(kāi)始「自底向上」逐層累加的路徑長(zhǎng)度，樹(shù)葉的高度為 0（有些書(shū)上也說(shuō)是 0，不用糾結(jié)）
?什么是節(jié)點(diǎn)的深度？
?
深度是從根節(jié)點(diǎn)開(kāi)始「自頂向下」逐層累加的路徑長(zhǎng)度，根的深度為1（有些書(shū)上也說(shuō)是 0，問(wèn)題不大）
小技巧：高度和深度，一個(gè)從下往上數(shù)，一個(gè)從上往下數(shù)。
樹(shù)的特點(diǎn)
樹(shù)形數(shù)據(jù)結(jié)構(gòu)，具有以下的結(jié)構(gòu)特點(diǎn)：
每個(gè)節(jié)點(diǎn)都只有有限個(gè)子節(jié)點(diǎn)或無(wú)子節(jié)點(diǎn)； 沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)； 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)； 除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)； 樹(shù)里面沒(méi)有環(huán)路，意思就是從一個(gè)節(jié)點(diǎn)出發(fā)，除非往返，否則不能回到起點(diǎn)。
二叉樹(shù)
有了前面「樹(shù)」的基礎(chǔ)鋪墊，二叉樹(shù)是一種特殊的樹(shù)，還記的上面我們學(xué)過(guò)「節(jié)點(diǎn)的度」嗎？二叉樹(shù)中每個(gè)節(jié)點(diǎn)的度不大于 2 ，即它的每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支，通常稱二叉樹(shù)節(jié)點(diǎn)的左右兩個(gè)分支為左右子樹(shù)。
二叉樹(shù)是很多其他樹(shù)型結(jié)構(gòu)的基礎(chǔ)結(jié)構(gòu)，比如下面要講的 AVL 樹(shù)、二叉查找樹(shù)，他們都是由二叉樹(shù)增加一些約束條件進(jìn)化而來(lái)。
三種遍歷方式
二叉樹(shù)的遍歷就是逐個(gè)訪問(wèn)二叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)，常見(jiàn)的二叉樹(shù)遍歷方式有三種，分別是前中后序遍歷，初學(xué)者分不清這幾個(gè)順序的差別。
「有個(gè)簡(jiǎn)單的記憶方式，這里的「前中后」都是對(duì)于根節(jié)點(diǎn)而言」。
先訪問(wèn)根節(jié)點(diǎn)后訪問(wèn)左右子樹(shù)的遍歷方式是前序遍歷，先訪問(wèn)左右子樹(shù)最后訪問(wèn)根節(jié)點(diǎn)的遍歷方式是后序遍歷，先訪問(wèn)左子樹(shù)再訪問(wèn)根節(jié)點(diǎn)最后訪問(wèn)右子樹(shù)的遍歷方式是中序遍歷，下面詳細(xì)說(shuō)明：
前序遍歷
遍歷順序是根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
遍歷的得到的序列是：1 2 4 5 3 6 7
中序遍歷
遍歷順序是左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)
遍歷的得到的序列是：4 2 5 1 6 3 7
后序遍歷
遍歷順序是左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)
遍歷的得到的序列是：4 5 2 6 7 3 1
二叉查找樹(shù)
由于最基礎(chǔ)的二叉樹(shù)節(jié)點(diǎn)是無(wú)序的，想象一下如果在二叉樹(shù)中查找一個(gè)數(shù)據(jù)，最壞情況可能要要遍歷整個(gè)二叉樹(shù)，這樣的查找效率是非常低下的。
由于基礎(chǔ)二叉樹(shù)不利于數(shù)據(jù)的查找和插入，因此我們有必要對(duì)二叉樹(shù)中的數(shù)據(jù)進(jìn)行排序，所以就有了「二叉查找樹(shù)」，可以說(shuō)這種樹(shù)是為了查找而生的二叉樹(shù)，有時(shí)也稱它為「二叉排序樹(shù)」，都是同一種結(jié)構(gòu)，只是換了個(gè)叫法。
查找二叉樹(shù)理解了也不難，簡(jiǎn)單來(lái)說(shuō)就是二叉樹(shù)上所有節(jié)點(diǎn)的，左子樹(shù)上的節(jié)點(diǎn)都小于根節(jié)點(diǎn)，右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)。
這樣的結(jié)構(gòu)設(shè)計(jì)，使得查找目標(biāo)節(jié)點(diǎn)非常方便，可以通過(guò)關(guān)鍵字和當(dāng)前節(jié)點(diǎn)的對(duì)比，很快就能知道目標(biāo)節(jié)點(diǎn)在該節(jié)點(diǎn)的左子樹(shù)還是右子樹(shù)上，方便在樹(shù)中搜索目標(biāo)節(jié)點(diǎn)。
如果對(duì)排序二叉樹(shù)執(zhí)行中序遍歷，因?yàn)橹行虮闅v的順序是：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)，最終可以得到一個(gè)節(jié)點(diǎn)值的有序列表。
舉個(gè)栗子：對(duì)上圖的排序二叉樹(shù)執(zhí)行中序遍歷，我們可以得到一個(gè)有序序列：1 2 3 4 5 6 7
查詢效率
二叉查找樹(shù)的查詢復(fù)雜度取決于目標(biāo)節(jié)點(diǎn)的深度，因此當(dāng)節(jié)點(diǎn)的深度比較大時(shí)，最壞的查詢效率是O(n)，其中n是樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)。
實(shí)際應(yīng)用中有很多改進(jìn)版的二叉查找樹(shù)，目的是盡可能使得每個(gè)節(jié)點(diǎn)的深度不要過(guò)深，從而提高查詢效率。比如AVL樹(shù)和紅黑樹(shù)，可以將最壞效率降低至O(log n)，下面我們就來(lái)看下這兩種改進(jìn)的二叉樹(shù)。
AVL樹(shù)
AVL 也叫平衡二叉查找樹(shù)。AVL 這個(gè)名字的由來(lái)，是它的兩個(gè)發(fā)明者G. M. Adelson-Velsky 和 Evgenii Landis 的縮寫(xiě)，AVL最初是他們兩人在1962 年的論文「An algorithm for the organization of information」中提出來(lái)一種數(shù)據(jù)結(jié)構(gòu)。
定義
AVL 樹(shù)是一種平衡二叉查找樹(shù)，二叉查找樹(shù)我們已經(jīng)知道，那平衡是什么意思呢？
我們舉個(gè)天平的例子，天平兩端的重量要差不多才能平衡，否則就會(huì)出現(xiàn)向一邊傾斜的情況。把這個(gè)概念遷移到二叉樹(shù)中來(lái)，根節(jié)點(diǎn)看作是天平的中點(diǎn)，左子樹(shù)的高度放在天平左邊，右子樹(shù)的高度放在天平右邊，當(dāng)左右子樹(shù)的高度相差「不是特別多」，稱為是平衡的二叉樹(shù)。
AVL樹(shù)有更嚴(yán)格的定義：在二叉查找樹(shù)中，任一節(jié)點(diǎn)對(duì)應(yīng)的兩棵子樹(shù)的最大高度差為 1，這樣的二叉查找樹(shù)稱為平衡二叉樹(shù)。其中左右子樹(shù)的高度差也有個(gè)專業(yè)的叫法：平衡因子。
AVL樹(shù)的旋轉(zhuǎn)
一旦由于插入或刪除導(dǎo)致左右子樹(shù)的高度差大于1，此時(shí)就需要旋轉(zhuǎn)某些節(jié)點(diǎn)調(diào)整樹(shù)高度，使其再次達(dá)到平衡狀態(tài)，這個(gè)過(guò)程稱為旋轉(zhuǎn)再平衡。
保持樹(shù)平衡的目的是可以控制查找、插入和刪除在平均和最壞情況下的時(shí)間復(fù)雜度都是O(log n)，相比普通二叉樹(shù)最壞情況的時(shí)間復(fù)雜度是 O(n) ，AVL樹(shù)把最壞情況的復(fù)雜度控制在可接受范圍，非常合適對(duì)算法執(zhí)行時(shí)間敏感類的應(yīng)用。
B樹(shù)
B樹(shù)是魯?shù)婪颉ぐ轄枺≧udolf Bayer）1972年在波音研究實(shí)驗(yàn)室（Boeing Research Labs）工作時(shí)發(fā)明的，關(guān)于B樹(shù)名字的由來(lái)至今是個(gè)未解之謎，有人猜是Bayer的首字母，也有人說(shuō)是波音實(shí)驗(yàn)室（Boeing Research Labs）的Boeing首字母縮寫(xiě)，雖然B樹(shù)這個(gè)名字來(lái)源撲朔迷離，我們心里也沒(méi)點(diǎn) B 樹(shù)，但不影響今天我們來(lái)學(xué)習(xí)它。
定義
一個(gè) m 階的B樹(shù)是一個(gè)有以下屬性的樹(shù)
每一個(gè)節(jié)點(diǎn)最多有 m 個(gè)子節(jié)點(diǎn) 每一個(gè)非葉子節(jié)點(diǎn)（除根節(jié)點(diǎn)）最少有 ?m/2? 個(gè)子節(jié)點(diǎn)，?m/2?表示向上取整。 如果根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，那么它至少有兩個(gè)子節(jié)點(diǎn) 有 k 個(gè)子節(jié)點(diǎn)的非葉子節(jié)點(diǎn)擁有 k ? 1 個(gè)鍵 所有的葉子節(jié)點(diǎn)都在同一層
如果之前不了解，相信第一眼看完定義肯定是蒙圈，不過(guò)多看幾遍好好理解一下就好了，畫(huà)個(gè)圖例，對(duì)照著看看：
特點(diǎn)
B樹(shù)是所有節(jié)點(diǎn)的平衡因子均等于0的多路查找樹(shù)（AVL樹(shù)是平衡因子不大于 1 的二路查找樹(shù)）。
B 樹(shù)節(jié)點(diǎn)可以保存多個(gè)數(shù)據(jù)，使得 B 樹(shù)可以不用像 AVL 樹(shù)那樣為了保持平衡頻繁的旋轉(zhuǎn)節(jié)點(diǎn)。
B樹(shù)的多路的特性，降低了樹(shù)的高度，所以B樹(shù)相比于平衡二叉樹(shù)顯得矮胖很多。
B樹(shù)非常適合保存在磁盤(pán)中的數(shù)據(jù)讀取，因?yàn)槊看巫x取都會(huì)有一次磁盤(pán)IO，高度降低減少了磁盤(pán)IO的次數(shù)。
B樹(shù)常用于實(shí)現(xiàn)數(shù)據(jù)庫(kù)索引，典型的實(shí)現(xiàn)，MongoDB索引用B樹(shù)實(shí)現(xiàn)，MySQL的Innodb 存儲(chǔ)引擎用B+樹(shù)存放索引。
說(shuō)到B樹(shù)不得不提起它的好兄弟B+樹(shù)，不過(guò)這里不展開(kāi)細(xì)說(shuō)，只需知道，B+樹(shù)是對(duì)B樹(shù)的改進(jìn)，數(shù)據(jù)都放在葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)只存數(shù)據(jù)索引。
紅黑樹(shù)
紅黑樹(shù)也是一種特殊的「二叉查找樹(shù)」。
到目前為止我們學(xué)習(xí)的 AVL 樹(shù)和即將學(xué)習(xí)的紅黑樹(shù)都是二叉查找樹(shù)的變體，可見(jiàn)二叉查找樹(shù)真的是非常重要基礎(chǔ)二叉樹(shù)，如果忘了它的定義可以先回頭看看。
特點(diǎn)
紅黑樹(shù)中每個(gè)結(jié)點(diǎn)都被標(biāo)記了紅黑屬性，紅黑樹(shù)除了有普通的「二叉查找樹(shù)」特性之外，還有以下的特征：
節(jié)點(diǎn)是紅色或黑色。 根是黑色。 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。 每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。） 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
這些性質(zhì)有興趣可以自行研究，不過(guò)，現(xiàn)在你只需要知道，這些約束確保了紅黑樹(shù)的關(guān)鍵特性：從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)。
而節(jié)點(diǎn)的路徑長(zhǎng)度決定著對(duì)節(jié)點(diǎn)的查詢效率，這樣我們確保了，最壞情況下的查找、插入、刪除操作的時(shí)間復(fù)雜度不超過(guò)O(log n)，并且有較高的插入和刪除效率。
應(yīng)用場(chǎng)景
紅黑樹(shù)在實(shí)際應(yīng)用中比較廣泛，有很多已經(jīng)落地的實(shí)踐，比如學(xué)習(xí)C++的同學(xué)都知道會(huì)接觸到 STL 標(biāo)準(zhǔn)庫(kù)，而STL容器中的map、set、multiset、multimap 底層實(shí)現(xiàn)都是基于紅黑樹(shù)。
再比如，Linux內(nèi)核中也有紅黑樹(shù)的實(shí)現(xiàn)，Linux系統(tǒng)在實(shí)現(xiàn)EXT3文件系統(tǒng)、虛擬內(nèi)存管理系統(tǒng)，都有使用到紅黑樹(shù)這種數(shù)據(jù)結(jié)構(gòu)。
Linux內(nèi)核中的紅黑樹(shù)定義在內(nèi)核文件如下的位置：
如果找不到，可以 find / -name rbtree.h 搜索一下即可，有興趣可以打開(kāi)文件看下具體實(shí)現(xiàn)。
紅黑樹(shù) ?VS ?平衡二叉樹(shù)（AVL樹(shù)）
插入和刪除操作，一般認(rèn)為紅黑樹(shù)的刪除和插入會(huì)比 AVL 樹(shù)更快。因?yàn)?，紅黑樹(shù)不像 AVL 樹(shù)那樣嚴(yán)格的要求平衡因子小于等于1，這就減少了為了達(dá)到平衡而進(jìn)行的旋轉(zhuǎn)操作次數(shù)，可以說(shuō)是犧牲嚴(yán)格平衡性來(lái)?yè)Q取更快的插入和刪除時(shí)間。
紅黑樹(shù)不要求有不嚴(yán)格的平衡性控制，但是紅黑樹(shù)的特點(diǎn)，使得任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決。而 AVL 樹(shù)如果不平衡，并不會(huì)控制旋轉(zhuǎn)操作次數(shù)，旋轉(zhuǎn)直到平衡為止。
查找操作，AVL樹(shù)的效率更高。因?yàn)?AVL 樹(shù)設(shè)計(jì)比紅黑樹(shù)更加平衡，不會(huì)出現(xiàn)平衡因子超過(guò) 1 的情況，減少了樹(shù)的平均搜索長(zhǎng)度。
Trie樹(shù)（前綴樹(shù)或字典樹(shù)）
Trie來(lái)源于單詞 retrieve（檢索），Trie樹(shù)也稱為前綴樹(shù)或字典樹(shù)。利用字符串前綴來(lái)查找指定的字符串，縮短查找時(shí)間提高查詢效率，主要用于字符串的快速查找和匹配。
為什么要稱其為字典樹(shù)呢？因?yàn)門(mén)rie樹(shù)的功能就像字典一樣，想象一下查英文字典，我們會(huì)根據(jù)首字母找到對(duì)應(yīng)的頁(yè)碼，接著根據(jù)第二、第三...個(gè)單詞，逐步查找到目標(biāo)單詞，Trie樹(shù)的組織思想和字典組織很像，字典樹(shù)由此得名。
定義
Trie的核心思想是空間換時(shí)間，有 3 個(gè)基本性質(zhì)：
根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。 從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。
比如對(duì)單詞序列lru, lua, mem, mcu 建立Trie樹(shù)如下：
Trie樹(shù)建立和查詢是可以同步進(jìn)行的，可以在還沒(méi)建立出完成的 Trie 樹(shù)之前就找到目標(biāo)數(shù)據(jù)，而如果用 Hash 表等結(jié)構(gòu)存儲(chǔ)是需要先建立完成表才能開(kāi)始查詢，這也是 Trie 樹(shù)查詢速度快的原因。
應(yīng)用
Trie樹(shù)還用于搜索引擎的關(guān)鍵詞提示功能。比如當(dāng)你在搜索框中輸入檢索單詞的開(kāi)頭幾個(gè)字，搜索引擎就可以自動(dòng)聯(lián)想匹配到可能的詞組出來(lái)，這正是Trie樹(shù)的最直接應(yīng)用。
這種結(jié)構(gòu)在海量數(shù)據(jù)查詢上很有優(yōu)勢(shì)，因?yàn)椴槐貫榱苏业侥繕?biāo)數(shù)據(jù)遍歷整個(gè)數(shù)據(jù)集合，只需按前綴遍歷匹配的路徑即可找到目標(biāo)數(shù)據(jù)。
因此，Trie樹(shù)還可用于解決類似以下的面試題：
?給你100000個(gè)長(zhǎng)度不超過(guò)10的單詞。對(duì)于每一個(gè)單詞，我們要判斷他出沒(méi)出現(xiàn)過(guò)，如果出現(xiàn)了，求第一次出現(xiàn)在第幾個(gè)位置。
?
?有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò)16字節(jié)，內(nèi)存限制大小是1M，求頻數(shù)最高的100個(gè)詞
?
?1000萬(wàn)字符串，其中有些是重復(fù)的，需要把重復(fù)的全部去掉，保留沒(méi)有重復(fù)的字符串，請(qǐng)問(wèn)怎么設(shè)計(jì)和實(shí)現(xiàn)？
?
?一個(gè)文本文件，大約有一萬(wàn)行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞，請(qǐng)給出思想，給出時(shí)間復(fù)雜度分析。
?
來(lái)個(gè)直擊靈魂的三連吧！