自平衡二叉查找樹 - gaochundong－IT工程師數位筆記本

文章出處

自平衡二叉查找樹（Self-Balancing Binary Search Tree）

AVL 樹
紅黑樹（Red-Black Tree）

自平衡二叉查找樹（Self-Balancing Binary Search Tree）

實際上，BST 操作的運行時間與樹的高度（Height）是有關系的。一個樹的高度指的是從樹的根開始所能到達的最長的路徑長度。樹的高度可被遞歸性地定義為：

如果節點沒有子節點，則高度為 0；
如果節點只有一個子節點，則高度為該子節點的高度加 1；
如果節點有兩個子節點，則高度為兩個子節點中高度較高的加 1；

計算樹的高度要從葉子節點開始，首先將葉子節點的高度置為 0，然后根據上面的規則向上計算父節點的高度。以此類推直到樹中所有的節點高度都被標注后，則根節點的高度就是樹的高度。

下圖顯示了幾棵已經計算好高度的 BST 樹。

如果樹中節點的數量為 n，則一棵滿足O(log₂n) 漸進運行時間的 BST 樹的高度應接近于比 log₂n 小的最大整數。

上圖中的三棵 BST 樹中，樹（b）擁有最好的高度與節點數量的比例。樹（b）的高度為 3 ，節點數量為 8，所以 log₂8 = 3，結果正好與樹的高度相等。

樹（a）的節點數量為 10，而高度為 4，log₂10 = 3.3219，比 3.3219 小的最大整數是 3，所以樹（a）最理想的高度應該為 3。我們可以通過移動距離最遠的節點到中間的某個非葉子節點，以減少數的高度，以使該樹的高度與節點數量的比例達到最優。

樹（c）的情況是最差的，它的節點數量是 5，所以log₂5 = 2.3219，則理想高度為 2，但實際上是 4。

實際上我們真正面對的問題是如何保證 BST 的拓撲結構始終保持樹高度與節點數量的最佳比例。因為 BST 的拓撲結構與節點的插入順序息息相關，一種方式是通過數據的亂序來保證。如果在向樹中插入節點前就可以得到數據還好說，而如果我們無法掌控數據的來源呢？比如，數據來自用戶的輸入，或者來自傳感器的實時數據等，基本上要保證數據亂序是沒希望了。那么，另一種方案就是在不試圖讓數據源決定數據順序的情況下，新的節點插入后仍然可以保持 BST 樹的平衡（balanced）。這種能夠始終維持樹平衡狀態的數據結構稱為自平衡二叉查找樹（self-balancing binary search tree）。

一棵平衡樹指的是樹能夠保持其高度與廣度能夠保持預先定義的比例。不同的數據結構可以定義不同的比例以保持平衡，但所有的比例都趨向于log₂n。那么，一顆自平衡的 BST 也同樣呈現出 O(log₂n) 的漸進運行時間。

有許多種不同的自平衡 BST 數據結構，例如 AVL 樹、紅黑樹（Red-Black Tree）、2-3 樹、2-3-4 樹、伸展樹（Splay Tree）、B 樹等等。本文中我們將簡要介紹其中的兩種：AVL 樹和紅黑樹。

AVL 樹

在 1962 年，俄羅斯數學家 G. M. Andel'son-Vel-skii 和 E. M. Landis 發明了第一種自平衡二叉查找樹，叫做 AVL 樹。AVL 樹必須維持如下平衡條件，對每個節點 n：

節點 n 的左子樹的高度與右子樹的高度的差至多是 1。

節點的左子樹或者右子樹的高度可以通過上面描述的步驟來計算。如果節點僅有一個子節點，則無子節點側的高度為 -1。

下圖展示了概念上 AVL 樹節點的兩側子樹高度需要保持的關系。

下面是一些 BST 樹。節點中的數字代表著節點的值，左右兩側的數字代表著左右子樹的高度。其中樹（a）和樹（b）是合法的 AVL 樹，而樹（c）和樹（d）則不合法，因為樹中不是所有的節點都滿足 AVL 的平衡性質要求。

當創建一棵 AVL 樹時，難點在于如何保證 AVL 的平衡性質要求，而不用關注對樹的具體操作。也就是說，無論是向樹添加節點還是刪除節點，最重要的事情就是保持樹的平衡。AVL 樹通過 "旋轉操作（rotations）" 來保持樹的平衡。旋轉操作可以重塑樹的拓撲結構來恢復樹的平衡，更重要的是，重塑后的樹依然符合二叉查找樹的性質要求。

當向一棵 AVL 樹中插入一個新的節點時，需要經過兩階段的過程。首先，插入新節點的操作將使用與向 BST 樹中插入新節點時使用的相同的查找算法。新的節點將做為一個葉子節點被添加到樹中合適的位置，以滿足 BST 的性質要求。在添加完節點后，將導致樹的結構可能已經違背 AVL 樹的性質要求。所以在第二個階段中，將遍歷訪問路徑，來檢查每個節點左右子樹高度。如果存在某節點的左右子樹的高度差大于 1 時，則需要使用旋轉操作來處理。

下圖闡述了對節點 3 進行旋轉操作的步驟。在階段一插入新節點 2 后，在節點 5 處的 AVL 樹的平衡性質已經被破壞，因為節點 5 的左右子樹的差為 2，大于 AVL 樹要求的 1。為了解決這個問題，需要在節點 5 的左子樹的根節點，也就是節點 3 處做旋轉操作。這個旋轉操作不僅恢復了 AVL 樹的平衡要求，而且也保持了 BST 的性質要求。

有時除了像上圖中描述的簡單的旋轉操作之外，可能還需要進行多次旋轉操作。對于成組的旋轉操作的深入討論已經超出了本篇文章的范疇，這里就不再贅述了。最重要的就是要意識到插入操作和刪除操作都會破壞 AVL 樹的平衡，而旋轉操作就是解決這些問題的法寶。

通過確保所有節點的左右子樹的差小于等于 1，AVL 樹保證了插入、刪除和查找操作將始終保持 O(log₂n) 的漸進運行時間，而與插入或刪除節點的順序無關。

紅黑樹（Red-Black Tree）

在 1972 年，慕尼黑理工大學（Technical University of Munich）的計算機科學家 Rudolf Bayer 創造了紅黑樹（Red-Black Tree）數據結構。除了包含數據和左右孩子節點之外，紅黑樹的節點還包含了一項特別的信息 -- 顏色。這個顏色只包含兩種顏色，即紅色和黑色。并且，紅黑樹還添加了一種特殊類型的節點，稱為 NIL 節點。NIL 節點將做為紅黑樹的偽葉子節點出現。也就是說，所有帶有關鍵數據的節點稱為內節點，而所有其他的外節點則均指向 NIL 節點。這個概念可能理解起來有些費勁，希望下面這張圖有所幫助。

紅黑樹（R-B Tree）需要滿足如下性質：

節點的顏色只能是紅色或者黑色；
根節點是黑色的；（根性質）
NIL 節點的顏色是黑色；
如果節點的顏色是紅色，則其子節點均為黑色；（紅性質）
從任一節點到其后代任一葉子節點的路徑上的黑色節點的數量相同；（黑性質）

前面幾條性質都很好解釋，只有最后一條最難理解。簡單的說，從樹中任意一個節點開始，從該節點到其后代的任意一個 NIL 節點的路徑上的黑色節點的數量必須相同。比如上圖中，以根節點為例，從節點 41 到任意一個 NIL 節點的路徑上，黑色節點的數量都是相同的，也就是 3 個。如從節點 41 到左下角的 NIL 節點的路徑上，黑色節點包括 41, 2, NIL，所以黑色節點數量是 3 個。

類似于 AVL 樹，紅黑樹也是一種自平衡二叉查找樹。AVL 樹的平衡性質是通過限制節點的左右子樹的高度來達成，而紅黑樹則是通過更形象化的方式來保證樹的平衡。如果一棵樹滿足紅黑樹的性質，其節點的總數量為 n，則它的高度將始終小于 2 * log₂(n+1) 。鑒于這個原因，致使紅黑樹保證了對樹的所有操作都能在 O(log₂n) 漸進運行時間范圍內。

同樣是和 AVL 樹一樣，當對紅黑樹進行節點的插入和刪除時，最終要的就是使其仍然符合紅黑樹的性質。AVL 樹通過使用旋轉操作（rotations）來恢復樹的平衡。而紅黑樹則是通過重新著色（recoloring）和旋轉兩種操作共同來完成。這不僅需要判斷節點的父節點的顏色，還需要對比叔父節點的顏色，使得紅黑樹的恢復過程變得更加復雜。

向紅黑樹中插入新的節點時，需要考慮很多種情況。假設已存在紅黑樹 T，即將被插入的新節點為 K。

首先一種特殊情況就是如果樹 T 為空，則可直接將節點 K 設置為根節點，并且將顏色標為黑色，這樣即可滿足 R-B 樹的所有要求。

如果樹 T 不為空，則需要遵循如下步驟：