建議先看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
本章內(nèi)容頗多，所以我分三篇來寫，這一篇是關(guān)于一些基本的概念和選擇，后面兩篇分別是插入和刪除。
上一章總結(jié)過BST(http://www.wutianqi.com/?p=2430)，BST在高度較小時，可以獲得很好的性能(因為BST的操作的平均時間為O(lgn))，但是在高度較大時，則性能就一般。而紅黑樹“近似平衡”，于是降低了平均時間，再者，紅黑樹并不追求“完全平衡”——它只要求部分地達(dá)到平衡要求，降低了對旋轉(zhuǎn)的要求，從而提高了性能。
談到紅黑樹的用途，最廣為人知的應(yīng)該就是紅黑樹在C++ STL中的應(yīng)用了，在set, multiset, map, multimap等中，都應(yīng)用了紅黑樹(具體大家可以去網(wǎng)上搜搜)。
下面給出紅黑樹和黑高度的定義：
滿足下面幾個條件(紅黑性質(zhì))的二叉搜索樹，稱為紅黑樹：
1. 每個結(jié)點或是紅色，或是是黑色。
2. 根結(jié)點是黑的。
3. 所有的葉結(jié)點(NULL)是黑色的。（NULL被視為一個哨兵結(jié)點，所有應(yīng)該指向NULL的指針，都看成指向了NULL結(jié)點。）
4. 如果一個結(jié)點是紅色的，則它的兩個兒子節(jié)點都是黑色的。
5. 對每個結(jié)點，從該結(jié)點到其子孫結(jié)點的所有路徑上包含相同數(shù)目的黑結(jié)點。
黑高度的定義：
從某個結(jié)點出發(fā)(不包括該結(jié)點)到達(dá)一個葉結(jié)點的任意一條路徑上，黑色結(jié)點的個數(shù)成為該結(jié)點x的黑高度。
下面就是一個紅黑樹：
紅黑樹是二叉搜索樹的一種。它與普通二叉搜索樹不同的是，紅黑樹的每個節(jié)點都附加了另一個屬性――顏色，可以是紅色，也可以是黑色。通過對于每條路徑上節(jié)點顏色的規(guī)則進(jìn)行限定，紅黑樹可以保證任何兩條從根部到樹葉的路徑節(jié)點個數(shù)相差不超過2倍。所以，紅黑樹是一種近似平衡的二叉搜索樹。
紅黑樹的查找、最大值、最小值、前趨、后繼等操作，與普通的二叉搜索樹沒有什么區(qū)別。插入和刪除操作需要重新實現(xiàn)。僅僅用普通的二叉搜索樹的插入和刪除動作，可能會破壞紅黑樹本身的一些性質(zhì)，因此，需要進(jìn)行額外的處理。這些額外的處理主要是改變樹節(jié)點的顏色，或是改變樹的結(jié)構(gòu)。
關(guān)于旋轉(zhuǎn)：
我把13-2手動畫了一次并添加了一些注釋：
旋轉(zhuǎn)其實比較簡單，就不多說了，以下是代碼：
void LeftRotate(RBTree &T, Node *x)
{
Node *y = x->rchild;
x->rchild = y->lchild;
if(y->lchild != NULL)
y->lchild->parent = x;
y->parent = x->parent;
if(x->parent == NULL)
T = y;
else
{
if(x == x->parent->lchild)
x->parent->lchild = y;
else
x->parent->rchild = y;
}
y->lchild = x;
x->parent = y;
}
void RightRotate(RBTree &T, Node *x)
{
Node *y = x->rchild;
x->rchild = y->lchild;
if(y->lchild != NULL)
y->lchild->parent = x;
y->parent = x->parent;
if(x->parent == NULL)
T = y;
else
{
if(x == x->parent->lchild)
x->parent->lchild = y;
else
x->parent->rchild = y;
}
y->lchild = x;
x->parent = y;
}
下一篇是關(guān)于插入。
在我獨立博客上的原文：http://www.wutianqi.com/?p=2438
歡迎大家互相學(xué)習(xí)，互相討論！
posted on 2011-05-07 09:13
Tanky Woo 閱讀(1684)
評論(3) 編輯 收藏 引用