一、樹是什么？

有根有枝葉便是樹！根只有一個，枝葉可以有，也可以沒有，可以有一個，也可以有很多。

就像這樣：

嗯，應該是這樣：

二、一些概念

1、高度

樹有多高，嗯，我一米八三！

樹的高度怎么算？

高度是啥，就是從下往上到最頂端，從葉節點到根節點。

從每個葉節點開始，一個節點一個節點往上數，數到根節點，最長的那個數就是數的高度。葉節點起始為0.

上面這個樹的高度是4。

2、深度

深度，顧名思義，就是從上往下到最低端，從根節點到葉節點。

從根開始，一個節點一個節點往下數，數到每個葉子節點，最長的那個數就是數的深度。根節點的起始為0.

上面這個樹的深度是4。

對比上面的高度，看到了哈，數值是一樣的，

3、層

一層是什么呢。就是橫向的同一高度的所有節點湊一塊兒就是一層。

像下面一條線連接了第二層所有的節點：

三、二叉樹的遍歷

二叉樹是什么？

二叉樹就是每個節點最多有兩個分叉子節點。

遍歷是什么意思？

遍歷就是一個樹的所有節點都點一遍，那么既然要點一遍，總歸要遵循一個特定的順序，不然，亂來的話總會可能漏一個，或者多一個。

像下面這棵樹：

1、前序遍歷

順序：中左右

中 6 -> 左中 5 -> 左 2 -> 右 3 -> 右中 7 -> 右 8

結果就是：6、5、2、3、7、8。

2、中序遍歷

順序：左中右

左 2 -> 中 5 -> 右 3 -> 中 6 -> 右中 7 -> 右 8

結果就是： 2、5、3、6、7、8。

3、后序遍歷

順序：左右中

左 2 -> 右 3 -> 中左 5 -> 右 8 -> 中右 7 -> 中 6

結果就是：2、3、5、8、7、6.

這個順序，其實很容易混亂。想要記得牢，只需要一點：

【前、中、后】，前為左，右為后，哪個順序遍歷，那么哪個節點就會順序居中，其它的節點，靠左的居前。

節點的巡查是從根節點出發，從上到下，從左至右巡查，每個節點及其子點巡查完畢后，再跳出到其它節點。

4、附加：層序遍歷

層序遍歷很簡單就是從上到下，一層一層的收攏節點。

第一層 6 -> 第二層 5、7 -> 第三層 2、3、8

結果就是：6、5、7、2、3、8.

4、樹能干什么？

樹能蓋房子！

沒錯，樹通常用來搭建存儲數據的房子。

數據存儲是對數據的持久化保存，針對數據的操作包括讀和寫。不過，無論是讀還是寫，都離不開對數據的檢索操作。

1、B樹

之前文章介紹過B樹及在數據庫存儲方面的應用：

你好，我是B樹

MySQL InnoDB 是怎么使用 B+ 樹存數據的？

B 樹，即balance tree。其結構及節點數據分布遵循特定的規則。

B 樹的算法運行時間通常由它所執行的【磁盤讀寫操作次數】決定，所有一般會一次盡可能的讀寫更多的信息。一個B樹節點通常和一個完整的磁盤頁大小相同，所以磁盤頁的大小限制了一個B樹節點所能包含孩子節點的個數。

B 樹每個節點會包含多少個分支，稱之為分支因子。分支因子越大，B 的高度越低，查找關鍵字所需的磁盤存取次數越少，查詢時間越短。這也是為什么會推崇使用B樹結構來作為數據底層存儲。

2、二叉搜索樹

二叉搜索樹是以一棵二叉樹來組織數據存儲，每個節點除了包含數據本身外，還包括指向左節點、右節點及父節點的指針，即key、left、right、p。其中存儲數據需滿足左中右非降序存儲，即left.key <= key <= right.key。

左中右，是不是很熟悉，就是我們上面講到過的【中序遍歷】順序。【中序遍歷】輸出的話，整個數列會是非降序排序數列。

搜索樹結構通常支持包括查找，最大值，最小值，插入，刪除等操作。嗯，這些操作是不是又很熟悉，總之就是一個【日常操作】。

二叉搜索樹上的操作時間和它的高度成正比，對于n節點二叉樹，通常最壞運行時間為O(lgn)（為什么是O(lgn)呢？這個需要推導，先記住就行了），這個就是樹元素隨機分步的情況下的結果。極端情況下，一條鏈從根到葉的話，時間固定就是O(n)了。就像下面這個棵樹：

3、紅黑樹

紅黑樹也是一個二叉搜索樹。那為什么會需要這么一棵樹呢？

就是為了避免上面哪種極端或者接近極端情況的出現。它可以【保證最壞的情況下操作時間復雜度為O(lgn)】。

對的，是保證！那怎么保證呢？當然是通過維持紅黑樹本身的結構特點來實現。

我們上面及到過二叉搜索樹節點包含的數據，紅黑樹會在其基礎上增加一個存儲位來表示節點的顏色（紅或者黑）。通過【對任何一條從根到葉子節點的簡單路徑上的各個節點顏色進行約束】來確保【沒有一路徑會比其它路徑長2倍】。

紅黑樹的特點：

• a)【節點要么紅，要么黑】

• b)【根節點是黑的】

• c)【葉節點是黑的】

• d)【如果一個節點是紅色的，那么它的子節點是黑色的】

• e)【對任何一個節點，從該節點到其所有后代葉節點的簡單路徑上的黑節點數據是相同的】

這里有個點需要強調一下，紅黑樹里所說的葉子節點指的是【外部節點】，也就是不包含 key 的節點。

黑高：從某個節點到達其葉節點的【任何一個（參考e】簡單路徑上的黑色節點個數稱之為黑高。紅黑樹的黑高即為其根節點的黑高。

一顆有 n 個內部節點的紅黑樹的高度至多為 2lg（n+1），也即我們前面說的能夠保證最壞的情況下操作時間復雜度為O(lgn)。

紅黑樹有哪些應用呢？

最常見的就是 HashMap了，用于解決存儲元素哈希沖突，當鏈表元素個數超過8時，即轉為紅黑樹。

總結

以上是生活随笔為你收集整理的数据结构里的一棵树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。