|
今天我們來(lái)介紹另一種平衡二叉樹(shù)：紅黑樹(shù)（Red Black Tree），紅黑樹(shù)由Rudolf Bayer于1972年發(fā)明，當(dāng)時(shí)被稱(chēng)為平衡二叉B樹(shù)（symmetric binary B-trees），1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一個(gè)比較摩登的名字：紅黑樹(shù)。 紅黑樹(shù)和之前所講的AVL樹(shù)類(lèi)似，都是在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持二叉查找樹(shù)的平衡，從而獲得較高的查找性能。自從紅黑樹(shù)出來(lái)后，AVL樹(shù)就被放到了博物館里，據(jù)說(shuō)是紅黑樹(shù)有更好的效率，更高的統(tǒng)計(jì)性能。不過(guò)在我了解了紅黑樹(shù)的實(shí)現(xiàn)原理后，并不相信這是真的，關(guān)于這一點(diǎn)我們會(huì)在后面進(jìn)行討論。 紅黑樹(shù)和AVL樹(shù)的區(qū)別在于它使用顏色來(lái)標(biāo)識(shí)結(jié)點(diǎn)的高度，它所追求的是局部平衡而不是AVL樹(shù)中的非常嚴(yán)格的平衡。之前我們?cè)谥v解AVL樹(shù)時(shí)，已經(jīng)領(lǐng)教過(guò)AVL樹(shù)的復(fù)雜，但AVL樹(shù)的復(fù)雜比起紅黑樹(shù)來(lái)說(shuō)簡(jiǎn)直是小巫見(jiàn)大巫。紅黑樹(shù)是真正的變態(tài)級(jí)數(shù)據(jù)結(jié)構(gòu)。 首先來(lái)一個(gè)Silverlight做的紅黑樹(shù)的動(dòng)畫(huà)，它有助于幫你理解什么是紅黑樹(shù)。這里需要注意，必須安裝Silverlight 2.0 RTW 才能正常運(yùn)行游戲，下載地址： http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0
使用注意事項(xiàng)： l 結(jié)點(diǎn)只接收整數(shù)，如果在添加和刪除操作中輸入非法字串，則會(huì)隨機(jī)添加或刪除一個(gè)0~99之間的整數(shù)。 l 可以不在編輯框中輸入數(shù)字，直接單擊添加和刪除按鈕進(jìn)行添加和刪除操作。 l 可以拖動(dòng)拖動(dòng)條控制動(dòng)畫(huà)速度。 紅黑樹(shù)的平衡紅黑樹(shù)首先是一棵二叉查找樹(shù)，它每個(gè)結(jié)點(diǎn)都被標(biāo)上了顏色（紅色或黑色），紅黑樹(shù)滿足以下5個(gè)性質(zhì)： 1、 每個(gè)結(jié)點(diǎn)的顏色只能是紅色或黑色。 2、 根結(jié)點(diǎn)是黑色的。 3、 每個(gè)葉子結(jié)點(diǎn)都帶有兩個(gè)空的黑色結(jié)點(diǎn)（被稱(chēng)為黑哨兵），如果一個(gè)結(jié)點(diǎn)n的只有一個(gè)左孩子，那么n的右孩子是一個(gè)黑哨兵；如果結(jié)點(diǎn)n只有一個(gè)右孩子，那么n的左孩子是一個(gè)黑哨兵。 4、 如果一個(gè)結(jié)點(diǎn)是紅的，則它的兩個(gè)兒子都是黑的。也就是說(shuō)在一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。 5、 對(duì)于每個(gè)結(jié)點(diǎn)來(lái)說(shuō)，從該結(jié)點(diǎn)到其子孫葉結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。 紅黑樹(shù)的這5個(gè)性質(zhì)中，第3點(diǎn)是比較難理解的，但它卻非常有必要。我們看圖1中的左邊這張圖，如果不使用黑哨兵，它完全滿足紅黑樹(shù)性質(zhì)，結(jié)點(diǎn)50到兩個(gè)葉結(jié)點(diǎn)8和葉結(jié)點(diǎn)82路徑上的黑色結(jié)點(diǎn)數(shù)都為2個(gè)。但如果加入黑哨兵后（如圖1右圖中的小黑圓點(diǎn)），葉結(jié)點(diǎn)的個(gè)數(shù)變?yōu)?/span>8個(gè)黑哨兵，根結(jié)點(diǎn)50到這8個(gè)葉結(jié)點(diǎn)路徑上的黑高度就不一樣了，所以它并不是一棵紅黑樹(shù)。
要看真正的紅黑樹(shù)請(qǐng)?jiān)谝陨蟿?dòng)畫(huà)中添加幾個(gè)結(jié)點(diǎn)，看看是否滿足以上性質(zhì)。 紅黑樹(shù)的旋轉(zhuǎn)操作紅黑樹(shù)的旋轉(zhuǎn)操作和AVL樹(shù)一樣，分為LL、RR、LR、RL四種旋轉(zhuǎn)類(lèi)型，差別在于旋轉(zhuǎn)完成后改變的是結(jié)點(diǎn)的顏色，而不是平衡因子。旋轉(zhuǎn)動(dòng)畫(huà)演示請(qǐng)參考AVL這篇文章中的Flash動(dòng)畫(huà)： http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html 紅黑樹(shù)上結(jié)點(diǎn)的插入在討論紅黑樹(shù)的插入操作之前必須要明白，任何一個(gè)即將插入的新結(jié)點(diǎn)的初始顏色都為紅色。這一點(diǎn)很容易理解，因?yàn)椴迦牒邳c(diǎn)會(huì)增加某條路徑上黑結(jié)點(diǎn)的數(shù)目，從而導(dǎo)致整棵樹(shù)黑高度的不平衡。但如果新結(jié)點(diǎn)父結(jié)點(diǎn)為紅色時(shí)（如圖2所示），將會(huì)違返紅黑樹(shù)性質(zhì)：一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。這時(shí)就需要通過(guò)一系列操作來(lái)使紅黑樹(shù)保持平衡。
為了清楚地表示插入操作以下在結(jié)點(diǎn)中使用“新”字表示一個(gè)新插入的結(jié)點(diǎn)；使用“父”字表示新插入點(diǎn)的父結(jié)點(diǎn)；使用“叔”字表示“父”結(jié)點(diǎn)的兄弟結(jié)點(diǎn)；使用“祖”字表示“父”結(jié)點(diǎn)的父結(jié)點(diǎn)。插入操作分為以下幾種情況： 1、黑父 如圖3所示，如果新點(diǎn)的父結(jié)點(diǎn)為黑色結(jié)點(diǎn)，那么插入一個(gè)紅點(diǎn)將不會(huì)影響紅黑樹(shù)的平衡，此時(shí)插入操作完成。紅黑樹(shù)比AVL樹(shù)優(yōu)秀的地方之一在于黑父的情況比較常見(jiàn)，從而使紅黑樹(shù)需要旋轉(zhuǎn)的幾率相對(duì)AVL樹(shù)來(lái)說(shuō)會(huì)少一些。
2．紅父 如果新點(diǎn)的父結(jié)點(diǎn)為紅色，這時(shí)就需要進(jìn)行一系列操作以保證整棵樹(shù)紅黑性質(zhì)。如圖3所示，由于父結(jié)點(diǎn)為紅色，此時(shí)可以判定，祖父結(jié)點(diǎn)必定為黑色。這時(shí)需要根據(jù)叔父結(jié)點(diǎn)的顏色來(lái)決定做什么樣的操作。青色結(jié)點(diǎn)表示顏色未知。由于有可能需要根結(jié)點(diǎn)到新點(diǎn)的路徑上進(jìn)行多次旋轉(zhuǎn)操作，而每次進(jìn)行不平衡判斷的起始點(diǎn)（我們可將其視為新點(diǎn)）都不一樣。所以我們?cè)诖耸褂靡粋€(gè)藍(lán)色箭頭指向這個(gè)起始點(diǎn)，并稱(chēng)之為判定點(diǎn)。
2.1 紅叔 當(dāng)叔父結(jié)點(diǎn)為紅色時(shí)，如圖4所示，無(wú)需進(jìn)行旋轉(zhuǎn)操作，只要將父和叔結(jié)點(diǎn)變?yōu)楹谏?，將祖父結(jié)點(diǎn)變?yōu)榧t色即可。但由于祖父結(jié)點(diǎn)的父結(jié)點(diǎn)有可能為紅色，從而違反紅黑樹(shù)性質(zhì)。此時(shí)必須將祖父結(jié)點(diǎn)作為新的判定點(diǎn)繼續(xù)向上進(jìn)行平衡操作。
需要注意，無(wú)論“父”在“叔”的左邊還是右邊，無(wú)論“新”是“父”的左孩子還是右孩子，它們的操作都完全一樣。
2.2 黑叔 當(dāng)叔父結(jié)點(diǎn)為黑色時(shí)，需要進(jìn)行旋轉(zhuǎn)，以下圖示了所有的旋轉(zhuǎn)可能 情形1：
情形2：
情形3：
情形4：
可以觀察到，當(dāng)旋轉(zhuǎn)完成后，新的旋轉(zhuǎn)根全部為黑色，此時(shí)不需要再向上回溯進(jìn)行平衡操作，插入操作完成。需要注意，上面四張圖的“叔”、“1”、“2”、“3”結(jié)點(diǎn)有可能為黑哨兵結(jié)點(diǎn)。 其實(shí)紅黑樹(shù)的插入操作不是很難，甚至比AVL樹(shù)的插入操作還更簡(jiǎn)單些。但刪除操作就遠(yuǎn)遠(yuǎn)比AVL樹(shù)復(fù)雜得多，下面就介紹紅黑樹(shù)的刪除操作。 紅黑樹(shù)上結(jié)點(diǎn)的刪除紅黑樹(shù)本身是一棵二叉查找樹(shù)，它的刪除和二叉查找樹(shù)的刪除類(lèi)似。首先要找到真正的刪除點(diǎn)，當(dāng)被刪除結(jié)點(diǎn)n存在左右孩子時(shí)，真正的刪除點(diǎn)應(yīng)該是n的中序遍在前驅(qū)，關(guān)于這一點(diǎn)請(qǐng)復(fù)習(xí)二叉查找樹(shù)的刪除。如圖9所示，當(dāng)刪除結(jié)點(diǎn)20時(shí)，實(shí)際被刪除的結(jié)點(diǎn)應(yīng)該為18，結(jié)點(diǎn)20的數(shù)據(jù)變?yōu)?/span>18。
所以可以推斷出，在進(jìn)行刪除操作時(shí)，真正的刪除點(diǎn)必定是只有一個(gè)孩子或沒(méi)有孩子的結(jié)點(diǎn)。而根據(jù)紅黑樹(shù)的性質(zhì)可以得出以下兩個(gè)結(jié)論： 1、 刪除操作中真正被刪除的必定是只有一個(gè)紅色孩子或沒(méi)有孩子的結(jié)點(diǎn)。 2、 如果真正的刪除點(diǎn)是一個(gè)紅色結(jié)點(diǎn)，那么它必定是一個(gè)葉子結(jié)點(diǎn)。 理解這兩點(diǎn)非常重要，如圖10所示，除了情況(a)外，其他任一種況結(jié)點(diǎn)N都無(wú)法滿足紅黑樹(shù)性質(zhì)。
在以下討論中，我們使用藍(lán)色箭頭表示真正的刪除點(diǎn)，它也是旋轉(zhuǎn)操作過(guò)程中的第一個(gè)判定點(diǎn)；真正的刪除點(diǎn)使用“舊”標(biāo)注，舊點(diǎn)所在位置將被它的的孩子結(jié)點(diǎn)所取代（最多只有一個(gè)孩子），我們使用“新”表示舊點(diǎn)的孩子結(jié)點(diǎn)。刪除操作可分為以下幾種情形： 1、舊點(diǎn)為紅色結(jié)點(diǎn) 若舊點(diǎn)為紅色結(jié)點(diǎn)，則它必定是葉子結(jié)點(diǎn)，直接刪除即可。如圖11所示
2、一紅一黑 當(dāng)舊點(diǎn)為黑色結(jié)點(diǎn)，新點(diǎn)為紅色結(jié)點(diǎn)時(shí)，將新點(diǎn)取代舊點(diǎn)位置后，將新點(diǎn)染成紅色即可（如圖12所示）。這里需要注意：舊點(diǎn)為紅色，新點(diǎn)為黑色的情況不可能存在。
3、雙黑 當(dāng)舊點(diǎn)和新點(diǎn)都為黑色時(shí)（新點(diǎn)為空結(jié)點(diǎn)時(shí)，亦屬于這種情況），情況比較復(fù)雜，需要根據(jù)舊點(diǎn)兄弟結(jié)點(diǎn)的顏色來(lái)決定進(jìn)行什么樣的操作。我們使用“兄”來(lái)表示舊點(diǎn)的兄弟結(jié)點(diǎn)。這里可分為紅兄和黑兄兩種情況： 3.1 紅兄 由于兄弟結(jié)點(diǎn)為紅色，所以父結(jié)點(diǎn)必定為黑色，而舊點(diǎn)被刪除后，新點(diǎn)取代了它的位置。下圖演示了兩種可能的情況：
紅兄的情況需要進(jìn)行RR或LL型旋轉(zhuǎn)，然后將父結(jié)點(diǎn)染成紅色，兄結(jié)點(diǎn)染成黑色。然后重新以新點(diǎn)為判定點(diǎn)進(jìn)行平衡操作。我們可以觀察到，旋轉(zhuǎn)操作完成后，判定點(diǎn)沒(méi)有向上回溯，而是降低了一層，此時(shí)變成了黑兄的情況。 3.2 黑兄 黑兄的情況最為復(fù)雜，需要根據(jù)黑兄孩子結(jié)點(diǎn)（這里用“侄”表示）和父親結(jié)點(diǎn)的顏色來(lái)決定做什么樣的操作。 3.2.1 黑兄二黑侄紅父 如圖14所示，這種情況比較簡(jiǎn)單，只需將父結(jié)點(diǎn)變?yōu)楹谏?，兄結(jié)點(diǎn)變?yōu)楹谏?，新結(jié)點(diǎn)變?yōu)楹谏纯?，刪除操作到此結(jié)束。
3.2.2 黑兄二黑侄黑父 如圖15所示，此時(shí)將父結(jié)點(diǎn)染成新結(jié)點(diǎn)的顏色，新結(jié)點(diǎn)染成黑色，兄結(jié)點(diǎn)染成黑色即可。當(dāng)新結(jié)點(diǎn)為紅色時(shí)，父結(jié)點(diǎn)被染成紅色，此時(shí)需要以父結(jié)點(diǎn)為判定點(diǎn)繼續(xù)向上進(jìn)行平衡操作。
3.2.3 黑兄紅侄 黑兄紅侄有以下四種情形，下面分別進(jìn)行圖示： 情形1：
情形2：
情形3：
情形4：
由以上圖例所示，看完以上四張圖的兄弟有可能會(huì)有一個(gè)疑問(wèn)，如果情形1和情形2中的兩個(gè)侄子結(jié)點(diǎn)都為紅色時(shí)，是該進(jìn)行LL旋轉(zhuǎn)還是進(jìn)行LR旋轉(zhuǎn)呢？答案是進(jìn)行LL旋轉(zhuǎn)。情形3和情形4則是優(yōu)先進(jìn)行RR旋轉(zhuǎn)的判定。 紅黑樹(shù)的代碼實(shí)現(xiàn)本以為紅黑樹(shù)的代碼非常容易，因?yàn)?/span>System.Collections.Generic.SortedDictionary類(lèi)就是使用紅黑樹(shù)實(shí)現(xiàn)的，把代碼的算法部分摳出來(lái)就搞定了。但看了SortedDictionary源碼后有些失望，C#中真正實(shí)現(xiàn)紅黑樹(shù)的是TreeSet類(lèi)，SortedDictionary只是在TreeSet的基礎(chǔ)上進(jìn)一步抽象，加上了Key/Value泛型對(duì)。TreeSet使用了一種新的紅黑樹(shù)算法，它在搜索插入點(diǎn)和刪除點(diǎn)時(shí)預(yù)先進(jìn)行旋轉(zhuǎn)和染色操作，從而避免插入和刪除后的回溯。這種算法看上去很美，但仔細(xì)想想，如果插入的是一個(gè)已經(jīng)存在的結(jié)點(diǎn)，刪除的結(jié)點(diǎn)并不存在，那這些預(yù)平衡處理不是白做了嗎？更可怕的是如果在一條路徑上間隔進(jìn)行一次插入和一次刪除，而這些操作沒(méi)有命中目標(biāo)，那么大家就會(huì)看到結(jié)點(diǎn)的顏色變來(lái)變?nèi)ィ@些都是無(wú)用功。來(lái)看看在尋找插入和刪除點(diǎn)的路徑上TreeSet每前進(jìn)一步都要做些什么：給四個(gè)變量賦值；判斷每個(gè)結(jié)點(diǎn)的兩個(gè)孩子結(jié)點(diǎn)的顏色。這種算法在《java數(shù)據(jù)結(jié)構(gòu)和算法》這本書(shū)中有詳細(xì)講述，不過(guò)只講解了插入算法。另外國(guó)內(nèi)也專(zhuān)門(mén)有一篇論文描述這個(gè)算法，他的測(cè)試結(jié)果是這種算法優(yōu)于其他算法，估計(jì)測(cè)試時(shí)沒(méi)有不命中目標(biāo)的情況發(fā)生?？傊也⒉幌嘈胚@是一個(gè)好的算法。 為了證實(shí)我的想法，我不得不自己實(shí)現(xiàn)紅黑樹(shù)，實(shí)現(xiàn)思路跟AVL樹(shù)很類(lèi)似，也是使用一個(gè)數(shù)組保存訪問(wèn)路徑以進(jìn)行回溯，當(dāng)然，考慮到紅黑樹(shù)不嚴(yán)格的平衡，數(shù)組的長(zhǎng)度設(shè)為64，這并不會(huì)給性能帶來(lái)什么影響。過(guò)程很艱辛，需要做大量測(cè)試。很不幸，寫(xiě)完后繼續(xù)做紅黑樹(shù)的Silverlight動(dòng)畫(huà)時(shí)不小心把原來(lái)的代碼給覆蓋掉了，結(jié)點(diǎn)刪除部分的代碼丟失。當(dāng)時(shí)幾乎崩潰，不過(guò)重寫(xiě)并沒(méi)有我想象的那么困難，很快完成，感覺(jué)思路清晰了很多，實(shí)現(xiàn)比原來(lái)也有了改進(jìn)，感謝上帝！ 下面把代碼貼出來(lái)，如果理解了上面所講內(nèi)容是很容易讀懂這些代碼的。
using System;
namespace PaintBST { public class RBTree : IBinaryTree //實(shí)現(xiàn)畫(huà)樹(shù)接口 { //成員變量 private Node _head; //頭指針 private Node[] path = new Node[32]; //記錄訪問(wèn)路徑上的結(jié)點(diǎn) private int p; //表示當(dāng)前訪問(wèn)到的結(jié)點(diǎn)在_path上的索引 INode IBinaryTree.Head //顯式接口實(shí)現(xiàn) { get { return (INode)_head; } } public bool Add(int value) //添加一個(gè)元素 { //如果是空樹(shù)，則新結(jié)點(diǎn)成為二叉排序樹(shù)的根 if (_head == null) { _head = new Node(value); _head.IsRed = false; return true; } p = 0; //parent為上一次訪問(wèn)的結(jié)點(diǎn)，current為當(dāng)前訪問(wèn)結(jié)點(diǎn) Node parent = null, current = _head; while (current != null) { path[p++] = current; //將路徑上的結(jié)點(diǎn)插入數(shù)組 //如果插入值已存在，則插入失敗 if (current.Data == value) { return false; } parent = current; //當(dāng)插入值小于當(dāng)前結(jié)點(diǎn)，則繼續(xù)訪問(wèn)左子樹(shù)，否則訪問(wèn)右子樹(shù) current = (value < parent.Data) ? parent.Left : parent.Right; } current = new Node(value); //創(chuàng)建新結(jié)點(diǎn) current.IsRed = true; if (value < parent.Data) //如果插入值小于雙親結(jié)點(diǎn)的值 { parent.Left = current; //成為左孩子 } else //如果插入值大于雙親結(jié)點(diǎn)的值 { parent.Right = current; //成為右孩子 } if (!parent.IsRed) { return true; } path[p] = current; //回溯并旋轉(zhuǎn) while ((p -= 2) >= 0) //現(xiàn)在p指向插入點(diǎn)的祖父結(jié)點(diǎn) { Node grandParent = path[p]; parent = path[p + 1]; if (!parent.IsRed) { break; } Node uncle = grandParent.Left == parent ? grandParent.Right : grandParent.Left; current = path[p + 2]; if (IsRed(uncle)) //叔父存在并且為紅色的情況 { parent.IsRed = false; uncle.IsRed = false; if (p > 0) //如果祖父不是根結(jié)點(diǎn)，則將其染成紅色 { grandParent.IsRed = true; } } else //叔父不存在或?yàn)楹诘那闆r需要旋轉(zhuǎn) { Node newRoot; if (grandParent.Left == parent) //如果當(dāng)前結(jié)點(diǎn)及父結(jié)點(diǎn)同為左孩子或右孩子 { newRoot = (parent.Left == current) ? LL(grandParent) : LR(grandParent); } else { newRoot = (parent.Right == current) ? RR(grandParent) : RL(grandParent); } grandParent.IsRed = true; //祖父染成紅色 newRoot.IsRed = false; //新根染成黑色 //將新根同曾祖父連接 ReplaceChildOfNodeOrRoot((p > 0) ? path[p - 1] : null, grandParent, newRoot); return true; //旋轉(zhuǎn)后不需要繼續(xù)回溯，添加成功，直接退出 } } return true; } //旋轉(zhuǎn)根旋轉(zhuǎn)后換新根 private void ReplaceChildOfNodeOrRoot(Node parent, Node child, Node newChild) { if (parent != null) { if (parent.Left == child) { parent.Left = newChild; } else { parent.Right = newChild; } } else { _head = newChild; } } private static bool IsBlack(Node node) { return ((node != null) && !node.IsRed); } private static bool IsNullOrBlack(Node node) { if (node != null) { return !node.IsRed; } return true; } private static bool IsRed(Node node) { return ((node != null) && node.IsRed); } //刪除指定值 public bool Remove(int value) { p = -1; //parent表示雙親結(jié)點(diǎn)，node表示當(dāng)前結(jié)點(diǎn) Node node = _head; //尋找指定值所在的結(jié)點(diǎn) while (node != null) { path[++p] = node; //如果找到，則調(diào)用RemoveNode方法刪除結(jié)點(diǎn) if (value == node.Data) { RemoveNode(node);//現(xiàn)在p指向被刪除結(jié)點(diǎn) return true; //返回true表示刪除成功 } if (value < node.Data) { //如果刪除值小于當(dāng)前結(jié)點(diǎn)，則向左子樹(shù)繼續(xù)尋找 node = node.Left; } else { //如果刪除值大于當(dāng)前結(jié)點(diǎn)，則向右子樹(shù)繼續(xù)尋找 node = node.Right; } } return false; //返回false表示刪除失敗 } //刪除指定結(jié)點(diǎn) private void RemoveNode(Node node) { Node tmp = null; //tmp最終指向?qū)嶋H被刪除的結(jié)點(diǎn) //當(dāng)被刪除結(jié)點(diǎn)存在左右子樹(shù)時(shí) if (node.Left != null && node.Right != null) { tmp = node.Left; //獲取左子樹(shù) path[++p] = tmp; while (tmp.Right != null) //獲取node的中序遍歷前驅(qū)結(jié)點(diǎn)，并存放于tmp中 { //找到左子樹(shù)中的最右下結(jié)點(diǎn) tmp = tmp.Right; path[++p] = tmp; } //用中序遍歷前驅(qū)結(jié)點(diǎn)的值代替被刪除結(jié)點(diǎn)的值 node.Data = tmp.Data; } else { tmp = node; } //當(dāng)只有左子樹(shù)或右子樹(shù)或?yàn)槿~子結(jié)點(diǎn)時(shí) //首先找到惟一的孩子結(jié)點(diǎn) Node newTmp = tmp.Left; if (newTmp == null) //如果只有右孩子或沒(méi)孩子 { newTmp = tmp.Right; } if (p > 0) { Node parent = path[p - 1]; if (parent.Left == tmp) { //如果被刪結(jié)點(diǎn)是左孩子 parent.Left = newTmp; } else { //如果被刪結(jié)點(diǎn)是右孩子 parent.Right = newTmp; } if (!tmp.IsRed && IsRed(newTmp)) { newTmp.IsRed = false; return; } } else //當(dāng)刪除的是根結(jié)點(diǎn)時(shí) { _head = newTmp; if (_head != null) { _head.IsRed = false; } return; } path[p] = newTmp; //如果被刪除的是紅色結(jié)點(diǎn)，則它必定是葉子結(jié)點(diǎn)，刪除成功，返回 if (IsRed(tmp)) { return; } //刪除完后進(jìn)行旋轉(zhuǎn)，現(xiàn)在p指向?qū)嶋H被刪除的位置,這個(gè)位置可能為空,tmp指向被刪除的舊點(diǎn)， while (p > 0) { //剩下的是雙黑的情況 //首先找到兄弟結(jié)點(diǎn) Node current = path[p]; Node parent = path[p - 1]; bool currentIsLeft = (parent.Left == current); Node sibling = currentIsLeft ? parent.Right : parent.Left; //紅兄的情況，需要LL旋轉(zhuǎn)或RR旋轉(zhuǎn) if (IsRed(sibling)) { Node newRoot; if (currentIsLeft) { newRoot = RR(parent); } else { newRoot = LL(parent); } ReplaceChildOfNodeOrRoot(p > 1 ? path[p - 2] : null, parent, newRoot); sibling.IsRed = false; parent.IsRed = true; //回溯點(diǎn)降低 path[p - 1] = newRoot; path[p] = parent; path[++p] = current; } else //黑兄的情況 { //黑兄二黑侄 if (IsNullOrBlack(sibling.Left) && IsNullOrBlack(sibling.Right)) { //紅父的情況 if (parent.IsRed) { parent.IsRed = false; sibling.IsRed = true; if (current != null) { current.IsRed = false; } break; //刪除成功 } else //黑父的情況 { parent.IsRed = IsRed(current); if (current != null) { current.IsRed = false; } sibling.IsRed = true; p--; //需要繼續(xù)回溯 } } else //黑兄紅侄 { Node newRoot; if (currentIsLeft) //兄弟在右邊 { if (IsRed(sibling.Right)) //紅侄在右邊 { //RR型旋轉(zhuǎn) newRoot = RR(parent); sibling.Right.IsRed = false; } else { //RL型旋轉(zhuǎn) newRoot = RL(parent); } } else //兄弟在左邊 { if (IsRed(sibling.Left)) { //LL型旋轉(zhuǎn) newRoot = LL(parent); sibling.Left.IsRed = false; } else { //LR型旋轉(zhuǎn) newRoot = LR(parent); } } if (current != null) { current.IsRed = false; } newRoot.IsRed = parent.IsRed; parent.IsRed = false; ReplaceChildOfNodeOrRoot(p > 1 ? path[p - 2] : null, parent, newRoot); break; //不需要回溯，刪除成功 } } } } //root為旋轉(zhuǎn)根，rootPrev為旋轉(zhuǎn)根雙親結(jié)點(diǎn) private Node LL(Node root) //LL型旋轉(zhuǎn)，返回旋轉(zhuǎn)后的新子樹(shù)根 { Node left = root.Left; root.Left = left.Right; left.Right = root; return left; } private Node LR(Node root) //LR型旋轉(zhuǎn)，返回旋轉(zhuǎn)后的新子樹(shù)根 { Node left = root.Left; Node right = left.Right; root.Left = right.Right; right.Right = root; left.Right = right.Left; right.Left = left; return right; } private Node RR(Node root) //RR型旋轉(zhuǎn)，返回旋轉(zhuǎn)后的新子樹(shù)根 { Node right = root.Right; root.Right = right.Left; right.Left = root; return right; } private Node RL(Node root) //RL型旋轉(zhuǎn)，返回旋轉(zhuǎn)后的新子樹(shù)根 { Node right = root.Right; Node left = right.Left; root.Right = left.Left; left.Left = root; right.Left = left.Right; left.Right = right; return left; } } }
完成紅黑樹(shù)后，做了一個(gè)比較粗糙的測(cè)試程序，對(duì)我自己實(shí)現(xiàn)的紅黑樹(shù)RBTree，C#類(lèi)庫(kù)中的紅黑樹(shù)TreeSet和我自己實(shí)現(xiàn)的AVL樹(shù)AVLTree進(jìn)行了簡(jiǎn)單的測(cè)試，為了公平起見(jiàn)，我把TreeSet改成了整型版，這樣大家都站在了同一起跑線上?？紤]到垃圾回收，這樣的測(cè)試并不是很精確、科學(xué)，但也能說(shuō)明一些問(wèn)題。以后我會(huì)專(zhuān)門(mén)寫(xiě)程序?qū)Ω鞣N常見(jiàn)的查找數(shù)據(jù)結(jié)構(gòu)進(jìn)行測(cè)試
后記測(cè)試結(jié)果基本證實(shí)了我的想法，惟一意外的是AVL樹(shù)有兩個(gè)項(xiàng)目輸給了RBTree。在理論上，RBTree在某些方面的確是比AVL樹(shù)更為優(yōu)秀，但從程序員的角度來(lái)說(shuō)，紅黑樹(shù)的實(shí)現(xiàn)需要調(diào)用大量方法，比如結(jié)點(diǎn)顏色的判斷，這會(huì)抵消紅黑樹(shù)的性能優(yōu)勢(shì)。國(guó)外網(wǎng)站也有針對(duì)紅黑樹(shù)和AVL樹(shù)的測(cè)試，結(jié)果基本上是AVL樹(shù)勝出。 紅黑樹(shù)的動(dòng)畫(huà)還有一些bug，整體效果也不盡如人意，我也懶得再改了，寫(xiě)它比寫(xiě)紅黑樹(shù)困難些。寫(xiě)它主要是為了學(xué)習(xí)Silverlight，這也算是第一個(gè)Silverlight動(dòng)畫(huà)作品，東西弄懂了就不想再動(dòng)了。打算將來(lái)更深入地了解Silverlight后再全面修改這個(gè)動(dòng)畫(huà)。 |
|
|
來(lái)自： webgj > 《我的圖書(shū)館》
