常用樹類資料結構總結-二叉查找樹(BST)，平衡二叉查找樹(AVL)，紅黑樹(RBT)，B~/B+樹(B-tree）的性能分析

http://www.iteye.com/topic/614070

此少俠總結的特棒，直接收藏了。

我們這個專題介紹的動态查找樹主要有： 二叉查找樹(BST)，平衡二叉查找樹(AVL)，紅黑樹(RBT)，B~/B+樹(B-tree)。這四種樹都具備下面幾個優勢：

(1) 都是動态結構。在删除，插入操作的時候，都不需要徹底重建原始的索引樹。最多就是執行一定量的旋轉，變色操作來有限的改變樹的形态。而這些操作所付出的代價都遠遠小于重建一棵樹。這一優勢在《查找結構專題(1)：靜态查找結構概論 》中講到過。

(2) 查找的時間複雜度大體維持在O(log(N))數量級上。可能有些結構在最差的情況下效率将會下降很快，比如BST。這個會在下面的對比中詳細闡述。

下面我們開始概括性描述這四種樹，并互相比較一下優劣。

1. 二叉查找樹 (Binary Search Tree) 詳細見《查找結構專題(2)：二叉查找樹 [BST] 》

很顯然，二叉查找樹的發現完全是因為靜态查找結構在動态插入，删除結點所表現出來的無能為力(需要付出極大的代價)。

BST 的操作代價分析：

(1) 查找代價： 任何一個資料的查找過程都需要從根結點出發，沿某一個路徑朝葉子結點前進。是以查找中資料比較次數與樹的形态密切相關。

當樹中每個結點左右子樹高度大緻相同時，樹高為logN。則平均查找長度與logN成正比，查找的平均時間複雜度在O(logN)數量級上。

當先後插入的關鍵字有序時，BST退化成單支樹結構。此時樹高n。平均查找長度為(n+1)/2，查找的平均時間複雜度在O(N)數量級上。

(2) 插入代價： 新結點插入到樹的葉子上，完全不需要改變樹中原有結點的組織結構。插入一個結點的代價與查找一個不存在的資料的代價完全相同。

(3) 删除代價： 當删除一個結點P，首先需要定位到這個結點P，這個過程需要一個查找的代價。然後稍微改變一下樹的形态。如果被删除結點的左、右子樹隻有一個存在，則改變形态的代價僅為O(1)。如果被删除結點的左、右子樹均存在，隻需要将當P的左孩子的右孩子的右孩子的...的右葉子結點與P互換，在改變一些左右子樹即可。是以删除操作的時間複雜度最大不會超過O(logN)。

BST效率總結 : 查找最好時間複雜度O(logN)，最壞時間複雜度O(N)。

插入删除操作算法簡單，時間複雜度與查找差不多

2. 平衡二叉查找樹 ( Balanced Binary Search Tree ) 詳細見《查找結構專題(3)：平衡二叉查找樹 [AVL] 》

二叉查找樹在最差情況下竟然和順序查找效率相當，這是無法仍受的。事實也證明，當存儲資料足夠大的時候，樹的結構對某些關鍵字的查找效率影響很大。當然，造成這種情況的主要原因就是BST不夠平衡(左右子樹高度差太大)。

既然如此，那麼我們就需要通過一定的算法，将不平衡樹改變成平衡樹。是以，AVL樹就誕生了。

AVL 的操作代價分析：

(1) 查找代價： AVL是嚴格平衡的BST（平衡因子不超過1）。那麼查找過程與BST一樣，隻是AVL不會出現最差情況的BST(單支樹)。是以查找效率最好，最壞情況都是O(logN)數量級的。

(2) 插入代價： AVL必須要保證嚴格平衡(|bf|<=1)，那麼每一次插入資料使得AVL中某些結點的平衡因子超過1就必須進行旋轉操作。事實上，AVL的每一次插入結點操作最多隻需要旋轉1次(單旋轉或雙旋轉)。是以，總體上插入操作的代價仍然在O(logN)級别上(插入結點需要首先查找插入的位置)。

(3) 删除代價：AVL删除結點的算法可以參見BST的删除結點，但是删除之後必須檢查從删除結點開始到根結點路徑上的所有結點的平衡因子。是以删除的代價稍微要大一些。每一次删除操作最多需要O(logN)次旋轉。是以，删除操作的時間複雜度為O(logN)+O(logN)=O(2logN)

AVL 效率總結 : 查找的時間複雜度維持在O(logN)，不會出現最差情況

AVL樹在執行每個插入操作時最多需要1次旋轉，其時間複雜度在O(logN)左右。

AVL樹在執行删除時代價稍大，執行每個删除操作的時間複雜度需要O(2logN)。

3. 紅黑樹 (Red-Black Tree ) 詳細見《查找結構專題(4)：紅黑樹 [RBT] 》

二叉平衡樹的嚴格平衡政策以犧牲建立查找結構(插入，删除操作)的代價，換來了穩定的O(logN) 的查找時間複雜度。但是這樣做是否值得呢？

能不能找一種折中政策，即不犧牲太大的建立查找結構的代價，也能保證穩定高效的查找效率呢？ 答案就是：紅黑樹。

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)，但是實際上，這種操作由于簡單所需要的代價很小。

4. B~樹/B+樹 (B-Tree ) 詳細見《查找結構專題(5)：B~樹/B+樹 》

對于在記憶體中的查找結構而言，紅黑樹的效率已經非常好了(實際上很多實際應用還對RBT進行了優化)。但是如果是資料量非常大的查找呢？将這些資料全部放入記憶體組織成RBT結構顯然是不實際的。實際上，像OS中的檔案目錄存儲，資料庫中的檔案索引結構的存儲.... 都不可能在記憶體中建立查找結構。必須在磁盤中建立好這個結構。那麼在這個背景下，RBT還是一種好的選擇嗎？

在磁盤中組織查找結構，從任何一個結點指向其他結點都有可能讀取一次磁盤資料，再将資料寫入記憶體進行比較。大家都知道，頻繁的磁盤IO操作，效率是很低下的(機械運動比電子運動要慢不知道多少)。顯而易見，所有的二叉樹的查找結構在磁盤中都是低效的。是以，B樹很好的解決了這一個問題。

B-Tree的操作代價分析：

(1) 查找代價： B-Tree作為一個平衡多路查找樹(m-叉)。B樹的查找分成兩種：一種是從一個結點查找另一結點的位址的時候，需要定位磁盤位址(查找位址)，查找代價極高。另一種是将結點中的有序關鍵字序列放入記憶體，進行優化查找(可以用折半)，相比查找代價極低。而B樹的高度很小，是以在這一背景下，B樹比任何二叉結構查找樹的效率都要高很多。而且B+樹作為B樹的變種，其查找效率更高。

(2)插入代價： B-Tree的插入會發生結點的分裂操作。當插入操作引起了s個節點的分裂時，磁盤通路的次數為h(讀取搜尋路徑上的節點)＋2s(回寫兩個分裂出的新節點)＋1（回寫新的根節點或插入後沒有導緻分裂的節點）。是以，所需要的磁盤通路次數是h+2s+1，最多可達到3h+1。是以插入的代價是很大的。

(3)删除代價：B-Tree的删除會發生結點合并操作。最壞情況下磁盤通路次數是3h＝（找到包含被删除元素需要h次

讀通路）+（擷取第2至h層的最相鄰兄弟需要h-1次讀通路）+（在第3至h層的合并需要h-2次寫

通路）+（對修改過的根節點和第2層的兩個節點進行3次寫通路）

B-Tree效率總結： 由于考慮磁盤儲存結構，B樹的查找、删除、插入的代價都遠遠要小于任何二叉結構樹(讀寫磁盤次數的降低)。

動态查找樹結構的對比：

(1) 平衡二叉樹和紅黑樹 [AVL PK RBT]

AVL 和RBT 都是二叉查找樹的優化。其性能要遠遠好于二叉查找樹。他們之間都有自己的優勢，其應用上也有不同。

結構對比： AVL的結構高度平衡，RBT的結構基本平衡。平衡度AVL > RBT.

查找對比： AVL 查找時間複雜度最好，最壞情況都是O(logN)。

RBT 查找時間複雜度最好為O(logN)，最壞情況下比AVL略差。

插入删除對比： 1. AVL的插入和删除結點很容易造成樹結構的不平衡，而RBT的平衡度要求較低。是以在大量資料插入的情況下，RBT需要通過旋轉變色操作來重新達到平衡的頻度要小于AVL。

2. 如果需要平衡處理時，RBT比AVL多一種變色操作，而且變色的時間複雜度在O(logN)數量級上。但是由于操作簡單，是以在實踐中這種變色仍然是非常快速的。

3. 當插入一個結點都引起了樹的不平衡，AVL和RBT都最多需要2次旋轉操作。但删除一個結點引起不平衡後，AVL最多需要logN 次旋轉操作，而RBT最多隻需要3次。是以兩者插入一個結點的代價差不多，但删除一個結點的代價RBT要低一些。

4. AVL和RBT的插入删除代價主要還是消耗在查找待操作的結點上。是以時間複雜度基本上都是與O(logN) 成正比的。

總體評價：大量資料實踐證明，RBT的總體統計性能要好于平衡二叉樹。

(2) B~樹和B+樹 [ B~Tree PK B+Tree]

B+樹是B~樹的一種變體，在磁盤查找結構中，B+樹更适合檔案系統的磁盤存儲結構。

結構對比： B~樹是平衡多路查找樹，所有結點中都包含了待查關鍵字的有效資訊(比如檔案磁盤指針)。每個結點若有n個關鍵字，則有n+1個指向其他結點的指針。

B+樹嚴格意義上說已經不是樹，它的葉子結點之間也有指針連結。B+樹的非終結點中并不含有關鍵字的資訊，需要查找的關鍵字的全部資訊都包含在葉子結點上。非終結點中隻作為葉子結點關鍵字的索引而存在。

查找對比：1. 在相同數量的待查資料下，B+樹查找過程中需要調用的磁盤IO操作要少于普通B~樹。由于B樹所在的磁盤存儲背景下，是以B+樹的查找性能要好于B~樹。

2. B+樹的查找效率更加穩定，因為所有葉子結點都處于同一層中，而且查找所有關鍵字都必須走完從根結點到葉子結點的全部曆程。是以同一顆B+樹中，任何關鍵字的查找比較次數都是一樣的。而B樹就不一定了，可能查找到某一個非終結點就結束了。

插入删除對比： B+樹與B~樹在插入删除操作中的效率是差不多的。

總體評價：在應用背景下，特别是檔案結構存儲中。B+樹的應用要更多，其效率也要比B~樹好。

字元串查找結構

這次專題所講的BST、AVL、BRT、B~Tree等可以勝任對任何關鍵字資料進行查找。但對字元串的查找(字元串比對)結構，有專門的結構和算法。詳見：《KMP算法 》，《Trie Tree 》