二叉樹

簡介

二叉樹(Binary Tree) ：是一種非常重要的非線性結構。：二叉樹是每個節點最多有兩個子樹的樹結構；
是n(n>=0)個結點的有限集合，它或者是空樹（n=0），或者是由一個根結點及兩顆互不相交的、分別稱為左子樹和右子樹的二叉樹所組成

節點：Node, 二叉樹是由N個節點組成，（每個節點有兩個子節點的指針（也可以沒有），分別為左子節點，右子節點）。

根節點：沒有父節點的節點就是根節點（唯一），也就是第一層的哪一個節點。如圖所示：4

葉子節點：沒有子節點的節點就是葉子節點。如圖所示：1，3，5，7

非葉子節點：有子節點的節點就是非葉子節點。如圖所示：2，6，4（4 是根節點也是特殊的非葉子節點）

度：表示節點的子節點個數，因為子節點最大數量為2 (左子，右子)，所以度最大為2.

高度：也稱樹的深度（層高）等，表示樹的層級。如圖所示：樹高度為3.

每層節點數量：N = 2^(h-1) . N（每層數量），h (層級)。

樹總節點數量：N = (2^h) - 1. N（每層數量），h (層級)。

如圖所示

分類

二叉樹也有類別：

普通二叉樹

平衡二叉樹

除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點

• 葉子結點只能出現在最下層和次下層。
• 最下層的葉子結點集中在樹的左部。
• 倒數第二層若存在葉子結點，一定在右部連續位置。
• 如果結點度為1，則該結點只有左孩子，即沒有右子樹。
• 同樣結點數目的二叉樹，完全二叉樹深度最小

滿二叉樹

除最后一層無任何子節點外，每一層上的所有結點都有兩個子結點的二叉樹

• 葉子只能出現在最下一層。出現在其它層就不可能達成平衡。
• 非葉子結點的度(結點擁有的子樹數目稱為結點的度)一定是2
• 在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多

二叉搜索樹（二叉排序樹、二叉查找樹），

二叉排序樹：可以為空樹，或者是具備如下性質：若它的左子樹不空，則左子樹上的所有結點的值均小于根節點的值；若它的右子樹不空，則右子樹上的所有結點的值均大于根節點的值，左右子樹分別為二叉排序樹。
如下圖所示

平衡二叉樹

平衡二叉樹是一種概念，是二叉查找樹的一個進化體，它有幾種實現方式：紅黑樹、AVL樹
它是一個空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是平衡二叉樹，如果插入或者刪除一個節點使得高度之差大于1，就要進行節點之間的旋轉，將二叉樹重新維持在一個平衡狀態。

這個方案很好的解決了二叉查找樹退化成鏈表的問題，把插入，查找，刪除的時間復雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查找樹來說，時間上穩定了很多

AVL實現平衡的關鍵在于旋轉操作：

插入和刪除可能破壞二叉樹的平衡，此時需要通過一次或多次樹旋轉來重新平衡這個樹。當插入數據時，最多只需要1次旋轉(單旋轉或雙旋轉)；但是當刪除數據時，會導致樹失衡，AVL需要維護從被刪除節點到根節點這條路徑上所有節點的平衡，旋轉的量級為O(lgn)
由于旋轉的耗時，AVL樹在刪除數據時效率很低；在刪除操作較多時，維護平衡所需的代價可能高于其帶來的好處，因此AVL實際使用并不廣泛

紅黑樹

紅黑樹是一種平衡二叉查找樹的變體，它的左右子樹高差有可能大于1，所以紅黑樹不是嚴格意義上的平衡二叉樹（AVL），但對之進行平衡的代價較低， 其平均統計性能要強于 AVL

• 每個節點或者是黑色，或者是紅色
• 根節點是黑色
• 每個葉結點是黑色
• 如果一個節點是紅色的，則它的子節點必須是黑色的，紅色節點的孩子和父親都不能是紅色。從每個葉子到根的所有路徑上不能有兩個連續的紅色節點，任意一結點到每個葉子結點的路徑都包含數量相同的黑結點。確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對接近平衡的二叉樹，并不是一個完美平衡二叉查找樹

紅黑樹和AVL樹區別
RB-Tree和AVL樹作為二叉搜索樹(BBST)，其實現的算法時間復雜度相同，AVL作為最先提出的BBST，貌似RB-tree實現的功能都可以用AVL樹是代替，那么為什么還需要引入RB-Tree呢

• 紅黑樹不追求完全平衡，即不像AVL那樣要求節點的 高度差的絕對值 <= 1，它只要求部分達到平衡，但是提出了為節點增加顏色，紅黑是用非嚴格的平衡來換取增刪節點時候旋轉次數的降低，任何不平衡都會在三次旋轉之內解決，而AVL是嚴格平衡樹，因此在增加或者刪除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多
• 就插入節點導致樹失衡的情況，AVL和RB-Tree都是最多兩次樹旋轉來實現復衡rebalance，旋轉的量級是O(1)
• 刪除節點導致失衡，AVL需要維護從被刪除節點到根節點root這條路徑上所有節點的平衡，旋轉的量級為O(logN)，而RB-Tree最多只需要旋轉3次實現復衡，只需O(1)，所以說RB-Tree刪除節點的rebalance的效率更高，開銷更小
• AVL的結構相較于RB-Tree更為平衡，插入和刪除引起失衡，RB-Tree復衡效率更高；當然，由于AVL高度平衡，因此AVL的Search效率更高
• 針對插入和刪除節點導致失衡后的rebalance操作，紅黑樹能夠提供一個比較便宜的解決方案，降低開銷，是對search，insert ，以及delete效率的折衷，總體來說，RB-Tree的統計性能高于AVL
• 故引入RB-Tree是功能、性能、空間開銷的折中結果
  AVL更平衡，結構上更加直觀，時間效能針對讀取而言更高；維護稍慢，空間開銷較大。
  紅黑樹，讀取略遜于AVL，維護強于AVL，空間開銷與AVL類似，內容極多時略優于AVL，維護優于AVL。

缺點：對于數據在內存中的情況，紅黑樹的表現是非常優異的。但是對于數據在磁盤等輔助存儲設備中的情況（如MySQL等數據庫），紅黑樹并不擅長，因為紅黑樹長得還是太高了。當數據在磁盤中時，磁盤IO會成為最大的性能瓶頸，設計的目標應該是盡量減少IO次數；而樹的高度越高，增刪改查所需要的IO次數也越多，會嚴重影響性能

總結：實際應用中，若搜索的次數遠遠大于插入和刪除，那么選擇AVL，如果搜索，插入刪除次數幾乎差不多，應該選擇RB-Tree

B樹類型

B樹（B-樹、B_樹）

一種平衡的多叉樹，稱為B樹（或B-樹、B_樹，B：balanced說明B樹和平衡樹有關系）
B樹是為磁盤等輔存設備設計的多路平衡查找樹，與二叉樹相比，B樹的每個非葉節點可以有多個子樹。 因此，當總節點數量相同時，B樹的高度遠遠小于AVL樹和紅黑樹(B樹是一顆“矮胖子”)，磁盤IO次數大大減少。

一棵M階B樹(M階數：表示此樹的結點最多有多少個孩子結點(子樹))是一棵平衡的m路搜索樹。它或者是空樹，或者是滿足下列性質的樹：

1. 每個節點最多包含 m 個子節點
2. 根結點至少有兩個子節點，除根節點外，每個非葉節點至少包含 m/2 個子節點；
3. 擁有 k 個子節點的非葉節點將包含 k - 1 條記錄
4. 每個非根節點所包含的關鍵字個數 j 滿足：┌m/2┐ - 1 <= j <= m - 1；
5. 除根結點以外的所有結點(不包括葉子結點)的度數正好是關鍵字總數加1，故內部子樹個數 k 滿足：┌m/2┐ <= k <= m ；
6. 所有的葉子結點都位于同一層。

簡單理解為：平衡多叉樹為B樹（每一個子節點上都是有數據的），葉子節點之間無指針相鄰

B樹的搜索，從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那么就命中；否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字；重復，直到所對應的兒子指針為空，或已經是葉子結點

如果B樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那么B樹的搜索性能逼近二分查找；但它比連續內存空間的二分查找的優點是，改變B樹結構（插入與刪除結點）不需要移動大段的內存數據，甚至通常是常數開銷；但B樹在經過多次插入與刪除后，有可能導致不同的結構

B-樹的特性：

1. 關鍵字集合分布在整顆樹中；
2. 任何一個關鍵字出現且只出現在一個結點中；
3. 搜索有可能在非葉子結點結束；
4. 其搜索性能等價于在關鍵字全集內做一次二分查找；
5. 自動層次控制；

由于M階B樹每個結點最少M/2個結點的限制，是為了最大限度的減少查找路徑的長度，提供查找效率
B樹在數據庫中有一些應用，如mongodb的索引使用了B樹結構。但是在很多數據庫應用中，使用了是B樹的變種B+樹

B+樹

B+樹是B樹的一種變形形式，B+樹上的葉子結點存儲關鍵字以及相應記錄的地址，葉子結點以上各層作為索引使用。一棵m階的B+樹定義如下

1. 每個結點至多有m個子女；
2. 除根結點外，每個結點至少有[m/2]個子女，根結點至少有兩個子女；
3. 有k個子女的結點必有k個關鍵字

B+樹的查找與B樹不同，當索引部分某個結點的關鍵字與所查的關鍵字相等時，并不停止查找，應繼續沿著這個關鍵字左邊的指針向下，一直查到該關鍵字所在的葉子結點為止。

B+樹也是多路平衡查找樹，其與B樹的區別主要在于：

• B樹中每個節點（包括葉節點和非葉節點）都存儲真實的數據，B+樹中只有葉子節點存儲真實的數據，非葉節點只存儲鍵。
  在MySQL中，這里所說的真實數據，可能是行的全部數據（如Innodb的聚簇索引），也可能只是行的主鍵（如Innodb的輔助索引），或者是行所在的地址（如MyIsam的非聚簇索引）
  點擊了解MySQL中索引數據結構分析
• B樹中一條記錄只會出現一次，不會重復出現，而B+樹的鍵則可能重復重現——一定會在葉節點出現，也可能在非葉節點重復出現。
• B+樹的葉節點之間通過雙向鏈表鏈接
• B樹中的非葉節點，記錄數比子節點個數少1；而B+樹中記錄數與子節點個數相同。

由此，B+樹與B樹相比，有以下優勢：

• 更少的IO次數：B+樹的非葉節點只包含鍵，而不包含真實數據，因此每個節點存儲的記錄個數比B樹多很多（即階m更大），因此B+樹的高度更低，訪問時所需要的IO次數更少。此外，由于每個節點存儲的記錄數更多，所以對訪問局部性原理的利用更好，緩存命中率更高。
• 更適于范圍查詢：在B樹中進行范圍查詢時，首先找到要查找的下限，然后對B樹進行中序遍歷，直到找到查找的上限；而B+樹的范圍查詢，只需要對鏈表進行遍歷即可。
• 更穩定的查詢效率：B樹的查詢時間復雜度在1到樹高之間(分別對應記錄在根節點和葉節點)，而B+樹的查詢復雜度則穩定為樹高，因為所有數據都在葉節點。

B+樹也存在劣勢：由于鍵會重復出現，因此會占用更多的空間。但是與帶來的性能優勢相比，空間劣勢往往可以接受，因此B+樹的在數據庫中的使用比B樹更加廣泛。

B*樹

B*樹是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；
B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3(代替B+樹的1/2)；

B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數據復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針；

B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那么將一部分數據移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，并各復制1/3的數據到新結點，最后在父結點增加新結點的指針；所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高

B樹類型總結：

• 二叉搜索樹：二叉樹，每個結點只存儲一個關鍵字，等于則命中，小于走左結點，大于走右結點；
• B樹(B-樹)：多路搜索樹，每個結點存儲M/2到M（M是指M階B樹）個關鍵字，非葉子結點存儲指向關鍵字范圍的子結點；所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中；
• B+樹：在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；
• B*樹：在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率從1/2提高到2/3