數據構造之紅黑樹詳解。本站提示廣大學習愛好者：（數據構造之紅黑樹詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是數據構造之紅黑樹詳解正文
1.簡介
紅黑樹是一種自均衡二叉查找樹。它的統計機能要好過均衡二叉樹（AVL樹），是以，紅黑樹在許多處所都有運用。在C++ STL中，許多部門(今朝包含set, multiset, map, multimap)運用了紅黑樹的變體(SGI STL中的紅黑樹有一些變更，這些修正供給了更好的機能，和對set操作的支撐)。它是龐雜的，但它的操作有著優越的最壞情形運轉時光，而且在理論中是高效的: 它可以在O(log n)時光內做查找，拔出和刪除等操作。
本文引見了紅黑樹的根本性質和根本操作。
2.紅黑樹的性質
紅黑樹，望文生義，經由過程紅黑兩種色彩域包管樹的高度近似均衡。它的每一個節點是一個五元組：color（色彩），key（數據），left（左孩子），right（右孩子）和p（父節點）。
紅黑樹的界說也是它的性質，有以下五條：
性質1. 節點是白色或黑色
性質2. 根是黑色
性質3. 一切葉子都是黑色（葉子是NIL節點）
性質4. 假如一個節點是紅的，則它的兩個兒子都是黑的
性質5. 從任一節點到其葉子的一切簡略途徑都包括雷同數量的黑色節點。
這五特性質強迫了紅黑樹的症結性質: 從根到葉子的最長的能夠途徑不多於最短的能夠途徑的兩倍長。為何呢？性質4暗示著任何一個簡略途徑上不克不及有兩個連接的白色節點，如許，最短的能夠途徑滿是黑色節點，最長的能夠途徑有瓜代的白色和黑色節點。同時依據性質5曉得：一切最長的途徑都有雷同數量的黑色節點，這就注解了沒有途徑能多於任何其他途徑的兩倍長。
3.紅黑樹的根本操作
由於紅黑樹也是二叉查找樹，是以紅黑樹上的查找操作與通俗二叉查找樹上的查找操作雷同。但是，紅黑樹上的拔出操作和刪除操作會招致不再相符紅黑樹的性質。恢復紅黑樹的性質須要大批(O(log n))的色彩變革(現實長短常疾速的)和不跨越三次樹扭轉(關於拔出操作是兩次)。固然拔出和刪除很龐雜，但操作時光仍可以堅持為 O(log n) 次。
3.1拔出操作
拔出操作可以歸納綜合為以下幾個步調：
(1)查找要拔出的地位，時光龐雜度為：O(N)
(2)將新節點的color賦為白色
(3)自下而上從新調劑該樹為紅黑樹
個中，第(1)步的查找辦法跟通俗二叉查找樹一樣，第(2)步之所以將新拔出的節點的色彩賦為白色，是由於：假如設為黑色，就會招致根到葉子的途徑上有一條路上，多一個額定的黑節點，這個是很難調劑的。然則設為白色節點後，能夠會招致湧現兩個持續白色節點的抵觸，那末可以經由過程色彩更換（color flips）和樹扭轉來調劑，如許簡略多了。上面評論辯論步調(3)的一些細節：
設要拔出的節點為N，其父節點為P，其父親G的兄弟節點為U（即P和U是統一個節點的兩個子節點）。
[1] 假如P是黑色的，則整棵樹不用調劑就是紅黑樹。
[2] 假如P是白色的（可知，其父節點G必定是黑色的），則拔出z後，違反了性質4，須要停止調劑。調劑時分以下3種情形：
（a）N的叔叔U是白色的
如上圖所示，我們將P和U重繪為黑色偏重繪節點G為白色(用來堅持性質5)。如今新節點N有了一個黑色的父節點P，由於經由過程父節點P或叔父節點U的任何途徑都一定經由過程祖父節點G，在這些途徑上的黑節點數量沒有轉變。然則，白色的祖父節點G的父節點也有能夠是白色的，這就違背了性質4。為懂得決這個成績，我們在祖父節點G上遞歸調劑色彩。
（b）N的叔叔U是黑色的，且N是右孩子
如上圖所示，我們對P停止一次左扭轉更換新節點和其父節點的腳色; 接著，按情況(c)處置之前的父節點P以處理依然掉效的性質4。
（c）N的叔叔U是黑色的，且N是左孩子
如上圖所示，對祖父節點G 的一次右扭轉; 在扭轉發生的樹中，之前的父節點P如今是新節點N和之前的祖父節點G 的父節點， 然後交流之前的父節點P和祖父節點G的色彩，成果的樹知足性質4，同時性質5[4]也依然堅持知足。
3.2刪除操作
刪除操作可以歸納綜合為以下幾個步調：
(1)查找要刪除地位，時光龐雜度為：O(N)
(2)用刪除節點後繼或許節點調換該節點（只停止數據調換便可，不用調劑指針，後繼節點是中序遍歷中緊挨著該節點的節點，即：右孩子的最左孩子節點）
(3)假如刪除節點的調換節點為黑色，則需從新調劑該樹為紅黑樹
個中，第(1)步的查找辦法跟通俗二叉查找樹一樣，第(2)步之所以用後繼節點調換刪除節點，是由於如許可以包管該後繼節點之上還是一個紅黑樹，爾後繼節點能夠是一個葉節點或許只要右子樹的節點，如許只需用有節點調換後繼節點便可到達刪除的目標。假如須要刪除的節點有兩個兒子，那末成績可以被轉化成刪除另外一個只要一個兒子的節點的成績。（沒看懂？？？可參考：http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91 ）在第(3)步中，假如，假如刪除節點為白色節點，則他的父親和孩子全為黑節點，如許直接刪除該節點便可，不用停止任何調劑。假如刪除節點是黑節點，分四種情形：
設要刪除的節點為N，其父節點為P，其兄弟節點為S。
因為N是黑色的，則P能夠是黑色的，也能夠是白色的，S也能夠是黑色的或許白色的
（1）S是白色的
此時P確定是白色的。我們對N的父節點停止左扭轉，然後把白色兄弟轉換成N的祖父。我們接著對換 N 的父親和祖父的色彩。雖然一切的途徑依然有雷同數量的黑色節點，如今 N 有了一個黑色的兄弟和一個白色的父親，所以我們可以接下去按 (2)、(3)或(4)情形來處置。
（2）S和S的孩子滿是黑色的
在這類情形下，P能夠是黑色的或許白色的，我們簡略的重繪S 為白色。成果是經由過程S的一切途徑，它們就是之前欠亨過 N 的那些途徑，都少了一個黑色節點。由於刪除 N 的初始的父親使經由過程 N 的一切途徑少了一個黑色節點，這使工作都均衡了起來。然則，經由過程 P 的一切途徑如今比欠亨過 P 的途徑少了一個黑色節點。接上去，要調劑以P作為N遞歸調劑樹。
（3）S是黑色的，S的左孩子是白色，右孩子是黑色
這類情形下我們在 S 上做右扭轉，如許 S 的左兒子成為 S 的父親和 N 的新兄弟。我們接著交流 S 和它的新父親的色彩。一切途徑仍有異樣數量的黑色節點，然則如今 N 有了一個右兒子是白色的黑色兄弟，所以我們進入了情形（4）。N 和它的父親都不受這個變換的影響。
（4）S是黑色的，S的右孩子是白色
在這類情形下我們在 N 的父親上做左扭轉，如許 S 成為 N 的父親和 S 的右兒子的父親。我們接著交流 N 的父親和 S 的色彩，並使 S 的右兒子為黑色。子樹在它的根上的還是異樣的色彩，所以屬性 3 沒有被違背。然則，N 如今增長了一個黑色先人: 要末 N 的父親釀成黑色，要末它是黑色而 S 被增長為一個黑色祖父。所以，經由過程 N 的途徑都增長了一個黑色節點。
4.參考材料
(1)《算法導論》，第二版
(2) http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
