一、摘要

二叉樹，作為一種數據結構，在實際開發中，有著非常廣泛的應用，尤其是以平衡二叉樹、紅黑樹為代表，在前幾篇文章中，我們詳細的介紹了BST、AVL、RBT的算法以及代碼實踐，下面簡要概括描述一下這三種樹，以及它們之間的優劣。

二、BST

二叉查找樹（英文全稱：Binary Search Tree，簡稱：BST）是計算機科學中最早投入實際使用的一種樹形結構，特性定義比較粗放（一個節點，最多2個分支），因此在樹形形態結構上，有著多樣，例如下圖：

很明顯，不同的形狀，所需查找的次數是不一樣的！

BST 的操作過程：

• 查找操作：任何一個數據的查找過程都需要從根結點出發，沿某一個路徑朝葉子結點前進，因此查找中數據比較次數與樹的形態密切相關。

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

當樹形結構為一個單子樹時，此時樹高n，則平均查找長度為(n+1)/2，查找的平均時間復雜度在O(N)數量級上。

• 插入操作：先通過查找方法找到合適的位置，然后將新結點插入到樹的葉子上，完全不需要改變樹中原有結點的組織結構。

插入一個節點的時間與查找一個插入合適的位置的時間完全相同。

• 刪除代價：當刪除一個節點A，首先需要定位到這個節點A，這個過程需要一個查找的時間。然后根據樹的形態分析，如果被刪除結點的左、右子樹只有一個存在，則改變形態的代價僅為O(1)。如果被刪除結點的左、右子樹均存在，只需要將A節點的左孩子的最末端的右子樹或者A節點的右孩子的最末端的左子樹結點與A互換，最后刪除該節點即可。

刪除操作的時間復雜度最大不會超過O(logN)。

BST效率總結：

• 查找最好時間復雜度O(logN)，最壞時間復雜度O(N)。
• 插入、刪除操作算法簡單，時間復雜度與查找差不多。

三、AVL

二叉查找樹在最差情況下和順序查找效率相當，這點是無法忍受的。

平衡二叉查找樹的出現，主要是為了解決當二叉樹查找樹形態結構變成一個鏈條結構的時候，查找效率變低的問題，算法由Adel'son-Vel'skii和Landis兩位大神發明，同時也俗稱AVL樹，特性如下：

• 它的左子樹和右子樹都是平衡二叉樹；
• 且它的左子樹和右子樹的深度之差的絕對值（平衡因子 ） 不超過1；

簡單的說，就是為了保證平衡，當前節點的左子樹、右子樹的高度差不超過1！

當樹的左、右子樹高度超過差超過1時，核心就是通過左旋轉、右旋轉實現樹再次高度平衡。

AVL 的操作過程：

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

• 插入操作：AVL插入與BST思路一樣，不同的是AVL必須要保證嚴格平衡(height<=1)，每一次插入數據使得AVL中某些結點的平衡因子超過1就必須進行旋轉操作。事實上，AVL的每一次插入結點操作最多只需要旋轉1次(單旋轉或雙旋轉)。因此，總體上插入操作的代價仍然在O(logN)級別上(插入結點需要首先查找插入的位置)。

• 刪除操作：AVL刪除結點的算法與BST思路一樣，但是刪除之后必須檢查從刪除結點開始到根結點路徑上的所有結點的平衡因子。因此刪除的代價稍微要大一些。每一次刪除操作最多需要O(logN)次旋轉。因此，刪除操作的時間復雜度為O(logN)+O(logN)=O(2logN)。

AVL 效率總結：

• 查找的時間復雜度維持在O(logN)，不會出現最差情況。
• AVL樹在執行每個插入操作時最多需要1次旋轉(單旋轉或雙旋轉)，其時間復雜度在O(logN)左右。
• AVL樹在執行刪除時代價稍大，執行每個刪除操作的時間復雜度需要O(2logN)。

四、RBT

平衡二叉查找樹通過嚴格平衡策略以犧牲建立查找結構的代價，換來了穩定的查找時間復雜度。但是相對來說，在刪除方面，時間復雜度稍大。

于是就出現了平衡二叉B樹，后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的紅黑樹。

紅黑樹（英文全稱：red-black-tree，簡稱：RBT），特性如下：

• 1.每個節點要么是黑色要么是紅色；
• 2.根節點是黑色；
• 3.每個葉子節點是黑色；（注意：這里葉子節點，是指為空的葉子節點）
• 4.如果一個節點是紅色的，則它的子節點必須是黑色的；（說明父子節點之間不能出現兩個連續的紅節點）
• 5.從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點；

特性5確保沒有一條路徑會比其他路徑長出倆倍，因而，紅黑樹是相對的接近平衡的二叉樹，但是相比平衡二叉樹而言，尤其是刪除的時間復雜度，有所降低。

RBT 的操作過程：

• 查找操作：由于紅黑樹的性質(最長路徑長度不超過最短路徑長度的2倍)，可以說明紅黑樹雖然不像AVL一樣是嚴格平衡的，但平衡性能還是要比BST要好。其查找代價基本維持在O(logN)左右，但在最差情況下(最長路徑是最短路徑的2倍少1)，比AVL要略遜色一點。

• 插入操作：RBT插入結點時，需要旋轉操作和變色操作。但由于只需要保證RBT基本平衡就可以了。因此插入結點最多只需要2次旋轉，這一點和AVL的插入操作一樣。雖然變色操作需要O(logN)，但是變色操作十分簡單，代價很小。

• 刪除代價：RBT的刪除操作代價要比AVL要好的多，刪除一個結點最多只需要3次旋轉操作。

RBT 效率總結：

• 查找效率最好情況下時間復雜度為O(logN)，但在最壞情況下比AVL要差一些，但也遠遠好于BST。
• 插入和刪除操作改變樹的平衡性的概率要遠遠小于AVL（RBT不是高度平衡的）。因此需要的旋轉操作的可能性要小，而且一旦需要旋轉，插入一個結點最多只需要旋轉2次，刪除最多只需要旋轉3次(小于AVL的刪除操作所需要的旋轉次數)。雖然變色操作的時間復雜度在O(logN)，但是實際上，這種操作由于簡單所需要的代價很小。

五、總結

平衡二叉查找樹、紅黑樹，在查詢、插入、刪除操作方面都是基于二叉查找樹的算法思路，不同點是：插入、刪除之后的調整過程，平衡二叉查找樹主要是通過左旋轉、右旋轉實現樹高度再次平衡，而紅黑樹因為引進了顏色，相比平衡二叉查找樹，多了一個顏色轉換操作。

三者整體比較，紅黑樹要優于平衡二叉查找樹，遠優于二叉查找樹！

六、寫到最后

最近無意間獲得一份阿里大佬寫的技術筆記，內容涵蓋 Spring、Spring Boot/Cloud、Dubbo、JVM、集合、多線程、JPA、MyBatis、MySQL 等技術知識。需要的小伙伴可以點擊如下鏈接獲取，資源地址：技術資料筆記。

不會有人刷到這里還想白嫖吧？點贊對我真的非常重要！在線求贊。加個關注我會非常感激！