兩紅夾一黑

紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

性質(zhì)1. 節(jié)點是紅色或黑色。

性質(zhì)2. 根節(jié)點是黑色。

性質(zhì)3 每個葉節(jié)點(NIL節(jié)點，空節(jié)點)是黑色的。

性質(zhì)4 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)

性質(zhì)5. 從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。

這些約束強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。

要知道為什么這些特性確保了這個結(jié)果，注意到性質(zhì)4導(dǎo)致了路徑不能有兩個毗連的紅色節(jié)點就足夠了。最短的可能路徑都是黑色節(jié)點，最長的可能路徑有交替的紅色和黑色節(jié)點。因為根據(jù)性質(zhì)5所有最長的路徑都有相同數(shù)目的黑色節(jié)點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。

在很多樹數(shù)據(jù)結(jié)構(gòu)的表示中，一個節(jié)點有可能只有一個子節(jié)點，而葉子節(jié)點不包含數(shù)據(jù)。用這種范例表示紅黑樹是可能的，但是這會改變一些屬性并使算法復(fù)雜。為此，本文中我們使用 "nil 葉子" 或"空(null)葉子"，如上圖所示，它不包含數(shù)據(jù)而只充當(dāng)樹在此結(jié)束的指示。這些節(jié)點在繪圖中經(jīng)常被省略，導(dǎo)致了這些樹好象同上述原則相矛盾，而實際上不是這樣。與此有關(guān)的結(jié)論是所有節(jié)點都有兩個子節(jié)點，盡管其中的一個或兩個可能是空葉子。

紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔(dān)保。這不只是使它們在時間敏感的應(yīng)用如即時應(yīng)用(real time application)中有價值，而且使它們有在提供最壞情況擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中作為建造板塊的價值;例如，在計算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)都可以基于紅黑樹。

紅黑樹在函數(shù)式編程中也特別有用，在這里它們是最常用的持久數(shù)據(jù)結(jié)構(gòu)之一，它們用來構(gòu)造關(guān)聯(lián)數(shù)組和集合，在突變之后它們能保持為以前的版本。除了O(log n)的時間之外，紅黑樹的持久版本對每次插入或刪除需要O(log n)的空間。

紅黑樹是 2-3-4樹的一種等同。換句話說，對于每個 2-3-4 樹，都存在至少一個數(shù)據(jù)元素是同樣次序的紅黑樹。在 2-3-4 樹上的插入和刪除操作也等同于在紅黑樹中顏色翻轉(zhuǎn)和旋轉(zhuǎn)。這使得 2-3-4 樹成為理解紅黑樹背后的邏輯的重要工具，這也是很多介紹算法的教科書在紅黑樹之前介紹 2-3-4 樹的原因，盡管 2-3-4 樹在實踐中不經(jīng)常使用。

在紅黑樹上只讀操作不需要對用于二叉查找樹的操作做出修改，因為它也是二叉查找樹。但是，在插入和刪除之后，紅黑屬性可能變得違規(guī)。恢復(fù)紅黑屬性需要少量(O(log n))的顏色變更(這在實踐中是非?？焖俚?并且不超過三次樹旋轉(zhuǎn)(對于插入是兩次)。這允許插入和刪除保持為 O(log n) 次，但是它導(dǎo)致了非常復(fù)雜的操作。