前言
??上文我們在遇到問題：二叉搜索樹退化到單支導(dǎo)致效率和性能降低時，利用了AVL樹解決。但是由于AVL樹是一棵絕對平衡的樹，每次修改樹結(jié)構(gòu)都要保證左右子樹高度差的絕對值不超過1，這可能會引發(fā)多次旋轉(zhuǎn)。因此，若我們要設(shè)計出一棵結(jié)構(gòu)動態(tài)變化的二叉搜索樹，利用AVL樹的效率并不高?；谶@個原因，紅黑樹誕生了。
1. 紅黑樹的概念
???
紅黑樹（RBTree）是一種二叉搜索樹，在每個節(jié)點設(shè)置一個存儲域用于指明該節(jié)點的顏色（Red或Black），進(jìn)而，通過限制任一條從根到葉子節(jié)點的路徑上的各個節(jié)點的著色方式，使得任一條路徑的長度都不超過另一條路徑，最終達(dá)到接近平衡的樹結(jié)構(gòu)。
??紅黑樹結(jié)構(gòu)示意圖：
其中，NIL為空節(jié)點
2. 紅黑樹的性質(zhì)
每一棵紅黑樹，都滿足以下五條性質(zhì)：
- 每個節(jié)點不是黑色就是紅色
- 根節(jié)點為黑
- 對于每個節(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點
- 不允許有相鄰的兩個紅色節(jié)點
- 每個葉節(jié)點都為黑（此處的葉節(jié)點指
NIL節(jié)點）
??這五條性質(zhì)，保證了紅黑樹最長路徑長度不超過最短路徑長度的二倍。
- 為何要引進(jìn) NIL 節(jié)點？
保證任意節(jié)點都有兩個分叉，這樣才能使得紅黑樹接近平衡。不這樣做的話，若直接以平時的葉子節(jié)點作葉節(jié)點，極端情況下，下面這棵樹同樣滿足紅黑樹的性質(zhì)，但是其已經(jīng)退化成鏈表了，查找效率為O(N)。
- 如何保證最長路徑長度不超過最短路徑的二倍?
如圖所示，我們以8為根節(jié)點的紅黑樹為例（只關(guān)注左右兩條路徑，假設(shè)左路徑是最短路徑，右路徑是最長路徑，圖中三角形是一些能保證整棵樹為紅黑樹的不同情況的子樹）
由性質(zhì)3可得，最短路徑中的黑節(jié)點必須與最長路徑中的黑節(jié)點數(shù)量相同，又由性質(zhì)4，最終可得最短路徑節(jié)點全為黑，且與最長路徑中黑節(jié)點數(shù)量相同。而最長路徑中，在與最短路徑擁有相同數(shù)量黑節(jié)點的前提下，穿插了紅色節(jié)點，使之長度最長的方法是每個黑節(jié)點都帶一個紅節(jié)點。這樣一來，最長路徑的長度就是最短路徑的二倍，此時最長路徑最后一個節(jié)點為紅，插入紅色節(jié)點違反性質(zhì)4，插入黑色節(jié)點違反性質(zhì)3，因此最長路徑長度不超過最短路徑長度的二倍。如圖中，左邊路徑長度為3（最短），右邊路徑長度為6（最長）。
3. 紅黑樹的定義
// 枚舉：紅和黑
enum COLOR
{
RED,
BLACK,
};
// RBTree的節(jié)點
template <class V>
struct RBTreeNode
{
typedef RBTreeNode<V> Self;
V _v; // 數(shù)據(jù)域
Self* _left;
Self* _right;
Self* _parent;
COLOR _col; // 顏色域
RBTreeNode(const V& v)
:_v(v)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};
// RBTree的大致結(jié)構(gòu)
template <class V>
class RBTree
{
typedef RBTreeNode<V> node;
public:
RBTree()
:_root(nullptr)
{}
private:
node* _root;
};
4. 紅黑樹的插入操作
??紅黑樹的插入，是其區(qū)別于AVL樹的最大亮點，紅黑樹的插入減少了一些旋轉(zhuǎn)，使用
變色+旋轉(zhuǎn)的調(diào)整方式，提高了插入效率。
??紅黑樹的插入操作可分為兩步 ：
- 按照二叉搜索樹的規(guī)則，插入新節(jié)點
? 插入新節(jié)點默認(rèn)為紅。如果默認(rèn)為黑，則必定違反性質(zhì)3，需要做的調(diào)整更多。而默認(rèn)為紅，有可能會違反性質(zhì)4，需要做出調(diào)整，也可能不違反任何性質(zhì)，無需調(diào)整。因而選擇第二種方案，減少插入時的調(diào)整次數(shù)，提高效率。
template <class V>
class RBTree
{
typedef RBTreeNode<V> node;
public:
//...
bool insert(const V& v)
{
if (_root == nullptr)
{
_root = new node(v);
_root->_col = BLACK;
return true;
}
//插入
node* cur = _root;
node* parent = nullptr;
while (cur)
{
if (v < cur->_v)
{
parent = cur;
cur = cur->_left;
}
else if (v > cur->_v)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new node(v);
if (cur->_v < parent->_v)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
// ...
}
private
node* _root;
};
- 檢查插入后是否破壞了紅黑樹結(jié)構(gòu)，若是則需進(jìn)行調(diào)整
??因為新節(jié)點的默認(rèn)顏色是紅色，所以：
- 如果其雙親節(jié)點的顏色是黑色，沒有違反紅黑樹任何性質(zhì)，則不需要調(diào)整；
- 如果新插入節(jié)點的雙親節(jié)點顏色為紅色時，就違反了性質(zhì)3
不允許有相鄰的兩個紅色節(jié)點，此時需要對紅黑樹分情況來討論，不同情況有不同調(diào)整方法：
約定:
需要調(diào)整時，cur為紅，p為紅，g為黑（否則調(diào)整前p、g就已經(jīng)破壞了紅黑樹的規(guī)則）。因此我們重點看uncle節(jié)點的情況，uncle節(jié)點的存在與否、著色狀態(tài)決定了該如何調(diào)整。
1??情況1：uncle節(jié)點存在且為紅
?注意，此時看到的樹可能是某棵子樹，也有可能是整棵樹。
- ??調(diào)整方法：p，u變黑，g變紅。這樣做不僅解決了相鄰兩個紅節(jié)點的問題，還使得以g為根到任意葉子節(jié)點的每條路徑的黑節(jié)點數(shù)量不變。但是要注意g還需繼續(xù)向上調(diào)整。
為什么g還需要向上繼續(xù)調(diào)整？
- 當(dāng)這棵樹是某棵子樹時，g一定還有雙親節(jié)點，若g的雙親節(jié)點為紅色，則需要繼續(xù)向上調(diào)整。
- 當(dāng)這棵樹是整顆樹時，g是根節(jié)點，則需要修改g的顏色為黑，否則會破壞性質(zhì)2（根節(jié)點為黑）。
- ??綜上所述，cur可以是新插入節(jié)點，也可以是由a、b子樹插入節(jié)點調(diào)整（情況1）后變成紅色。 若cur為新插入的節(jié)點，易得a、b為空樹。此時c、d、e皆為空樹，否則插入前的樹并不是紅黑樹。若cur是調(diào)整后得來的紅節(jié)點，則各個子樹又有不同情況?？偠灾?，插入新節(jié)點前該樹必須滿足紅黑樹的性質(zhì)。
- 因為情況1并不涉及旋轉(zhuǎn)，不會調(diào)整樹的物理結(jié)構(gòu)，所以調(diào)整方法與cur的插入位置無關(guān)，只要滿足條件即可。下面四種情況均屬于情況1的調(diào)整。
2??情況2：uncle節(jié)點不存在/存在且為黑
-
uncle不存在。cur只能是新插入節(jié)點的情況（不能是由子樹調(diào)整而來變紅）。abcde子樹均不存在，否則插入之前不滿足紅黑樹的性質(zhì)。
-
uncle存在且為黑。cur只能是由子樹調(diào)整而來變紅 （即情況1變化而來） 的情況（不能是新插入節(jié)點），否則調(diào)整前不滿足紅黑樹的性質(zhì)。
?假設(shè)cur為新插入節(jié)點，則插入前樹結(jié)構(gòu)如圖所示（暫且不考慮NIL節(jié)點），違反性質(zhì)3。
(1)(2)的調(diào)整方法都是一樣的。不同于情況1，情況二無法單憑節(jié)點的變色完成調(diào)整，而是要借助旋轉(zhuǎn)＋變色。旋轉(zhuǎn)方式與AVL樹的旋轉(zhuǎn)大同小異。
-
左左——右單旋
-
右右——左單旋
-
左右——左右雙旋
-
右左——右左雙旋
??代碼實現(xiàn)
template <class V>
class RBTree
{
typedef RBTreeNode<V> node;
public:
//...
bool insert(const V& v)
{
if (_root == nullptr)
{
_root = new node(v);
_root->_col = BLACK;
return true;
}
//插入
node* cur = _root;
node* parent = nullptr;
while (cur)
{
if (v < cur->_v)
{
parent = cur;
cur = cur->_left;
}
else if (v > cur->_v)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new node(v);
if (cur->_v < parent->_v)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
// 調(diào)整
node* grandfather = nullptr, *uncle = nullptr;
while (parent && parent->_col == RED) // parent存在且為紅色時需繼續(xù)向上調(diào)整
{
grandfather = parent->_parent;
if (parent == grandfather->_left)
{
uncle = grandfather->_right;
}
else
{
uncle = grandfather->_left;
}
//情況1：u存在且為紅
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 繼續(xù)向上更新
cur = grandfather;
parent = cur->_parent;
}
//情況2：u不存在/u存在且為黑
else
{
if (cur == parent->_left && parent == grandfather->_left)
{
// 左左——右單旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else if (cur == parent->_right && parent == grandfather->_right)
{
// 右右——左單旋
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else if (cur == parent->_right && parent == grandfather->_left)
{
// 左右——左右雙旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
else if (cur == parent->_left && parent == grandfather->_right)
{
// 右左——右左雙旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
// 經(jīng)過情況2調(diào)整后，子樹根節(jié)點必為黑，因此直接結(jié)束更新
break;
}
}
// 最后寫定根節(jié)點為黑色
_root->_col = BLACK;
return true;
}
private:
// 右單旋
void RotateR(node* pParent)
{
node* subL = pParent->_left;
node* subLR = subL->_right;
node* ppParent = pParent->_parent;
//1.pParent(父)和subLR(子)
pParent->_left = subLR;
if (subLR)
subLR->_parent = pParent;
//2.subL(父)和pParent(子)
subL->_right = pParent;
pParent->_parent = subL;
//3.ppParent(父)和subL(子)
if (pParent == _root)
{
_root = subL;
}
else
{
if (ppParent->_left == pParent)
{
ppParent->_left = subL;
}
else
{
ppParent->_right = subL;
}
}
subL->_parent = ppParent;
}
// 左單旋
void RotateL(node* pParent)
{
node* subR = pParent->_right;
node* subRL = subR->_left;
node* ppParent = pParent->_parent;
pParent->_right = subRL;
if (subRL)
subRL->_parent = pParent;
subR->_left = pParent;
pParent->_parent = subR;
if (pParent == _root)
{
_root = subR;
}
else
{
if (ppParent->_left == pParent)
{
ppParent->_left = subR;
}
else
{
ppParent->_right = subR;
}
}
subR->_parent = ppParent;
}
node* _root;
};
5. 紅黑樹的驗證
??驗證一棵樹是否為紅黑樹，不能像AVL樹一樣簡單粗暴地判斷左右子樹高度差的絕對值是否小于1，因為紅黑樹只是接近平衡。紅黑樹的驗證需要驗證其五條性質(zhì)是否都成立。
?紅黑樹的性質(zhì)
- 每個節(jié)點不是黑色就是紅色
- 根節(jié)點為黑
- 對于每個節(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點
- 不允許有相鄰的兩個紅色節(jié)點
- 每個葉節(jié)點都為黑（此處的葉節(jié)點指
NIL節(jié)點）
性質(zhì)1和性質(zhì)5無需驗證，通過代碼就已經(jīng)保證了。我們需要驗證性質(zhì)2、3、4。
??思路：
- 驗證性質(zhì)2：直接判斷即可
- 驗證性質(zhì)3：先選取任一路徑（一般旋轉(zhuǎn)最左或最右路徑），計算其黑節(jié)點數(shù)量，作為參考值，然后再用每一條路徑的黑節(jié)點數(shù)量與參考值比較，只要有一條路徑上的黑節(jié)點數(shù)量與參考值不相等，則不滿足紅黑樹旋轉(zhuǎn)3。
- 驗證性質(zhì)4：判斷當(dāng)前節(jié)點與其parent節(jié)點是否同時為紅即可。（parent節(jié)點必存在，孩子節(jié)點不一定存在且情況多，所以選取parent與當(dāng)前節(jié)點比較）。
??代碼實現(xiàn)
class RBTree
{
typedef RBTreeNode<V> node;
public:
//...
bool IsRBTree()
{
if (_root == nullptr)
{
return true;
}
// 判斷性質(zhì)2
if (_root->_col == RED)
{
cout << "違反性質(zhì)2：根節(jié)點為黑" << endl;
return false;
}
// 求任意一條路徑上的黑色節(jié)點數(shù)量，讓其他路徑上的與之對比
// 選取最左路徑
node* left = _root;
int ref = 0;
while (left)
{
if (left->_col == BLACK)
{
ref++;
}
left = left->_left;
}
// NIL節(jié)點也是黑色
ref++;
// 檢查左右子樹，需要傳入路徑到達(dá)當(dāng)前節(jié)點的黑節(jié)點的數(shù)量
return check(_root->_left, 1, ref) && check(_root->_right, 1, ref);
}
private:
bool check(node* cur, int prevBlackCount, const int& refBlackCount)
{
if (cur == nullptr)
{
// 當(dāng)前路徑到達(dá)終點
// 黑色節(jié)點個數(shù)與參照值比較
// 加上NIL節(jié)點
prevBlackCount++;
if (prevBlackCount != refBlackCount)
{
cout << "違反性質(zhì)3：每條路徑的黑節(jié)點數(shù)量應(yīng)相同" << endl;
return false;
}
else
{
return true;
}
}
// 判斷性質(zhì)4
if (cur->_col == RED && cur->_parent->_col == RED)
{
cout << "違反性質(zhì)4：不允許有相鄰的兩個紅節(jié)點" << endl;
return false;
}
// 計算路徑到達(dá)當(dāng)前節(jié)點的黑節(jié)點的數(shù)量
int curBlackCount = cur->_col == BLACK ? prevBlackCount + 1 : prevBlackCount;
return check(cur->_left, curBlackCount, refBlackCount)
&& check(cur->_right, curBlackCount, refBlackCount);
}
node* _root;
};
?? 測試函數(shù)
void testRBTree()
{
RBTree<int> rbt;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
rbt.insert(a[i]);
}
if (rbt.IsRBTree())
{
cout << "The tree is a RBTree!!!" << endl;
}
}
?? 簡易的遞歸圖
6. 紅黑樹和AVL樹的比較
??紅黑樹和AVL樹都是常見的自平衡二叉搜索樹，它們都能夠保證樹的高度不會過高，從而保證了樹的查詢、插入和刪除操作的時間復(fù)雜度都是O(logN)。但是它們之間有一些不同點。
上面提到，紅黑樹是近似平衡，而AVL樹是絕對平衡，因此，紅黑樹的查找效率低于AVL樹。那么這對使用紅黑樹的影響大嗎？那么需要探討一下近似平衡的概念。
-
近似平衡
紅黑樹通過對從根到葉子節(jié)點的任一條路徑上各個節(jié)點的著色方式的限制，以達(dá)到近似平衡的效果，即最長路徑長度不超過最短路徑的二倍。近似平衡，通俗理解，在效率方面，越接近平衡越優(yōu)，越不平衡越差，若要得到其查找的時間復(fù)雜度，就要分近似平衡的最優(yōu)情況和最差情況討論。
-
最優(yōu)情況：每條路徑都是全黑，或者每條路徑都是一紅一黑相間。此時的紅黑樹是滿二叉樹，即最平衡的情況，查找的時間復(fù)雜度為
O(logN)
-
最差情況：每個節(jié)點的往左右的兩條路徑，一條全黑，一條一紅一黑相間，此時左右兩條路徑有一條是另一條的兩倍，這種情況下為最差情況。抽象示意圖如下：
?分析：
設(shè)全黑路徑長度（即最短路徑長度）：h
-
極端情況下，當(dāng)N黑很大時，N紅相對于N黑很小，可忽略不計
N = N黑 + N紅故
N = N黑 -
此時只考慮黑色節(jié)點，可以想象成將紅色節(jié)點都往最底部挪，那么上層是一個由黑色節(jié)點組成的滿二叉樹
故：
N黑 = N = 2^h-1h = logN
因為：全黑路徑長度 = 最短路徑長度 = h
所以：最長路徑長度 = 2×最短路徑長度 = 2h = 2logN
??紅黑樹最差情況的查找，就是去找最長路徑的最后一個節(jié)點，綜上推論，大概要找
2logN次。而在AVL樹中，由于絕對平衡的結(jié)構(gòu)，查找一個節(jié)點只需找logN次。
-
給一個很大的數(shù)，比方說10億。那么，在一棵10億節(jié)點的AVL樹中，查找的最壞情況是找30次（log10億）。而在一棵10億節(jié)點的紅黑樹中，查找的最壞情況是找60次（2*log10億）?？梢姡?strong>紅黑樹的查找效率略低于AVL樹，但是二者是同一個量級的，對于計算機(jī)來說，這點差別不算什么。所以這點效率區(qū)別對紅黑樹的使用影響并不大。
-
對于樹的插入和刪除。AVL樹在插入或刪除節(jié)點時，可能會需要更多地通過旋轉(zhuǎn)操作來保持樹的平衡，而旋轉(zhuǎn)操作可能會導(dǎo)致更多的旋轉(zhuǎn)，從而導(dǎo)致插入和刪除操作的時間復(fù)雜度可能會比紅黑樹更高。而紅黑樹通過著色和旋轉(zhuǎn)操作來保持平衡，旋轉(zhuǎn)次數(shù)比AVL樹少。因此紅黑樹插入和刪除操作的效率可能會更高。
??得出結(jié)論：如果需要頻繁進(jìn)行插入和刪除操作，且對查詢效率要求不是特別高，可以選擇紅黑樹；如果對查詢效率有比較高的要求，且能夠容忍插入和刪除操作的效率稍低，可以選擇AVL樹。實際應(yīng)用中，紅黑樹用的更多。
7. 紅黑樹的應(yīng)用
- C++ STL庫 – map/set、mutil_map/mutil_set
- Java 庫
- linux內(nèi)核
- 其他一些庫
??下一篇文章將帶你了解map和set，并分析如何用紅黑樹實現(xiàn)它們。文章來源：http://www.zghlxwxcb.cn/news/detail-429016.html
完。文章來源地址http://www.zghlxwxcb.cn/news/detail-429016.html
到了這里，關(guān)于二叉搜索樹：紅黑樹的原理和實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
