平衡二叉查找樹

平衡二叉搜索樹：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。常用算法有紅黑樹、AVL、Treap、伸展樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O（log2n），大大降低了操作的時間復雜度。

調整平衡的基本思想：?
當在二叉排序樹中插入一個節點時，首先檢查是否因插入而破壞了平衡，若破壞，則找出其中的最小不平衡二叉樹，在保持二叉排序樹特性的情況下，調整最小不平衡子樹中節點之間的關系，以達到新的平衡。?
所謂最小不平衡子樹，指離插入節點最近且以平衡因子的絕對值大于1的節點作為根的子樹。

先插入指定節點，記錄下當前節點的信息，LH，EH或者RH。?
1. 若左子樹高LH，查看其左子樹根節點的信息，若是LH，則一次右旋；若是RH，則一次左旋+一次右旋?
2. 若右子樹高RH，查看右子樹根節點的信息，若是RH，則一次左旋；若是LH，則一次右旋+一次左旋?
3. 調整改變的節點信息

追求絕對的高度平衡，隨著樹的高度的增加，動態插入和刪除的代價也隨之增加

紅黑樹

紅黑樹參考?
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹?
紅黑樹和AVL樹類似，都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。?
二叉平衡樹的嚴格平衡策略以犧牲建立查找結構(插入，刪除操作)的代價，換來了穩定的O(logN) 的查找時間復雜度?
它雖然是復雜的，但它的最壞情況運行時間也是非常良好的，并且在實踐中是高效的： 它可以在O(log n)時間內做查找，插入和刪除，這里的n 是樹中元素的數目。

(1) 每個節點或者是黑色，或者是紅色。 (2) 根節點是黑色。 (3) 每個葉子節點是黑色。 [注意：這里葉子節點，是指為空的葉子節點！] (4) 如果一個節點是紅色的，則它的子節點必須是黑色的。 (5) 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

RBT 的操作代價分析：?
(1) 查找代價：由于紅黑樹的性質(最長路徑長度不超過最短路徑長度的2倍)，可以說明紅黑樹雖然不像AVL一樣是嚴格平衡的，但平衡性能還是要比BST要好。其查找代價基本維持在O(logN)左右，但在最差情況下(最長路徑是最短路徑的2倍少1)，比AVL要略遜色一點。?
(2) 插入代價：RBT插入結點時，需要旋轉操作和變色操作。但由于只需要保證RBT基本平衡就可以了。因此插入結點最多只需要2次旋轉，這一點和AVL的插入操作一樣。雖然變色操作需要O(logN)，但是變色操作十分簡單，代價很小。?
(3) 刪除代價：RBT的刪除操作代價要比AVL要好的多，刪除一個結點最多只需要3次旋轉操作。?
RBT 效率總結 : 查找 效率最好情況下時間復雜度為O(logN)，但在最壞情況下比AVL要差一些，但也遠遠好于BST。?
插入和刪除操作改變樹的平衡性的概率要遠遠小于AVL（RBT不是高度平衡的）。因此需要的旋轉操作的可能性要小，而且一旦需要旋轉，插入一個結點最多只需要旋轉2次，刪除最多只需要旋轉3次(小于AVL的刪除操作所需要的旋轉次數)。雖然變色操作的時間復雜度在O(logN)，但是實際上，這種操作由于簡單所需要的代價很小。

紅黑樹能夠以O(log2(N))的時間復雜度進行搜索、插入、刪除操作。此外,任何不平衡都會在3次旋轉之內解決。這一點是AVL所不具備的。

插入操作： 1.插入根節點（不需要操作） 2.父節點為黑色(不需要操作) 3.父節點和兄弟節點為紅色，祖父節點為黑色，只需要變色，將祖父節點遞歸檢查（原本檢查自己） 4.父節點為紅色，兄弟節點為黑色，祖父節點為紅色，先兩次旋轉再調整顏色（左旋+右旋） 刪除操作： 1.刪除只有一個新的根節點（直接刪除） 2.父節點為黑色，兄弟節點為紅色（先旋轉成左左，再刪除） 3.父節點為黑色，兄弟節點為黑色（先將兄弟節點換成紅色，變成情況2） 4.父節點為紅色，自己和兄弟節點為黑色（將父節點變成黑色，兄弟節點變成紅色，變成情況2） 5.兄弟節點為黑色，兄弟節點左子樹根節點為紅色（交換顏色，旋轉成為左左） 6.情況2和情況5，調整性質5（將N刪掉，用子節點頂替，若子節點為紅色，則重繪為黑色）

?
參考

B樹（多叉查找樹）：

1、根結點至少有兩個子女；?
2、每個非根節點所包含的關鍵字個數 j 滿足：m/2 - 1 <= j <= m - 1；?
3、除根結點以外的所有結點（不包括葉子結點）的度數正好是關鍵字總數加1，故內部子樹個數 k 滿足：m/2<= k <= m ；?
4、所有的葉子結點都位于同一層。?

B-樹

?
1、關鍵字集合分布在整棵樹中；?
2、任何一個關鍵字出現且只出現在一個結點中；?
3、搜索有可能在非葉子結點結束；?
4、其搜索性能等價于在關鍵字全集內做一次二分查找；?
5、自動層次控制；?
m階B-樹?
1) 樹中每個結點至多有m個孩子；?
2) 除根結點和葉子結點外，其它每個結點至少有[m/2]個孩子；?
3) 若根結點不是葉子結點，則至少有2個孩子；?
4) 所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息(可以看做是外部接點或查詢失敗的接點，實際上這些結點不存在，指向這些結點的指針都為null)；?
5) 每個非終端結點中包含有n個關鍵字信息： (n，A0，K1，A1，K2，A2，……，Kn，An)。其中，?
a) Ki (i=1…n)為關鍵字，且關鍵字按順序排序Ki < K(i-1)。?
b) Ai為指向子樹根的接點，且指針A(i-1)指向子樹種所有結點的關鍵字均小于Ki，但都大于K(i-1)。?
c) 關鍵字的個數n必須滿足： [m/2]-1 <= n <= m-1?
建立?
由于B~樹結點中的關鍵字個數必須>=[m/2]-1。因此和平衡二叉樹不同，每一次插入一個關鍵字并不是在樹中添加一個結點，而是首先在最低層的某個非終端結點中添加一個關鍵字，若該結點的關鍵字個數不超過m-1，則插入完成。否則，要產生結點的”分裂” 。?
外存?
我們現在把整棵樹構造在磁盤中，假如每個盤塊可以正好存放一個B~樹的結點（正好存放2個文件名）。那么一個BTNode結點就代表一個盤塊，而子樹指針就是存放另外一個盤塊 （詳細見《外部存儲器—磁盤 》）的地址。?
現在我們模擬查找文件29的過程：?
(1) 根據根結點指針找到文件目錄的根磁盤塊1，將其中的信息導入內存。【磁盤IO操作1次】?
(2) 此時內存中有兩個文件名17，35和三個存儲其他磁盤頁面地址的數據。根據算法我們發現17<29<35，因此我們找到指針p2。?
(3) 根據p2指針，我們定位到磁盤塊3，并將其中的信息導入內存。【磁盤IO操作2次】?
(4) 此時內存中有兩個文件名26，30和三個存儲其他磁盤頁面地址的數據。根據算法我們發現26<29<30，因此我們找到指針p2。?
(5) 根據p2指針，我們定位到磁盤塊8，并將其中的信息導入內存。【磁盤IO操作3次】?
(6) 此時內存中有兩個文件名28，29。根據算法我們查找到文件29，并定位了該文件內存的磁盤地址。

分析一下上面的過程，我們發現需要3次磁盤IO操作和3次內存查找操作。關于內存中的文件名查找，由于是一個有序表結構，可以利用折半查找提高效率。至于3次磁盤IO操作時影響整個B~樹查找效率的決定因素。當然，如果我們使用平衡二叉樹的磁盤存儲結構來進行查找，磁盤IO操作最少4次，最多5次。而且文件越多，B~樹比平衡二叉樹所用的磁盤IO操作次數將越少，效率也越高。

B+樹：

B+ 樹是一種樹數據結構，是一個n叉樹，每個節點通常有多個孩子，一顆B+樹包含根節點、內部節點和葉子節點。根節點可能是一個葉子節點，也可能是一個包含兩個或兩個以上孩子節點的節點。?
B+ 樹通常用于數據庫和操作系統的文件系統中。?
NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系統都在使用B+樹作為元數據索引。?
B+ 樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間復雜度。?
B+ 樹元素自底向上插入。?
?
所有的葉子結點中包含了全部關鍵字的信息，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序鏈接。(而B 樹的葉子節點并沒有包括全部需要查找的信息)?
所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。(而B 樹的非終節點也包含需要查找的有效信息)

1) 有n棵子樹的結點中含有n個關鍵字； (B~樹是n棵子樹有n+1個關鍵字) 2) 所有的葉子結點中包含了全部關鍵字的信息，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序鏈接。 (B~樹的葉子節點并沒有包括全部需要查找的信息) 3) 所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。 (B~樹的非終節點也包含需要查找的有效信息)B+樹的有效內容均在葉子節點，B-樹的有效內容不全在葉子節點上 B+樹的頭指針有兩個，一個指向根節點，另一個指向關鍵字最小的元素，因此B+樹有兩種遍歷的方式： 1.從根節點開始隨機查詢 2.從最小關鍵詞順序查詢

B*樹

為什么說B+樹比B 樹更適合實際應用中操作系統的文件索引和數據庫索引？

B+樹的磁盤讀寫代價更低?
B+樹的內部結點并沒有指向關鍵字具體信息的指針。因此其內部結點相對B 樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那么盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。?
舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體信息指針2bytes。一棵9階B-tree(一個結點最多8個關鍵字)的內部結點需要2個盤快。而B+樹內部結點只需要1個盤快。當需要把內部結點讀入內存中的時候，B 樹就比B+樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。

B+樹的查詢效率更加穩定?
由于非終結點并不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。

B+樹和B-樹的區別

B+樹?
性質：B+樹是B-樹的變體，也是一種多路搜索樹：?
　　

1.其定義基本與B-樹同，除了： 2.非葉子結點的子樹指針與關鍵字個數相同； 3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區間）； 4.為所有葉子結點增加一個鏈指針； 5.所有關鍵字都在葉子結點出現；

B-樹?
性質：是一種多路搜索樹（并不是二叉的）：?
　　

1.定義任意非葉子結點最多只有M個兒子；且M>2； 2.根結點的兒子數為[2, M]； 3.除根結點以外的非葉子結點的兒子數為[M/2, M]； 4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字） 5.非葉子結點的關鍵字個數=指向兒子的指針個數-1； 6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]； 7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹； 8.所有葉子結點位于同一層；

紅黑樹和平衡二叉樹區別如下：?
1、紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間復雜度相差不大的情況下，保證每次插入最多只需要三次旋轉就能達到平衡，實現起來也更為簡單。?
2、平衡二叉樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩，每次插入新節點之后需要旋轉的次數不能預知。

小結

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

另外：MySql的InnoDB引擎和MyIsam引擎存儲數據結構是B+樹，HashMap單個節點沖突域長度大于8則自動轉換為紅黑樹。

總結

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

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