data_structure_and_algorithm -- 紅黑樹（上）：為什麼工程中都用紅黑樹這種二叉樹？
今天主要看一下紅黑樹，主要參考：前谷歌工程師王爭的課程，感興趣可以通過下面方式微信掃碼購買：
樹、二叉樹、二叉查詢樹。二叉查詢樹是最常用的一種二叉樹，它支援快速插入、刪除、查詢操作，各個操作的時間複雜度跟樹的高度成正比，理想情況下，時間複雜度是 O(logn)。
不過，二叉查詢樹在頻繁的動態更新過程中，可能會出現樹的高度遠大於 log2n 的情況，從而導致各個操作的效率下降。極端情況下，二叉樹會退化為連結串列，時間複雜度會退化到 O(n)。我上一節說了，要解決這個複雜度退化的問題，我們需要設計一種平衡二叉查詢樹，也就是今天要講的這種資料結構。
很多書籍裡，但凡講到平衡二叉查詢樹，就會拿紅黑樹作為例子。不僅如此，如果你有一定的開發經驗，你會發現，在工程中，很多用到平衡二叉查詢樹的地方都會用紅黑樹。你有沒有想過，為什麼工程中都喜歡用紅黑樹，而不是其他平衡二叉查詢樹呢？
帶著這個問題，讓我們一起來學習今天的內容吧！
什麼是“平衡二叉查詢樹”？
平衡二叉樹的嚴格定義是這樣的：二叉樹中任意一個節點的左右子樹的高度相差不能大於 1。從這個定義來看，上一節我們講的完全二叉樹、滿二叉樹其實都是平衡二叉樹，但是非完全二叉樹也有可能是平衡二叉樹。
平衡二叉查詢樹不僅滿足上面平衡二叉樹的定義，還滿足二叉查詢樹的特點。最先被髮明的平衡二叉查詢樹是AVL 樹，它嚴格符合我剛講到的平衡二叉查詢樹的定義，即任何節點的左右子樹高度相差不超過 1，是一種高度平衡的二叉查詢樹。
但是很多平衡二叉查詢樹其實並沒有嚴格符合上面的定義（樹中任意一個節點的左右子樹的高度相差不能大於 1），比如我們下面要講的紅黑樹，它從根節點到各個葉子節點的最長路徑，有可能會比最短路徑大一倍。
我們學習資料結構和演算法是為了應用到實際的開發中的，所以，我覺得沒必去死摳定義。對於平衡二叉查詢樹這個概念，我覺得我們要從這個資料結構的由來，去理解“平衡”的意思。
發明平衡二叉查詢樹這類資料結構的初衷是，解決普通二叉查詢樹在頻繁的插入、刪除等動態更新的情況下，出現時間複雜度退化的問題。
所以，平衡二叉查詢樹中“平衡”的意思，其實就是讓整棵樹左右看起來比較“對稱”、比較“平衡”，不要出現左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應的插入、刪除、查詢等操作的效率高一些。
所以，如果我們現在設計一個新的平衡二叉查詢樹，只要樹的高度不比 log2n 大很多（比如樹的高度仍然是對數量級的），儘管它不符合我們前面講的嚴格的平衡二叉查詢樹的定義，但我們仍然可以說，這是一個合格的平衡二叉查詢樹。
如何定義一棵“紅黑樹”？
平衡二叉查詢樹其實有很多，比如，Splay Tree（伸展樹）、Treap（樹堆）等，但是我們提到平衡二叉查詢樹，聽到的基本都是紅黑樹。它的出鏡率甚至要高於“平衡二叉查詢樹”這幾個字，有時候，我們甚至預設平衡二叉查詢樹就是紅黑樹，那我們現在就來看看這個“明星樹”。
紅黑樹的英文是“Red-Black Tree”，簡稱 R-B Tree。它是一種不嚴格的平衡二叉查詢樹，我前面說了，它的定義是不嚴格符合平衡二叉查詢樹的定義的。那紅黑樹究竟是怎麼定義的呢？
顧名思義，紅黑樹中的節點，一類被標記為黑色，一類被標記為紅色。除此之外，一棵紅黑樹還需要滿足這樣幾個要求：
（1）根節點是黑色的；
（2）每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不儲存資料；
（3）任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的；
（4）每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點；
這裡的第二點要求“葉子節點都是黑色的空節點”，稍微有些奇怪，它主要是為了簡化紅黑樹的程式碼實現而設定的，下一節我們講紅黑樹的實現的時候會講到。這節我們暫時不考慮這一點，所以，在畫圖和講解的時候，我將黑色的、空的葉子節點都省略掉了。
為了讓你更好地理解上面的定義，我畫了兩個紅黑樹的圖例，你可以對照著看下。
為什麼說紅黑樹是“近似平衡”的？
我們前面也講到，平衡二叉查詢樹的初衷，是為了解決二叉查詢樹因為動態更新導致的效能退化問題。所以， “平衡”的意思可以等價為效能不退化。“近似平衡”就等價為效能不會退化的太嚴重。
我們在上一節講過，二叉查詢樹很多操作的效能都跟樹的高度成正比。一棵極其平衡的二叉樹（滿二叉樹或完全二叉樹）的高度大約是 log2n，所以如果要證明紅黑樹是近似平衡的，我們只需要分析，紅黑樹的高度是否比較穩定地趨近 log2n 就好了。
紅黑樹的高度不是很好分析，我帶你一步一步來推導。
首先，我們來看，如果我們將紅色節點從紅黑樹中去掉，那單純包含黑色節點的紅黑樹的高度是多少呢？
紅色節點刪除之後，有些節點就沒有父節點了，它們會直接拿這些節點的祖父節點（父節點的父節點）作為父節點。所以，之前的二叉樹就變成了四叉樹。
前面紅黑樹的定義裡有這麼一條：從任意節點到可達的葉子節點的每個路徑包含相同數目的黑色節點。我們從四叉樹中取出某些節點，放到葉節點位置，四叉樹就變成了完全二叉樹。所以，僅包含黑色節點的四叉樹的高度，比包含相同節點個數的完全二叉樹的高度還要小。
上一節我們說，完全二叉樹的高度近似 log2n，這裡的四叉“黑樹”的高度要低於完全二叉樹，所以去掉紅色節點的“黑樹”的高度也不會超過 log2n。
我們現在知道只包含黑色節點的“黑樹”的高度，那我們現在把紅色節點加回去，高度會變成多少呢？
從上面我畫的紅黑樹的例子和定義看，在紅黑樹中，紅色節點不能相鄰，也就是說，有一個紅色節點就要至少有一個黑色節點，將它跟其他紅色節點隔開。 紅黑樹中包含最多黑色節點的路徑不會超過 log2n，所以加入紅色節點之後，最長路徑不會超過 2log2n，也就是說，紅黑樹的高度近似 2log2n。
所以，紅黑樹的高度只比高度平衡的 AVL 樹的高度（log2n）僅僅大了一倍，在效能上，下降得並不多。這樣推匯出來的結果不夠精確，實際上紅黑樹的效能更好。
解答開篇
我們剛剛提到了很多平衡二叉查詢樹，現在我們就來看下，為什麼在工程中大家都喜歡用紅黑樹這種平衡二叉查詢樹？
我們前面提到 Treap、Splay Tree，絕大部分情況下，它們操作的效率都很高，但是也無法避免極端情況下時間複雜度的退化。儘管這種情況出現的概率不大，但是對於單次操作時間非常敏感的場景來說，它們並不適用。
AVL 樹是一種高度平衡的二叉樹，所以查詢的效率非常高，但是，有利就有弊，AVL 樹為了維持這種高度的平衡，就要付出更多的代價。每次插入、刪除都要做調整，就比較複雜、耗時。所以，對於有頻繁的插入、刪除操作的資料集合，使用 AVL 樹的代價就有點高了。
紅黑樹只是做到了近似平衡，並不是嚴格的平衡，所以在維護平衡的成本上，要比 AVL 樹要低。
所以，紅黑樹的插入、刪除、查詢各種操作效能都比較穩定。對於工程應用來說，要面對各種異常情況，為了支撐這種工業級的應用，我們更傾向於這種效能穩定的平衡二叉查詢樹。
內容小結
很多同學都覺得紅黑樹很難，的確，它算是最難掌握的一種資料結構。其實紅黑樹最難的地方是它的實現，我們今天還沒有涉及，下一節我會專門來講。
不過呢，我認為，我們其實不應該把學習的側重點，放到它的實現上。那你可能要問了，關於紅黑樹，我們究竟需要掌握哪些東西呢？
還記得我多次說過的觀點嗎？我們學習資料結構和演算法，要學習它的由來、特性、適用的場景以及它能解決的問題。對於紅黑樹，也不例外。你如果能搞懂這幾個問題，其實就已經足夠了。
紅黑樹是一種平衡二叉查詢樹。它是為了解決普通二叉查詢樹在資料更新的過程中，複雜度退化的問題而產生的。紅黑樹的高度近似 log2n，所以它是近似平衡，插入、刪除、查詢操作的時間複雜度都是 O(logn)。
因為紅黑樹是一種效能非常穩定的二叉查詢樹，所以，在工程中，但凡是用到動態插入、刪除、查詢資料的場景，都可以用到它。不過，它實現起來比較複雜，如果自己寫程式碼實現，難度會有些高，這個時候，我們其實更傾向用跳錶來替代它。
課後思考
動態資料結構支援動態地資料插入、刪除、查詢操作，除了紅黑樹，我們前面還學習過哪些呢？能對比一下各自的優勢、劣勢，以及應用場景嗎？