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