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