圖解6種“樹”，你心中有數(shù)嗎？

時間：2020-10-29 11:05:45

關(guān)鍵字：嵌入式數(shù)據(jù)結(jié)構(gòu)

手機(jī)看文章

掃描二維碼
隨時隨地手機(jī)看文章

[導(dǎo)讀]數(shù)據(jù)結(jié)構(gòu)這門課程是計算機(jī)相關(guān)專業(yè)的基礎(chǔ)課，數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)在計算機(jī)中的存儲、組織方式。我們在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時候，會遇到各種各樣的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，比如堆棧、隊列、數(shù)組、鏈表、樹...這些基本的數(shù)據(jù)結(jié)構(gòu)類型有各自的特點，不同數(shù)據(jù)結(jié)構(gòu)適用于解決不同場景下的問題。

數(shù)據(jù)結(jié)構(gòu)這門課程是計算機(jī)相關(guān)專業(yè)的基礎(chǔ)課，數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)在計算機(jī)中的存儲、組織方式。

我們在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時候，會遇到各種各樣的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，比如堆棧、隊列、數(shù)組、鏈表、樹...這些基本的數(shù)據(jù)結(jié)構(gòu)類型有各自的特點，不同數(shù)據(jù)結(jié)構(gòu)適用于解決不同場景下的問題。

樹形結(jié)構(gòu)相比數(shù)組、鏈表、堆棧這些數(shù)據(jù)結(jié)構(gòu)來說，稍微復(fù)雜一點點，但樹形結(jié)構(gòu)可以用于解決很多實際問題，因為現(xiàn)實世界事物之間的關(guān)系往往不是線性關(guān)聯(lián)的，而「樹」恰好適合描述這種非線性關(guān)系。

今天就帶大家一起學(xué)習(xí)下，數(shù)據(jù)結(jié)構(gòu)中的各種「樹」，這也是面試中經(jīng)常考察的內(nèi)容，手撕二叉樹是常規(guī)套路，對候選人也很有區(qū)分度，學(xué)完這篇文章，相信大家都會心中有「樹」了。

從樹說起

什么是樹？現(xiàn)實中的樹大家都見過，在數(shù)據(jù)結(jié)構(gòu)中也有樹，此樹非彼樹，不過數(shù)據(jù)結(jié)構(gòu)的樹和現(xiàn)實中的樹在形態(tài)上確實有點相像。

樹是非線性的數(shù)據(jù)結(jié)構(gòu)，用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合，它是由n個有限節(jié)點組成的具有層次關(guān)系的集合。在數(shù)據(jù)結(jié)構(gòu)中樹是非線性數(shù)據(jù)結(jié)構(gòu)，那我們先來了解下，什么是線性與非線性數(shù)據(jù)結(jié)構(gòu)？

線性結(jié)構(gòu)

「線性結(jié)構(gòu)」是一個有序數(shù)據(jù)元素的集合。其中數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的，常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙端隊列，數(shù)組，串。

可以想象，所謂的線性結(jié)構(gòu)數(shù)據(jù)組織形式，就像一條線段一樣筆直，元素之間首尾相接。比如現(xiàn)實中的火車進(jìn)站、食堂打飯排隊的隊列。

非線性結(jié)構(gòu)

簡而言之，線性結(jié)構(gòu)的對立面就是「非線性結(jié)構(gòu)」。

樹

線性結(jié)構(gòu)中節(jié)點是首位相接一對一關(guān)系，在樹結(jié)構(gòu)中節(jié)點之間不再是簡單的一對一關(guān)系，而是較為復(fù)雜的一對多的關(guān)系，一個節(jié)點可以與多個節(jié)點發(fā)生關(guān)聯(lián)，樹是一種層次化的數(shù)據(jù)組織形式，樹在現(xiàn)實中是可以找到例子的，比如現(xiàn)實中的族譜，親戚之間的關(guān)系是層次關(guān)聯(lián)的樹形關(guān)系。

數(shù)據(jù)結(jié)構(gòu)中的「樹」的名字由來，是因為如果把節(jié)點之間的關(guān)系直觀展示出來，由于長得和現(xiàn)實世界中的樹很像，由此得名。如圖：

樹的關(guān)鍵概念

人們對樹形結(jié)構(gòu)的研究比較深入，為了方便研究樹的各種性質(zhì)，抽象出了一些樹相關(guān)的概念，以便清晰簡介的描述一顆樹。下面幾個基礎(chǔ)概念必須了解，否則你當(dāng)你刷LeetCode樹相關(guān)題目時候，或者面試官向你描述問題時，你會連題目都看不懂事什么意思。

先來上一個圖解，下面的術(shù)語和概念對照著看，更容易理解。

什么是節(jié)點的度？

度很好理解，直觀來說，數(shù)一下節(jié)點有幾個分叉就說這個節(jié)點的度是多少。

什么是根節(jié)點？

在一顆樹形結(jié)構(gòu)中，最頂層的那個節(jié)點就是根節(jié)點了，所有的子節(jié)點都源自它發(fā)散開來。

什么是父節(jié)點？

樹的父子關(guān)系和現(xiàn)實中很相似，若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點。

什么是葉子節(jié)點？

直觀來看葉子節(jié)點都位于樹的最底層，就是沒有分叉的節(jié)點，嚴(yán)格的定義是度為 0 的節(jié)點叫葉子節(jié)點。

什么是節(jié)點的高度？

高度是從葉子節(jié)點開始「自底向上」逐層累加的路徑長度，樹葉的高度為 0（有些書上也說是 0，不用糾結(jié)）

什么是節(jié)點的深度？

深度是從根節(jié)點開始「自頂向下」逐層累加的路徑長度，根的深度為1（有些書上也說是 0，問題不大）

小技巧：高度和深度，一個從下往上數(shù)，一個從上往下數(shù)。

樹的特點

樹形數(shù)據(jù)結(jié)構(gòu)，具有以下的結(jié)構(gòu)特點：

每個節(jié)點都只有有限個子節(jié)點或無子節(jié)點；
沒有父節(jié)點的節(jié)點稱為根節(jié)點；
每一個非根節(jié)點有且只有一個父節(jié)點；
除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹；
樹里面沒有環(huán)路，意思就是從一個節(jié)點出發(fā)，除非往返，否則不能回到起點。

二叉樹

有了前面「樹」的基礎(chǔ)鋪墊，二叉樹是一種特殊的樹，還記的上面我們學(xué)過「節(jié)點的度」嗎？二叉樹中每個節(jié)點的度不大于 2 ，即它的每個節(jié)點最多只有兩個分支，通常稱二叉樹節(jié)點的左右兩個分支為左右子樹。

二叉樹是很多其他樹型結(jié)構(gòu)的基礎(chǔ)結(jié)構(gòu)，比如下面要講的 AVL 樹、二叉查找樹，他們都是由二叉樹增加一些約束條件進(jìn)化而來。

三種遍歷方式

二叉樹的遍歷就是逐個訪問二叉樹節(jié)點的數(shù)據(jù)，常見的二叉樹遍歷方式有三種，分別是前中后序遍歷，初學(xué)者分不清這幾個順序的差別。

「有個簡單的記憶方式，這里的「前中后」都是對于根節(jié)點而言」。

先訪問根節(jié)點后訪問左右子樹的遍歷方式是前序遍歷，先訪問左右子樹最后訪問根節(jié)點的遍歷方式是后序遍歷，先訪問左子樹再訪問根節(jié)點最后訪問右子樹的遍歷方式是中序遍歷，下面詳細(xì)說明：

前序遍歷

遍歷順序是根節(jié)點->左子樹->右子樹

遍歷的得到的序列是：1 2 4 5 3 6 7

中序遍歷

遍歷順序是左子樹->根節(jié)點->右子樹

遍歷的得到的序列是：4 2 5 1 6 3 7

后序遍歷

遍歷順序是左子樹->右子樹->根節(jié)點

遍歷的得到的序列是：4 5 2 6 7 3 1

二叉查找樹

由于最基礎(chǔ)的二叉樹節(jié)點是無序的，想象一下如果在二叉樹中查找一個數(shù)據(jù)，最壞情況可能要要遍歷整個二叉樹，這樣的查找效率是非常低下的。

由于基礎(chǔ)二叉樹不利于數(shù)據(jù)的查找和插入，因此我們有必要對二叉樹中的數(shù)據(jù)進(jìn)行排序，所以就有了「二叉查找樹」，可以說這種樹是為了查找而生的二叉樹，有時也稱它為「二叉排序樹」，都是同一種結(jié)構(gòu)，只是換了個叫法。

查找二叉樹理解了也不難，簡單來說就是二叉樹上所有節(jié)點的，左子樹上的節(jié)點都小于根節(jié)點，右子樹上所有節(jié)點的值都大于根節(jié)點。

這樣的結(jié)構(gòu)設(shè)計，使得查找目標(biāo)節(jié)點非常方便，可以通過關(guān)鍵字和當(dāng)前節(jié)點的對比，很快就能知道目標(biāo)節(jié)點在該節(jié)點的左子樹還是右子樹上，方便在樹中搜索目標(biāo)節(jié)點。

如果對排序二叉樹執(zhí)行中序遍歷，因為中序遍歷的順序是：左子樹->根節(jié)點->右子樹，最終可以得到一個節(jié)點值的有序列表。

舉個栗子：對上圖的排序二叉樹執(zhí)行中序遍歷，我們可以得到一個有序序列：1 2 3 4 5 6 7

查詢效率

二叉查找樹的查詢復(fù)雜度取決于目標(biāo)節(jié)點的深度，因此當(dāng)節(jié)點的深度比較大時，最壞的查詢效率是O(n)，其中n是樹中的節(jié)點個數(shù)。

實際應(yīng)用中有很多改進(jìn)版的二叉查找樹，目的是盡可能使得每個節(jié)點的深度不要過深，從而提高查詢效率。比如AVL樹和紅黑樹，可以將最壞效率降低至O(log n)，下面我們就來看下這兩種改進(jìn)的二叉樹。

AVL樹

AVL 也叫平衡二叉查找樹。AVL 這個名字的由來，是它的兩個發(fā)明者G. M. Adelson-Velsky 和 Evgenii Landis 的縮寫，AVL最初是他們兩人在1962 年的論文「An algorithm for the organization of information」中提出來一種數(shù)據(jù)結(jié)構(gòu)。

定義

AVL 樹是一種平衡二叉查找樹，二叉查找樹我們已經(jīng)知道，那平衡是什么意思呢？

我們舉個天平的例子，天平兩端的重量要差不多才能平衡，否則就會出現(xiàn)向一邊傾斜的情況。把這個概念遷移到二叉樹中來，根節(jié)點看作是天平的中點，左子樹的高度放在天平左邊，右子樹的高度放在天平右邊，當(dāng)左右子樹的高度相差「不是特別多」，稱為是平衡的二叉樹。

AVL樹有更嚴(yán)格的定義：在二叉查找樹中，任一節(jié)點對應(yīng)的兩棵子樹的最大高度差為 1，這樣的二叉查找樹稱為平衡二叉樹。其中左右子樹的高度差也有個專業(yè)的叫法：平衡因子。

AVL樹的旋轉(zhuǎn)

一旦由于插入或刪除導(dǎo)致左右子樹的高度差大于1，此時就需要旋轉(zhuǎn)某些節(jié)點調(diào)整樹高度，使其再次達(dá)到平衡狀態(tài)，這個過程稱為旋轉(zhuǎn)再平衡。

保持樹平衡的目的是可以控制查找、插入和刪除在平均和最壞情況下的時間復(fù)雜度都是O(log n)，相比普通二叉樹最壞情況的時間復(fù)雜度是 O(n) ，AVL樹把最壞情況的復(fù)雜度控制在可接受范圍，非常合適對算法執(zhí)行時間敏感類的應(yīng)用。

B樹

B樹是魯?shù)婪颉ぐ轄枺≧udolf Bayer）1972年在波音研究實驗室（Boeing Research Labs）工作時發(fā)明的，關(guān)于B樹名字的由來至今是個未解之謎，有人猜是Bayer的首字母，也有人說是波音實驗室（Boeing Research Labs）的Boeing首字母縮寫，雖然B樹這個名字來源撲朔迷離，我們心里也沒點 B 樹，但不影響今天我們來學(xué)習(xí)它。

定義

一個 m 階的B樹是一個有以下屬性的樹

每一個節(jié)點最多有 m 個子節(jié)點
每一個非葉子節(jié)點（除根節(jié)點）最少有 ?m/2? 個子節(jié)點，?m/2?表示向上取整。
如果根節(jié)點不是葉子節(jié)點，那么它至少有兩個子節(jié)點
有 k 個子節(jié)點的非葉子節(jié)點擁有 k ? 1 個鍵
所有的葉子節(jié)點都在同一層

如果之前不了解，相信第一眼看完定義肯定是蒙圈，不過多看幾遍好好理解一下就好了，畫個圖例，對照著看看：

圖3

特點

B樹是所有節(jié)點的平衡因子均等于0的多路查找樹（AVL樹是平衡因子不大于 1 的二路查找樹）。
B 樹節(jié)點可以保存多個數(shù)據(jù)，使得 B 樹可以不用像 AVL 樹那樣為了保持平衡頻繁的旋轉(zhuǎn)節(jié)點。
B樹的多路的特性，降低了樹的高度，所以B樹相比于平衡二叉樹顯得矮胖很多。
B樹非常適合保存在磁盤中的數(shù)據(jù)讀取，因為每次讀取都會有一次磁盤IO，高度降低減少了磁盤IO的次數(shù)。

B樹常用于實現(xiàn)數(shù)據(jù)庫索引，典型的實現(xiàn)，MongoDB索引用B樹實現(xiàn)，MySQL的Innodb 存儲引擎用B+樹存放索引。

說到B樹不得不提起它的好兄弟B+樹，不過這里不展開細(xì)說，只需知道，B+樹是對B樹的改進(jìn)，數(shù)據(jù)都放在葉子節(jié)點，非葉子節(jié)點只存數(shù)據(jù)索引。

紅黑樹

紅黑樹也是一種特殊的「二叉查找樹」。

到目前為止我們學(xué)習(xí)的 AVL 樹和即將學(xué)習(xí)的紅黑樹都是二叉查找樹的變體，可見二叉查找樹真的是非常重要基礎(chǔ)二叉樹，如果忘了它的定義可以先回頭看看。

特點

紅黑樹中每個結(jié)點都被標(biāo)記了紅黑屬性，紅黑樹除了有普通的「二叉查找樹」特性之外，還有以下的特征：

節(jié)點是紅色或黑色。
根是黑色。
所有葉子都是黑色（葉子是NIL節(jié)點）。
每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。）
從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。

這些性質(zhì)有興趣可以自行研究，不過，現(xiàn)在你只需要知道，這些約束確保了紅黑樹的關(guān)鍵特性：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。

紅黑樹

而節(jié)點的路徑長度決定著對節(jié)點的查詢效率，這樣我們確保了，最壞情況下的查找、插入、刪除操作的時間復(fù)雜度不超過O(log n)，并且有較高的插入和刪除效率。

應(yīng)用場景

紅黑樹在實際應(yīng)用中比較廣泛，有很多已經(jīng)落地的實踐，比如學(xué)習(xí)C++的同學(xué)都知道會接觸到 STL 標(biāo)準(zhǔn)庫，而STL容器中的map、set、multiset、multimap 底層實現(xiàn)都是基于紅黑樹。

再比如，Linux內(nèi)核中也有紅黑樹的實現(xiàn)，Linux系統(tǒng)在實現(xiàn)EXT3文件系統(tǒng)、虛擬內(nèi)存管理系統(tǒng)，都有使用到紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。

Linux內(nèi)核中的紅黑樹定義在內(nèi)核文件如下的位置：

如果找不到，可以 find / -name rbtree.h 搜索一下即可，有興趣可以打開文件看下具體實現(xiàn)。

紅黑樹 ?VS ?平衡二叉樹（AVL樹）

插入和刪除操作，一般認(rèn)為紅黑樹的刪除和插入會比 AVL 樹更快。因為，紅黑樹不像 AVL 樹那樣嚴(yán)格的要求平衡因子小于等于1，這就減少了為了達(dá)到平衡而進(jìn)行的旋轉(zhuǎn)操作次數(shù)，可以說是犧牲嚴(yán)格平衡性來換取更快的插入和刪除時間。
紅黑樹不要求有不嚴(yán)格的平衡性控制，但是紅黑樹的特點，使得任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決。而 AVL 樹如果不平衡，并不會控制旋轉(zhuǎn)操作次數(shù)，旋轉(zhuǎn)直到平衡為止。
查找操作，AVL樹的效率更高。因為 AVL 樹設(shè)計比紅黑樹更加平衡，不會出現(xiàn)平衡因子超過 1 的情況，減少了樹的平均搜索長度。

Trie樹（前綴樹或字典樹）

Trie來源于單詞 retrieve（檢索），Trie樹也稱為前綴樹或字典樹。利用字符串前綴來查找指定的字符串，縮短查找時間提高查詢效率，主要用于字符串的快速查找和匹配。

為什么要稱其為字典樹呢？因為Trie樹的功能就像字典一樣，想象一下查英文字典，我們會根據(jù)首字母找到對應(yīng)的頁碼，接著根據(jù)第二、第三...個單詞，逐步查找到目標(biāo)單詞，Trie樹的組織思想和字典組織很像，字典樹由此得名。

定義

Trie的核心思想是空間換時間，有 3 個基本性質(zhì)：

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

比如對單詞序列lru, lua, mem, mcu 建立Trie樹如下：

Trie樹建立和查詢是可以同步進(jìn)行的，可以在還沒建立出完成的 Trie 樹之前就找到目標(biāo)數(shù)據(jù)，而如果用 Hash 表等結(jié)構(gòu)存儲是需要先建立完成表才能開始查詢，這也是 Trie 樹查詢速度快的原因。

應(yīng)用

Trie樹還用于搜索引擎的關(guān)鍵詞提示功能。比如當(dāng)你在搜索框中輸入檢索單詞的開頭幾個字，搜索引擎就可以自動聯(lián)想匹配到可能的詞組出來，這正是Trie樹的最直接應(yīng)用。

這種結(jié)構(gòu)在海量數(shù)據(jù)查詢上很有優(yōu)勢，因為不必為了找到目標(biāo)數(shù)據(jù)遍歷整個數(shù)據(jù)集合，只需按前綴遍歷匹配的路徑即可找到目標(biāo)數(shù)據(jù)。

因此，Trie樹還可用于解決類似以下的面試題：

給你100000個長度不超過10的單詞。對于每一個單詞，我們要判斷他出沒出現(xiàn)過，如果出現(xiàn)了，求第一次出現(xiàn)在第幾個位置。

有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M，求頻數(shù)最高的100個詞

1000萬字符串，其中有些是重復(fù)的，需要把重復(fù)的全部去掉，保留沒有重復(fù)的字符串，請問怎么設(shè)計和實現(xiàn)？

一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞，請給出思想，給出時間復(fù)雜度分析。

總結(jié)一下

樹形數(shù)據(jù)結(jié)構(gòu)有許多變種，這篇文章我們從樹開始，把幾種常見樹形數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)了一遍，包括二叉樹、二叉查找樹（二叉搜索樹）、AVL樹、紅黑樹、B樹、Trie樹。

文章構(gòu)思的時候想聊聊數(shù)據(jù)結(jié)構(gòu)中的樹，沒想到步子跨的有點大，大到不知從何說起，因為數(shù)據(jù)結(jié)構(gòu)中各種樹的變體非常多，一篇文章實難細(xì)數(shù)，篇幅有限，也只能說是淺嘗輒止，作為樹形數(shù)據(jù)結(jié)構(gòu)入門，如果要深入的學(xué)習(xí)，每個知識點還能寫出一篇文章，比如 B+ 樹原理及其在數(shù)據(jù)庫索引中的應(yīng)用、紅黑樹的詳細(xì)分析等等，這次檸檬只是粗略帶大家走一遍。

在后端開發(fā)中，數(shù)據(jù)結(jié)構(gòu)與算法是后端程序員的基本素養(yǎng)，除了基礎(chǔ)架構(gòu)部的后端開發(fā)同學(xué)，雖然我們平常不會經(jīng)常造輪子，但是掌握基本的數(shù)據(jù)結(jié)構(gòu)與算法仍然是非常有必要，面試也對相關(guān)能力有要求。

回顧往期文章，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容寫的比較少，如果大家有興趣，檸檬會再多寫一些相關(guān)主題的文章！

感謝各位的閱讀，文章的目的是分享對知識的理解，技術(shù)類文章我都會反復(fù)求證以求最大程度保證準(zhǔn)確性，若文中出現(xiàn)明顯紕漏也歡迎指出，我們一起在探討中學(xué)習(xí)。

哈嘍，我是小林，就愛圖解計算機(jī)基礎(chǔ)，如果覺得文章對你有幫助，歡迎分享給你的朋友，也給小林點個「在看」，這對小林非常重要，謝謝你們，給各位小姐姐小哥哥們抱拳了，我們下次見！