數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)領(lǐng)域本科教育教學(xué)改革試點(diǎn)工作計(jì)劃（“101計(jì)劃”）研究成果10112.4紅黑樹第12章

高級查找12.4.1紅黑樹的定義12.4.2紅黑樹的旋轉(zhuǎn)12.4.3紅黑樹的插入12.4.4紅黑樹的刪除12.4.5紅黑樹的應(yīng)用12.4.6紅黑樹的小結(jié)12.4.7紅黑樹的作業(yè)12.4.1紅黑樹的定義12.4.1紅黑樹的定義數(shù)據(jù)結(jié)構(gòu)紅黑樹是滿足下列性質(zhì)的二叉查找樹：每個(gè)結(jié)點(diǎn)或者為黑色，或者為紅色根結(jié)點(diǎn)為黑色每個(gè)空結(jié)點(diǎn)（NULL結(jié)點(diǎn)）都是黑色如果有一個(gè)結(jié)點(diǎn)是紅色，那么他的2個(gè)孩子結(jié)點(diǎn)都是黑色（不能有2個(gè)相鄰的紅色結(jié)點(diǎn)）對于每一個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫的葉子結(jié)點(diǎn)的路徑中所包含的黑色結(jié)點(diǎn)數(shù)量必須相等。從紅黑樹任意結(jié)點(diǎn)x出發(fā)，到達(dá)葉子結(jié)點(diǎn)的任意路徑上（不包含x)的黑色結(jié)點(diǎn)個(gè)數(shù)稱為x結(jié)點(diǎn)的黑高度，記為bh(x)，規(guī)定葉子結(jié)點(diǎn)高度為1，黑高度為1。紅黑樹的黑高度定義為根結(jié)點(diǎn)的黑高度。12.4.1紅黑樹的定義12.4.1紅黑樹的定義數(shù)據(jù)結(jié)構(gòu)著色性質(zhì)二叉查找樹中每個(gè)結(jié)點(diǎn)著色為紅黑兩色中的一種顏色；根結(jié)點(diǎn)為黑色；任一紅結(jié)點(diǎn)的孩子只能為黑色。

黑高度相等性質(zhì)每個(gè)結(jié)點(diǎn)x到其所有子孫葉結(jié)點(diǎn)的路徑中所包含的黑結(jié)點(diǎn)個(gè)數(shù)（不包含結(jié)點(diǎn)x）必須相等，并稱該個(gè)數(shù)為結(jié)點(diǎn)x的黑高度，記為bh(x)，規(guī)定空結(jié)點(diǎn)的黑高度為0，則葉子結(jié)點(diǎn)的黑高度是1，根結(jié)點(diǎn)的黑高度為紅黑樹的黑高度。紅黑樹是一顆自平衡二叉查找樹，在插入刪除操作時(shí)通過特定操作保持二叉樹的平衡，從而獲得較高的查找性能。最壞O(logn)時(shí)間內(nèi)完成查找，插入和刪除。寫出該紅黑樹的每個(gè)結(jié)點(diǎn)的黑高度作答主觀題10分12.4.1紅黑樹的定義12.4.1紅黑樹的定義數(shù)據(jù)結(jié)構(gòu)1121111122寫出該紅黑樹的每個(gè)結(jié)點(diǎn)的黑高度解答：圖1紅黑樹左旋圖2紅黑樹右旋12.4.2紅黑樹的旋轉(zhuǎn)12.4.2紅黑樹的旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)1.旋轉(zhuǎn)不會(huì)影響旋轉(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，父結(jié)點(diǎn)以上結(jié)點(diǎn)結(jié)構(gòu)保持不變2.旋轉(zhuǎn)不考慮顏色！2.旋轉(zhuǎn)是局部的，目的是當(dāng)一邊子樹的結(jié)點(diǎn)少了，那么向另外一邊子樹“借入”一些結(jié)點(diǎn)；當(dāng)一邊子樹的結(jié)點(diǎn)多了，那么向另外一邊子樹“出租”一些結(jié)點(diǎn)。12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)提問：紅黑樹進(jìn)行插入操作，第一步是滿足二叉查找樹的性質(zhì)，插入之后，怎么判斷是否需要進(jìn)行旋轉(zhuǎn)？如何通過更改顏色（著色）使其仍然滿足紅黑樹的定義？以這棵樹為例子，分別插入4，14，92，5，77,插入后的紅黑樹是怎樣的？12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)提問：紅黑樹插入操作的時(shí)候，插入位置已經(jīng)找到，把插入結(jié)點(diǎn)放到正確的位置就可以啦，請問插入結(jié)點(diǎn)是應(yīng)該是什么顏色呢？為什么？答案：插入紅色結(jié)點(diǎn)。因?yàn)榧t色在父結(jié)點(diǎn)（如果存在）為黑色結(jié)點(diǎn)時(shí)，紅黑樹的黑色平衡沒被破壞，不需要做自平衡操作。但如果插入結(jié)點(diǎn)是黑色，那么插入位置所在的子樹黑色結(jié)點(diǎn)總是多1，必須做自平衡。注意：插入位置始終是葉子結(jié)點(diǎn)（查找失敗的位置）12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)提問：請觀察紅黑樹的紅結(jié)點(diǎn)多還是黑結(jié)點(diǎn)多？最壞情況是怎樣的？因此插入紅結(jié)點(diǎn)除了因?yàn)楦附Y(jié)點(diǎn)是黑色不用調(diào)整，還有什么優(yōu)點(diǎn)？答案：通常黑結(jié)點(diǎn)多。最壞情況是根結(jié)點(diǎn)黑色，然后每一個(gè)結(jié)點(diǎn)的一個(gè)分支全部是黑結(jié)點(diǎn)，一個(gè)分支是一層紅結(jié)點(diǎn)，一層黑結(jié)點(diǎn)，使得黑高度相同，但高度差1倍。因?yàn)榇蟛糠智闆r下黑結(jié)點(diǎn)多，插入紅結(jié)點(diǎn)不用調(diào)整，使得插入操作比AVL樹減少大量旋轉(zhuǎn)，功能更優(yōu)。12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)提問：紅黑樹的插入有幾種情況？如何處理？12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)提問：紅黑樹的插入有幾種情況？如何處理？12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)Insert(tree,key,value)輸入：紅黑樹tree，鍵key，值value輸出：無ifIsEmpty(tree)then//紅黑樹為空tree.root←RBNode(key,value,BLACK)returnendt←key在tree中的目標(biāo)插入位置p←key在tree中的目標(biāo)插入位置的父結(jié)點(diǎn)ift≠NILthen//key已存在t.value←valueelse//key不存在t←RBNode(key,value,RED,p)ift.p.color=REDthen//插入結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色I(xiàn)nsertAdjust(t)endend紅黑樹的插入偽代碼12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)InsertAdjust(tree,x)輸入：紅黑樹tree，結(jié)點(diǎn)x。結(jié)點(diǎn)x屬于tree輸出：無whilex.p≠NILandx.p.color=REDdoifx.p=x.p.p.leftthen//父結(jié)點(diǎn)為祖父結(jié)點(diǎn)的左孩子y←x.p.p.right//y表示叔叔結(jié)點(diǎn)ify≠NILandy.color=REDthen//case4.1叔叔是紅結(jié)點(diǎn)x.p.color←BLACKy.color←BLACKx.p.p.color←REDx←x.p.p

else//叔叔是黑結(jié)點(diǎn)ifx=x.p.rightthen

//case4.2.2插入結(jié)點(diǎn)是父結(jié)點(diǎn)的右孩子LRx←x.pLRotate(tree,x)end//case4.2.1插入結(jié)點(diǎn)是父結(jié)點(diǎn)的左孩子LLx.p.color←BLACKx.p.p.color←REDRRotate(tree,x.p.p)end12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)else//父結(jié)點(diǎn)為祖父結(jié)點(diǎn)的右孩子，與前面的左孩子情況鏡像對稱y←x.p.p.left//y表示叔叔結(jié)點(diǎn)ify≠NILandy.color=REDthen//case4.1叔叔是紅結(jié)點(diǎn)x.p.color←BLACKy.color←BLACKx.p.p.color←REDx←x.p.pelseifx=x.p.leftthen//case4.3.2插入結(jié)點(diǎn)是父結(jié)點(diǎn)的左孩子x←x.pRRotate(tree,x)end//叔叔是黑結(jié)點(diǎn)//case4.3.1插入結(jié)點(diǎn)是父結(jié)點(diǎn)的右孩子x.p.color←BLACKx.p.p.color←REDLRotate(tree,x.p.p)endendendtree.root.color←BLACK12.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)例題：從無到有建立一顆紅黑樹，關(guān)鍵字分別是12,7,24,66,52,18,2012.4.3紅黑樹的插入12.4.3紅黑樹的插入數(shù)據(jù)結(jié)構(gòu)例題：從無到有建立一顆紅黑樹，關(guān)鍵字分別是12,7,24,66,52,18,2012.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)研討：請分析討論紅黑樹的各種刪除情況，課后給出刪除算法描述并編程測試。1空樹2待刪除結(jié)點(diǎn)不在樹中3待刪除結(jié)點(diǎn)不在樹中紅黑樹是刪除分析12.4.4紅黑樹的刪除1葉結(jié)點(diǎn)2單分支結(jié)點(diǎn)3雙分支結(jié)點(diǎn)待刪除結(jié)點(diǎn)在樹中分析紅葉結(jié)點(diǎn)：直接刪除；父結(jié)點(diǎn)指針空黑葉結(jié)點(diǎn)：父結(jié)點(diǎn)孩子指針空，繼任結(jié)點(diǎn)比兄弟黑高度少1，繼續(xù)調(diào)整紅結(jié)點(diǎn)：父結(jié)點(diǎn)指向孩子。黑結(jié)點(diǎn)：父結(jié)點(diǎn)指向孩子，孩子調(diào)整為黑色。左分支最大值或者右分支最小值替換該結(jié)點(diǎn)，轉(zhuǎn)到左分支/右分支刪除單分支或者葉結(jié)點(diǎn)12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)while當(dāng)前結(jié)點(diǎn)不是紅色and不是根：

針對刪除黑結(jié)點(diǎn)，造成父結(jié)點(diǎn)的左右黑高度不平衡，進(jìn)行調(diào)整假設(shè)結(jié)點(diǎn)X是實(shí)際刪除黑結(jié)點(diǎn)之后的后繼結(jié)點(diǎn)或者刪除后向根調(diào)整的路徑上造成父結(jié)點(diǎn)的左右黑高度不平衡的結(jié)點(diǎn),下面我們分析可能出現(xiàn)的情況及調(diào)整策略12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)X的兄弟是紅色，父結(jié)點(diǎn)不可能是紅色（雙紅）：因此父結(jié)點(diǎn)是黑色：兄弟置黑色，父結(jié)點(diǎn)置紅色，父結(jié)點(diǎn)左旋，兄弟的左孩子成為父結(jié)點(diǎn)的右孩子；然后以雙黑X繼續(xù)調(diào)整刪除黑結(jié)點(diǎn)的調(diào)整策略12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)刪除黑結(jié)點(diǎn)的調(diào)整策略刪除黑葉結(jié)點(diǎn)20：雙黑是空結(jié)點(diǎn)，兄弟是紅色。處理：父親紅色，兄弟黑色，父親左旋例：刪除2012.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)刪除黑結(jié)點(diǎn)的調(diào)整策略例：刪除20雙黑空結(jié)點(diǎn)繼續(xù)處理：兄弟黑色，兄弟的兩個(gè)孩子都是黑色，兄弟置紅色，雙親作為X繼續(xù)調(diào)整12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)刪除黑結(jié)點(diǎn)的調(diào)整策略例：刪除2035是紅色，結(jié)束循環(huán)，設(shè)置為黑色12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)刪除黑結(jié)點(diǎn)的調(diào)整策略雙黑的兄弟是黑色，且兄弟的2個(gè)孩子都是黑色：無論雙親的顏色，方法都是：兄弟置紅色，以父結(jié)點(diǎn)B作為當(dāng)前結(jié)點(diǎn)，繼續(xù)向根方向調(diào)整(1)紅結(jié)點(diǎn)B結(jié)束循環(huán)(2)黑結(jié)點(diǎn)B繼續(xù)調(diào)整12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)刪除黑結(jié)點(diǎn)的調(diào)整策略例：刪除512.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)刪除黑結(jié)點(diǎn)的調(diào)整策略例：刪除5刪除5：12的左黑葉結(jié)點(diǎn)5被刪除后，雙黑X是空結(jié)點(diǎn)，兄弟是黑色的，兄弟孩子都是黑色。處理策略：兄弟結(jié)點(diǎn)15置紅，父結(jié)點(diǎn)12繼續(xù)調(diào)整；持續(xù)這個(gè)過程直到根結(jié)點(diǎn)12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)刪除黑結(jié)點(diǎn)的調(diào)整策略雙黑的兄弟是黑色，且兄弟至少有1個(gè)孩子是紅色：(1)兄弟的左孩子是紅色，兄弟的右孩子是黑色調(diào)整策略：兄弟紅，兄弟左孩子黑，兄弟右旋，變成雙黑的黑兄弟是右紅孩子情況繼續(xù)處理12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)刪除黑結(jié)點(diǎn)的調(diào)整策略雙黑的兄弟是黑色，且兄弟至少有1個(gè)孩子是紅色：(1)

兄弟的左孩子是紅色，兄弟的右孩子是黑色（2）兄弟的右孩子是紅色調(diào)整策略：雙親左旋，兄弟右孩子調(diào)整和雙親同色第二種情況是否和完善？(1)C的左孩子是黑色：如第一種和第二種情況，僅父結(jié)點(diǎn)B左旋；兄弟右孩子和雙親顏色一致。(2)C的左孩子是紅色（兄弟2個(gè)孩子都是紅色）：如第三種和第四種情況，兄弟結(jié)點(diǎn)置為父結(jié)點(diǎn)的顏色，父結(jié)點(diǎn)置為黑色，兄弟結(jié)點(diǎn)的右孩子置為黑色，父結(jié)點(diǎn)左旋。(1)C的左孩子是黑色：如第一種和第二種情況，僅父結(jié)點(diǎn)B左旋；兄弟右孩子和雙親顏色一致。(2)C的左孩子是紅色（兄弟2個(gè)孩子都是紅色）：如第三種和第四種情況，兄弟結(jié)點(diǎn)置為父結(jié)點(diǎn)的顏色，父結(jié)點(diǎn)置為黑色，兄弟結(jié)點(diǎn)的右孩子置為黑色，父結(jié)點(diǎn)左旋。12.4.4紅黑樹的刪除總結(jié)12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)針對黑結(jié)點(diǎn)刪除造成的黑高度不平衡需要將多余黑色去除掉，調(diào)整策略是通過旋轉(zhuǎn)將額外的黑色上移，直到下面情況之一發(fā)生，則停止調(diào)整：1）當(dāng)前調(diào)整的結(jié)點(diǎn)X為紅結(jié)點(diǎn)，將其著為黑色即可；2）當(dāng)前結(jié)點(diǎn)X為根。在調(diào)整過程中，需保持紅黑樹的性質(zhì)，特別是黑高性質(zhì)，結(jié)點(diǎn)X為父結(jié)點(diǎn)的左孩子調(diào)整情況分類如下（X為右孩子的情況是鏡像對稱的）：1）結(jié)點(diǎn)X的兄弟結(jié)點(diǎn)為紅色：兄弟結(jié)點(diǎn)置黑色，父結(jié)點(diǎn)置紅色，父結(jié)點(diǎn)左旋，雙黑X繼續(xù)調(diào)整；2）結(jié)點(diǎn)X的兄弟結(jié)點(diǎn)為黑色，兄弟結(jié)點(diǎn)的左、右孩子均為黑色：兄弟結(jié)點(diǎn)置紅色，父結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)X，進(jìn)入下一次調(diào)整循環(huán)；3）結(jié)點(diǎn)X的兄弟結(jié)點(diǎn)為黑色，兄弟結(jié)點(diǎn)的左孩子為紅色，右孩子為黑色：兄弟結(jié)點(diǎn)置紅色，兄弟結(jié)點(diǎn)左孩子置黑色，兄弟結(jié)點(diǎn)右旋，繼續(xù)處理；4）結(jié)點(diǎn)X的兄弟結(jié)點(diǎn)為黑色，兄弟結(jié)點(diǎn)的左孩子是黑色，右孩子為紅色：兄弟結(jié)點(diǎn)置為父結(jié)點(diǎn)的顏色，父結(jié)點(diǎn)置為黑色，兄弟結(jié)點(diǎn)的右孩子置為黑色，父結(jié)點(diǎn)左旋。12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)例：在下圖的紅黑樹中依次刪除20和52（要求用右子樹的最小值替換有2個(gè)孩子的結(jié)點(diǎn)），畫出刪除后的紅黑樹。12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)例：在下圖的紅黑樹中依次刪除20和52（要求用右子樹的最小值替換有2個(gè)孩子的結(jié)點(diǎn)），畫出刪除后的紅黑樹。12.4.4紅黑樹的刪除12.4.4紅黑樹的刪除數(shù)據(jù)結(jié)構(gòu)例：在下圖的紅黑樹中依次刪除20和52（要求用右子樹的最小值替換有2個(gè)孩子的結(jié)點(diǎn)），畫出刪除后的紅黑樹。12.4.5紅黑樹的應(yīng)用12.4.5紅黑樹的應(yīng)用數(shù)據(jù)結(jié)構(gòu)紅黑樹增加一些數(shù)據(jù)結(jié)構(gòu)，可以實(shí)現(xiàn)更多的功能。比如區(qū)間樹就是一種增強(qiáng)的紅黑樹，適合區(qū)間操作。區(qū)間樹是紅黑樹的關(guān)鍵字是區(qū)間的最小值，增加的成員是區(qū)間最大值。Linux內(nèi)核的虛擬內(nèi)存管理，用紅黑樹而不是雙向鏈表，可以使得查找一個(gè)虛擬內(nèi)存的速度由O(n)提升到O(logn)，且插入新的虛擬內(nèi)存僅需定位到新區(qū)域的前面，再做二叉查找樹的插入和紅黑樹的調(diào)整，不用掃描整個(gè)鏈表空間。C++S