<a href="http://www.cnblogs.com/gaochundong/p/self_balancing_binary_search_tree.html#self-balancing-binary-search-tree">自平衡二叉查找樹（Self-Balancing Binary Search Tree）</a>
<a href="http://www.cnblogs.com/gaochundong/p/self_balancing_binary_search_tree.html#avl-tree">AVL 樹</a>
<a href="http://www.cnblogs.com/gaochundong/p/self_balancing_binary_search_tree.html#read-black-tree">紅黑樹（Red-Black Tree）</a>
如果節點沒有子節點，則高度為 0；
如果節點隻有一個子節點，則高度為該子節點的高度加 1；
如果節點有兩個子節點，則高度為兩個子節點中高度較高的加 1；
計算樹的高度要從葉子節點開始，首先将葉子節點的高度置為 0，然後根據上面的規則向上計算父節點的高度。以此類推直到樹中所有的節點高度都被标注後，則根節點的高度就是樹的高度。
如果樹中節點的數量為 n，則一棵滿足O(log2n) 漸進運作時間的 BST 樹的高度應接近于比 log2n 小的最大整數。
上圖中的三棵 BST 樹中，樹（b）擁有最好的高度與節點數量的比例。樹（b）的高度為 3 ，節點數量為 8，是以 log28 = 3，結果正好與樹的高度相等。
樹（a）的節點數量為 10，而高度為 4，log210 = 3.3219，比 3.3219 小的最大整數是 3，是以樹（a）最理想的高度應該為 3。我們可以通過移動距離最遠的節點到中間的某個非葉子節點，以減少數的高度，以使該樹的高度與節點數量的比例達到最優。
樹（c）的情況是最差的，它的節點數量是 5，是以log25 = 2.3219，則理想高度為 2，但實際上是 4。
實際上我們真正面對的問題是如何保證 BST 的拓撲結構始終保持樹高度與節點數量的最佳比例。因為 BST 的拓撲結構與節點的插入順序息息相關，一種方式是通過資料的亂序來保證。如果在向樹中插入節點前就可以得到資料還好說，而如果我們無法掌控資料的來源呢？比如，資料來自使用者的輸入，或者來自傳感器的實時資料等，基本上要保證資料亂序是沒希望了。那麼，另一種方案就是在不試圖讓資料源決定資料順序的情況下，新的節點插入後仍然可以保持 BST 樹的平衡（balanced）。這種能夠始終維持樹平衡狀态的資料結構稱為自平衡二叉查找樹（self-balancing binary search tree）。
一棵平衡樹指的是樹能夠保持其高度與廣度能夠保持預先定義的比例。不同的資料結構可以定義不同的比例以保持平衡，但所有的比例都趨向于log2n。那麼，一顆自平衡的 BST 也同樣呈現出 O(log2n) 的漸進運作時間。
有許多種不同的自平衡 BST 資料結構，例如 AVL 樹、紅黑樹（Red-Black Tree）、2-3 樹、2-3-4 樹、伸展樹（Splay Tree）、B 樹等等。本文中我們将簡要介紹其中的兩種：AVL 樹和紅黑樹。
節點 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(log2n) 的漸進運作時間，而與插入或删除節點的順序無關。
在 1972 年，慕尼黑理工大學（Technical University of Munich）的計算機科學家 Rudolf Bayer 創造了紅黑樹（Red-Black Tree）資料結構。除了包含資料和左右孩子節點之外，紅黑樹的節點還包含了一項特别的資訊 -- 顔色。這個顔色隻包含兩種顔色，即紅色和黑色。并且，紅黑樹還添加了一種特殊類型的節點，稱為 NIL 節點。NIL 節點将做為紅黑樹的僞葉子節點出現。也就是說，所有帶有關鍵資料的節點稱為内節點，而所有其他的外節點則均指向 NIL 節點。這個概念可能了解起來有些費勁，希望下面這張圖有所幫助。
節點的顔色隻能是紅色或者黑色；
根節點是黑色的；（根性質）
NIL 節點的顔色是黑色；
如果節點的顔色是紅色，則其子節點均為黑色；（紅性質）
從任一節點到其後代任一葉子節點的路徑上的黑色節點的數量相同；（黑性質）
前面幾條性質都很好解釋，隻有最後一條最難了解。簡單的說，從樹中任意一個節點開始，從該節點到其後代的任意一個 NIL 節點的路徑上的黑色節點的數量必須相同。比如上圖中，以根節點為例，從節點 41 到任意一個 NIL 節點的路徑上，黑色節點的數量都是相同的，也就是 3 個。如從節點 41 到左下角的 NIL 節點的路徑上，黑色節點包括 41, 2, NIL，是以黑色節點數量是 3 個。
類似于 AVL 樹，紅黑樹也是一種自平衡二叉查找樹。AVL 樹的平衡性質是通過限制節點的左右子樹的高度來達成，而紅黑樹則是通過更形象化的方式來保證樹的平衡。如果一棵樹滿足紅黑樹的性質，其節點的總數量為 n，則它的高度将始終小于 2 * log2(n+1) 。鑒于這個原因，緻使紅黑樹保證了對樹的所有操作都能在 O(log2n) 漸進運作時間範圍内。
同樣是和 AVL 樹一樣，當對紅黑樹進行節點的插入和删除時，最終要的就是使其仍然符合紅黑樹的性質。AVL 樹通過使用旋轉操作（rotations）來恢複樹的平衡。而紅黑樹則是通過重新着色（recoloring）和旋轉兩種操作共同來完成。這不僅需要判斷節點的父節點的顔色，還需要對比叔父節點的顔色，使得紅黑樹的恢複過程變得更加複雜。
向紅黑樹中插入新的節點時，需要考慮很多種情況。假設已存在紅黑樹 T，即将被插入的新節點為 K。
首先一種特殊情況就是如果樹 T 為空，則可直接将節點 K 設定為根節點，并且将顔色标為黑色，這樣即可滿足 R-B 樹的所有要求。
如果樹 T 不為空，則需要遵循如下步驟：
使用 BST 插入算法将節點 K 插入到樹 T 中；
将節點 K 着色為紅色；
如果需要，則重塑 R-B 樹的性質；
我們知道 BST 樹總是将新節點添加為葉子節點，是以将節點 K 插入到樹 T 中不會破壞根性質。而添加一個紅色的葉子節點也不會影響樹 T 的黑性質。實際上，添加一個紅色的葉子節點僅有可能影響樹 T 的紅性質，是以我們僅需檢查樹的紅性質，如果紅性質被違背，則需要重塑樹結構以重新滿足紅黑樹性質。
我們将節點 K 的父節點稱為節點 P（parent node），将節點 P 的父節點稱為節點 G（grandparent node），将節點 P 的兄弟節點稱為節點 S（sibling node）。
當向非空樹 T 中插入節點 K 時，将直接受到父節點 P 的顔色的影響，可能會遇到如下多種情況。
情況1：節點 P 是黑色。
如果 P 為黑色，而節點 K 為紅色，是以實際上不會違背紅性質，則樹 T 已經滿足所有紅黑樹性質條件。
情況2：節點 P 是紅色。
如果節點 P 為紅色，那麼 P 現在有了新的子節點 K，并且 K 也為紅色，是以已經違背了紅性質。為了處理這種兩個紅節點的情況，我們需要考慮節點 G 的其他子節點，也就是節點 P 的兄弟節點 S。此時，會有兩種情況發生：
情況 2a：節點 S 是黑色或者為空。
如果節點 S 是黑色或者為空，則需要對節點 K、P、G 進行旋轉。根據 K、P、G 順序的不同，旋轉操作可能存在四種可能性。
前兩種可能性為當 P 為 G 的左子節點時。
如果 S 為空，則上圖中直接将 S 删除即可。
另兩種可能性為當 P 為 G 的右子節點時，正好與上面圖中的過程相反。
旋轉操作過程結束後，雙紅節點情況已經被合理的解決了。
情況 2b：節點 S 是紅色。
如果 P 的兄弟節點 S 是紅色，則需要對 P、S、G 進行重新着色：将 P 和 S 着色為黑色，将 G 着色為紅色。
重新着色操作不會影響樹 T 的黑性質，因為當 P、G 的顔色更改時，所有路徑上的黑色節點數量并沒有改變。但是，重新着色可能會使 G 和 G 的父節點産生雙紅情況。這種情況下，則需要從 G 和 G 的父節點開始繼續遵循處理 K 和 K 的父節點的方式遞歸式地解決雙紅問題。
對于紅黑樹深入的讨論不在本文的範疇，這裡不再贅述。
參考資料
<a href="http://msdn.microsoft.com/en-US/library/ms379572(v=vs.80).aspx">An Extensive Examination of Data Structures Using C# 2.0</a>
<a href="http://www.cnblogs.com/wayfarer/archive/2004/07/16/24703.aspx">考察資料結構 - 第三部分：二叉樹和BSTs[譯]</a>
<a href="http://en.wikipedia.org/wiki/Red%E2%80%93black_tree">Red–black tree</a>
<a href="https://www.cs.usfca.edu/~galles/visualization/RedBlack.html">Red/Black Tree Algorithm Visualization</a>
<a href="http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf">Left-Leaning Red-Black Trees</a>
<a href="http://pages.cs.wisc.edu/~hasti/cs367-1/readings/Red-Black-Trees/index.html">Red-Black Trees</a>
<a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-10-red-black-trees-rotations-insertions-deletions/lec10.pdf">Introduction to Algorithms ： LECTURE 10 Balanced Search Trees </a>
<a href="http://blog.csdn.net/v_july_v/article/details/6105630">教你透徹了解紅黑樹</a>
本文轉自匠心十年部落格園部落格，原文連結：http://www.cnblogs.com/gaochundong/p/self_balancing_binary_search_tree.html，如需轉載請自行聯系原作者