紅黑樹(shù)是一種自平衡二叉查找樹(shù)，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由Rudolf Bayer發(fā)明的，他稱之為"對(duì)稱二叉B樹(shù)"，它現(xiàn)代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。它是復(fù)雜的，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中是高效的: 它可以在O(log n)時(shí)間內(nèi)做查找，插入和刪除，這里的n 是樹(shù)中元素的數(shù)目。
紅黑樹(shù)是一種很有意思的平衡檢索樹(shù)。它的統(tǒng)計(jì)性能要好于平衡二叉樹(shù)(有些書籍根據(jù)作者姓名，Adelson-Velskii和Landis，將其稱為 AVL-樹(shù))，因此，紅黑樹(shù)在很多地方都有應(yīng)用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應(yīng)用了紅黑樹(shù)的變體(SGI STL中的紅黑樹(shù)有一些變化，這些修改提供了更好的性能，以及對(duì)set操作的支持)。
背景和術(shù)語(yǔ)
紅黑樹(shù)是一種特定類型的二叉樹(shù)，它是在計(jì)算機(jī)科學(xué)中用來(lái)組織數(shù)據(jù)比如數(shù)字的塊的一種結(jié)構(gòu)。所有數(shù)據(jù)塊都存儲(chǔ)在節(jié)點(diǎn)中。這些節(jié)點(diǎn)中的某一個(gè)節(jié)點(diǎn)總是擔(dān)當(dāng)啟始位置的功能，它不是任何節(jié)點(diǎn)的兒子；我們稱之為根節(jié)點(diǎn)或根。它有最多兩個(gè)"兒子"，都是它連接到的其他節(jié)點(diǎn)。所有這些兒子都可以有自己的兒子，以此類推。這樣根節(jié)點(diǎn)就有了把它連接到在樹(shù)中任何其他節(jié)點(diǎn)的路徑。
如果一個(gè)節(jié)點(diǎn)沒(méi)有兒子，我們稱之為葉子節(jié)點(diǎn)，因?yàn)樵谥庇X(jué)上它是在樹(shù)的邊緣上。子樹(shù)是從特定節(jié)點(diǎn)可以延伸到的樹(shù)的某一部分，其自身被當(dāng)作一個(gè)樹(shù)。在紅黑樹(shù)中，葉子被假定為 null 或空。
由于紅黑樹(shù)也是二叉查找樹(shù)，它們當(dāng)中每一個(gè)節(jié)點(diǎn)都的比較值都必須大于或等于在它的左子樹(shù)中的所有節(jié)點(diǎn)，并且小于或等于在它的右子樹(shù)中的所有節(jié)點(diǎn)。這確保紅黑樹(shù)運(yùn)作時(shí)能夠快速的在樹(shù)中查找給定的值。
用途和好處
紅黑樹(shù)和AVL樹(shù)一樣都對(duì)插入時(shí)間、刪除時(shí)間和查找時(shí)間提供了最好可能的最壞情況擔(dān)保。這不只是使它們?cè)跁r(shí)間敏感的應(yīng)用如即時(shí)應(yīng)用(real time application)中有價(jià)值，而且使它們有在提供最壞情況擔(dān)保的其他數(shù)據(jù)結(jié)構(gòu)中作為建造板塊的價(jià)值；例如，在計(jì)算幾何中使用的很多數(shù)據(jù)結(jié)構(gòu)都可以基于紅黑樹(shù)。
紅黑樹(shù)在函數(shù)式編程中也特別有用，在這里它們是最常用的持久數(shù)據(jù)結(jié)構(gòu)之一，它們用來(lái)構(gòu)造關(guān)聯(lián)數(shù)組和集合，在突變之后它們能保持為以前的版本。除了O(log n)的時(shí)間之外，紅黑樹(shù)的持久版本對(duì)每次插入或刪除需要O(log n)的空間。
紅黑樹(shù)是 2-3-4樹(shù)的一種等同。換句話說(shuō)，對(duì)于每個(gè) 2-3-4 樹(shù)，都存在至少一個(gè)數(shù)據(jù)元素是同樣次序的紅黑樹(shù)。在 2-3-4 樹(shù)上的插入和刪除操作也等同于在紅黑樹(shù)中顏色翻轉(zhuǎn)和旋轉(zhuǎn)。這使得 2-3-4 樹(shù)成為理解紅黑樹(shù)背后的邏輯的重要工具，這也是很多介紹算法的教科書在紅黑樹(shù)之前介紹 2-3-4 樹(shù)的原因，盡管 2-3-4 樹(shù)在實(shí)踐中不經(jīng)常使用。
屬性
紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都有顏色特性的二叉查找樹(shù)，顏色的值是紅色或黑色之一。除了二叉查找樹(shù)帶有的一般要求，我們對(duì)任何有效的紅黑樹(shù)加以如下增補(bǔ)要求:
1.節(jié)點(diǎn)是紅色或黑色。
2.根是黑色。
3.所有葉子（外部節(jié)點(diǎn)）都是黑色。
4.每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
5.從每個(gè)葉子到根的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
這些約束強(qiáng)制了紅黑樹(shù)的關(guān)鍵屬性: 從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)。結(jié)果是這個(gè)樹(shù)大致上是平衡的。因?yàn)椴僮鞅热绮迦?、刪除和查找某個(gè)值都要求與樹(shù)的高度成比例的最壞情況時(shí)間，這個(gè)在高度上的理論上限允許紅黑樹(shù)在最壞情況下都是高效的，而不同于普通的二叉查找樹(shù)。
要知道為什么這些特性確保了這個(gè)結(jié)果，注意到屬性4導(dǎo)致了路徑不能有兩個(gè)毗連的紅色節(jié)點(diǎn)就足夠了。最短的可能路徑都是黑色節(jié)點(diǎn)，最長(zhǎng)的可能路徑有交替的紅色和黑色節(jié)點(diǎn)。因?yàn)楦鶕?jù)屬性5所有最長(zhǎng)的路徑都有相同數(shù)目的黑色節(jié)點(diǎn)，這就表明了沒(méi)有路徑能多于任何其他路徑的兩倍長(zhǎng)。
在很多樹(shù)數(shù)據(jù)結(jié)構(gòu)的表示中，一個(gè)節(jié)點(diǎn)有可能只有一個(gè)兒子，而葉子節(jié)點(diǎn)包含數(shù)據(jù)。用這種范例表示紅黑樹(shù)是可能的，但是這會(huì)改變一些屬性并使算法復(fù)雜。為此，本文中我們使用 "nil 葉子" 或"空(null)葉子"，如上圖所示，它不包含數(shù)據(jù)而只充當(dāng)樹(shù)在此結(jié)束的指示。這些節(jié)點(diǎn)在繪圖中經(jīng)常被省略，導(dǎo)致了這些樹(shù)好像同上述原則相矛盾，而實(shí)際上不是這樣。與此有關(guān)的結(jié)論是所有節(jié)點(diǎn)都有兩個(gè)兒子，盡管其中的一個(gè)或兩個(gè)可能是空葉子。
操作
在紅黑樹(shù)上只讀操作不需要對(duì)用于二叉查找樹(shù)的操作做出修改，因?yàn)樗捕娌檎覙?shù)。但是，在插入和刪除之后，紅黑屬性可能變得違規(guī)。恢復(fù)紅黑屬性需要少量(O(log n))的顏色變更(這在實(shí)踐中是非?？焖俚?并且不超過(guò)三次樹(shù)旋轉(zhuǎn)(對(duì)于插入是兩次)。這允許插入和刪除保持為 O(log n) 次，但是它導(dǎo)致了非常復(fù)雜的操作。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
重慶分公司
重慶分公司
