引言
之前學習的AVL樹，是一種平衡二叉搜索樹，它追求絕對平衡，從而導致插入和刪除性能較差。而今天學習的紅黑樹，是另一種平衡二叉搜索樹，它追求相對平衡，使得增刪查改的性能都極佳，時間復雜度皆為O(log2N)，是數據結構中的精華，天才般的設想！
一、紅黑樹的概念
紅黑樹，顧名思義，其節(jié)點有紅和黑兩種顏色。
之所以新增結點顏色的標記，是因為通過結點著色方式的限制，能夠讓紅黑樹的最長路徑不超過最短路徑的兩倍，以保證相對平衡。
紅黑樹滿足五條性質：
- 所有結點非黑即紅
- 根結點為黑色
- NIL結點為黑色
- 紅色結點的子結點必為黑色
- 任意結點到其葉子NIL結點的所有路徑，都包含相同的黑色結點
在紅黑樹中，NIL節(jié)點（也稱為空節(jié)點）是葉子節(jié)點的一種特殊表示。它們不是實際存儲數據的節(jié)點，而是樹結構中的占位符，用于定義樹的邊界。所有的紅黑樹都以NIL節(jié)點為葉子節(jié)點，這些NIL節(jié)點在視覺上通常不被畫出來。
性質解讀：
- 性質4：表明不能有連續(xù)的紅色結點
- 性質4+性質5：
- 理論最短路徑：全為黑色結點
- 理論最長路徑：紅黑相間
這樣，就保證了最長路徑不超過最短路徑的兩倍。
二、紅黑樹的模擬實現
2.1 結點
enum Color
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Color _col;
RBTreeNode(const pair<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
細節(jié)：
- 使用三叉鏈，增加了指向parent的指針
- 使用KV模型，數據存儲鍵值對pair
- 結點儲存顏色，同時顏色使用枚舉
- 結點的顏色初始化為紅色
說明：為什么結點的顏色初始化為紅色呢？因為插入新節(jié)點時（不為根部），如果插入黑色，就會直接破壞性質5，導致每條路徑黑結點數目不同；而如果插入紅色，有可能不會破壞性質4，所以結點初始化為紅色更優(yōu)。
2.2 成員變量
template<class K, class V>
class RBTree
{
protected:
typedef RBTreeNode<K, V> Node;
public:
protected:
Node* _root = nullptr;
};
2.3 插入
因為紅黑樹也是二叉搜索樹，所以默認成員函數和遍歷與之前寫的沒什么不同，這里重點講解紅黑樹的插入。
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (grandparent->_right == parent)//uncle在左，parent在右
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)//uncle為紅，變色+向上調整
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else//uncle為空或為黑，變色+旋轉
{
if (parent->_right == cur)//左單旋
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//右左旋
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
}
}
else//parent在左，uncle在右
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
if (parent->_left == cur)//右單旋
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//左右旋
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
}
}
}
_root->_col = BLACK;
return true;
}
思路：
- 以二叉搜索樹的方式正常插入
- 討論并調整結點的顏色，以及調整結構，使之滿足紅黑樹的性質
循環(huán)條件：while (parent && parent->_col == RED)
保證了parent存在且為紅，grandparent存在且為黑
情況一：uncle在左，parent在右
如果uncle存在且為紅色：
處理方法：
- 將parent和uncle變黑，grandparent變紅
- cur = grandparent，parent = cur->_parent，繼續(xù)向上調整
- 防止grandparent為根節(jié)點卻變紅，在循環(huán)結束后將根節(jié)點變?yōu)楹谏?/li>
如果uncle不存在，或者存在且為黑色：
當cur在右部外側時：
處理方法：
- 先對grandparent進行左單旋
- 再將parent變黑，grandparent變紅
當cur在右部內側時：
處理方法：
- 先對parent進行右單旋
- 再對grandparent進行左單旋
- 最后將cur變黑，grandparent變紅
情況二：parent在左，uncle在右
如果uncle存在且為紅色：
處理方法：
- 將parent和uncle變黑，grandparent變紅
- cur = grandparent，parent = cur->_parent，繼續(xù)向上調整
- 防止grandparent為根節(jié)點卻變紅，在循環(huán)結束后將根節(jié)點變?yōu)楹谏?/li>
如果uncle不存在，或者存在且為黑色：
當cur在左部外側時：
處理方法：
- 先對grandparent進行右單旋
- 再將parent變黑，grandparent變紅
當cur在左部內側時：
處理方法：
- 先對parent進行左單旋
- 再對grandparent進行右單旋
- 最后將cur變黑，grandparent變紅
紅黑樹插入的核心口訣：uncle存在且為紅，變色+向上調整，uncle不存在或為黑，變色+旋轉
附上旋轉的實現：
void RotateL(Node* parent)
{
Node* grandparent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (grandparent)
{
if (grandparent->_right == parent)
{
grandparent->_right = subR;
}
else
{
grandparent->_left = subR;
}
}
else
{
_root = subR;
}
subR->_parent = grandparent;
}
void RotateR(Node* parent)
{
Node* grandparent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (grandparent)
{
if (grandparent->_right == parent)
{
grandparent->_right = subL;
}
else
{
grandparent->_left = subL;
}
}
else
{
_root = subL;
}
subL->_parent = grandparent;
}
三、紅黑樹的驗證
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根結點為紅色" << endl;
return false;
}
int benchMark = 0;//基準值
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++benchMark;
}
cur = cur->_right;
}
return Check(_root, 0, benchMark);
}
bool Check(Node* root, int blackNum, int benchMark)
{
if (root == nullptr)
{
if (blackNum != benchMark)
{
cout << "某條路徑黑色結點數量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << "存在連續(xù)的紅色結點" << endl;
return false;
}
return Check(root->_left, blackNum, benchMark)
&& Check(root->_right, blackNum, benchMark);
}
細節(jié)：
- 驗證根節(jié)點是否為黑
- 先計算出一條路徑的黑色結點個數作為基準值，再在遞歸中比較每條路徑的黑色結點是否相等
- 若該節(jié)點為紅，檢測其parent是否為紅，判斷是否存在連續(xù)的紅色節(jié)點
四、紅黑樹的性能
4.1 優(yōu)勢
紅黑樹是高效的平衡二叉樹，增刪改查的時間復雜度都是O( l o g 2 N log_2 N log2?N)，紅黑樹不追求絕對平衡，其只需保證最長路徑不超過最短路徑的2倍，相對AVL樹而言，降低了插入和旋轉的次數。
4.2 適用場景
因此，在經常進行增刪的結構中性能比AVL樹更優(yōu)，而且紅黑樹實現比較簡單，所以實際運用中紅黑樹更多。文章來源：http://www.zghlxwxcb.cn/news/detail-845466.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-845466.html
到了這里，關于【C++練級之路】【Lv.16】紅黑樹（冰與火的碰撞，紅與黑的史詩）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
