C++ STL容器詳解之紅黑樹部分模擬實現
一、紅黑樹的概念
紅黑樹（Red Black Tree），是在計算機科學中用到的一種數據結構，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。
二、紅黑樹的性質
1. 每個結點不是紅色就是黑色；
2. 根節點是黑色的；
3. 如果一個節點是紅色的，則它的兩個孩子結點是黑色的；
4. 對於每個結點，從該結點到其所有後代葉結點的簡單路徑上，均 包含相同數目的黑色結點；
5. 每個葉子結點都是黑色的(此處的葉子結點指的是空結點)；
滿足上面的性質，紅黑樹就能保證其最長路徑中節點個數不會超過最短路徑節點個數的兩倍。
三、紅黑樹節點的定義
enum Colour //紅黑樹顏色枚舉
{
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;
Colour _col;
RBTreeNode(const pair<K, V>& kv) //構造函數
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
插入時默認為紅色節點，因為紅色可能會破壞規則3，黑色一定會破壞規則4，所以默認紅色。
四、紅黑樹結構
為瞭後續實現關聯式容器簡單，紅黑樹的實現中增加一個頭結點，因為跟節點必須為黑色，為瞭與根節點進行區分，將頭結點給成黑色，並且讓頭結點的 parent 域指向紅黑樹的根節點，left域指向紅黑樹中最小的節點，right域指向紅黑樹中最大的節點，如下:
五、 紅黑樹的插入操作
紅黑樹是在二叉搜索樹的基礎上加上其平衡限制條件，因此紅黑樹的插入可分為兩步：
1. 按照二叉搜索的樹規則插入新節點：
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return make_pair(_root, true);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
Node* newNode = new Node(kv);
newNode->_col = RED;
if (parent->_kv.first > kv.first)
{
parent->_left = newNode;
newNode->_parent = parent;
}
else
{
parent->_right = newNode;
newNode->_parent = parent;
}
cur = newNode;
while (parent && parent->_col == RED) //違反規則三
{
}
_root->_col = BLACK; //插入結束再次將根變為黑
return make_pair(cur, true);
}
2. 檢測新節點插入後，紅黑樹的性質是否造到破壞
因為新節點的默認顏色是紅色，因此：如果其雙親節點的顏色是黑色，沒有違反紅黑樹任何性質，則不需要調整；但當新插入節點的雙親節點顏色為紅色時，就違反瞭性質三不能有連在一起的紅色節點，此時需要對紅黑樹分情況來討論：
cur為當前節點，p為父節點，g為祖父節點，u為叔叔節點
情況一：cur為紅，p為紅，g為黑，u存在且為紅
如果g是根節點，調整完成後，需要將g改為黑色，如果g是子樹，g一定有父節點，且如果為紅色呃，繼續向上調整。
將p,u改為黑，g改為紅，然後把g當成cur，繼續向上調整 。
情況二: cur為紅，p為紅，g為黑，u不存在/u為黑
u的情況有兩種：
1.如果u節點不存在，則cur一定是新插入節點，因為如果cur不是新插入節點，則cur和p一定有一個節點的顏色是黑色，就不滿足性質4：每條路徑黑色節點個數相同。
2.如果u節點存在，則其一定是黑色的，那麼cur節點原來的顏色一定是黑色的，現在看到其是紅色的原因是因為cur的子樹在調整的過程中將cur節點的顏色由黑色改成紅色。
p為g的左孩子，cur為p的左孩子，則進行右單旋轉；
p為g的右孩子，cur為p的右孩子，則進行左單旋轉。
p變黑，g變紅。
情況三: cur為紅，p為紅，g為黑，u不存在/u為黑
需要進行雙旋。
代碼實現：
while (parent && parent->_col == RED) //違反規則三
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) //左半邊
{
Node* uncle = parent->_right;
if (uncle && uncle->_col == red) //情況一
{
uncle->_col = BLACK;
grandfather->_col = RED;
parent->_col = BLACK;
cur = grandfather; //迭代
parent = cur->_parent;
}
else //情況2.3
{
if (cur == parent->_left) //單側
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break; //黑色數量無變化，不需要向上
}
}
else // parent == grandfather->_right
{
Node* uncle = parent->_left;
if (uncle && uncle->_col == red) //情況一
{
uncle->_col = BLACK;
grandfather->_col = RED;
parent->_col = BLACK;
cur = grandfather; //迭代
parent = cur->_parent;
}
else //情況2.3
{
if (cur == parent->_right) //單側
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
六、代碼
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Colour //紅黑樹顏色枚舉
{
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;
Colour _col;
RBTreeNode(const pair<K, V>& kv) //構造函數
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
private:
Node* _root;
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentP = parent->_parent;
if (subLR) //左子樹的右子樹連接到父的右
subLR->_parent = parent;
parent->_left = subLR;
subL->_right = parent;
parent->_parent = subL;
// 如果parent是根節點，根新指向根節點的指針
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
// 如果parent是子樹，可能是其雙親的左子樹，也可能是右子樹
if (parentP->_left == parent)
parentP->_left = subL;
else
parentP->_right = subL;
subL->_parent = parentP;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentP = parent->_parent;
if (subRL)
subRL->_parent = parent;
parent->_right = subRL;
subR->_left = parent;
parent->_parent = subR;
// 如果parent是根節點，根新指向根節點的指針
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
// 如果parent是子樹，可能是其雙親的左子樹，也可能是右子樹
if (parentP->_left == parent)
parentP->_left = subR;
else
parentP->_right = subR;
subR->_parent = parentP;
}
}
void _Destory(Node* root)
{
if (root == nullptr)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
public:
RBTree()
:_root(nullptr)
{}
~RBTree()
{
_Destory(_root);
_root = nullptr;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return make_pair(_root, true);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(cur, false);
}
}
Node* newNode = new Node(kv);
newNode->_col = RED;
if (parent->_kv.first > kv.first)
{
parent->_left = newNode;
newNode->_parent = parent;
}
else
{
parent->_right = newNode;
newNode->_parent = parent;
}
cur = newNode;
while (parent && parent->_col == RED) //違反規則三
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) //左半邊
{
Node* uncle = parent->_right;
if (uncle && uncle->_col == red) //情況一
{
uncle->_col = BLACK;
grandfather->_col = RED;
parent->_col = BLACK;
cur = grandfather; //迭代
parent = cur->_parent;
}
else //情況2.3
{
if (cur == parent->_left) //單側
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break; //黑色數量無變化，不需要向上
}
}
else // parent == grandfather->_right
{
Node* uncle = parent->_left;
if (uncle && uncle->_col == red) //情況一
{
uncle->_col = BLACK;
grandfather->_col = RED;
parent->_col = BLACK;
cur = grandfather; //迭代
parent = cur->_parent;
}
else //情況2.3
{
if (cur == parent->_right) //單側
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK; //插入結束再次將根變為黑
return make_pair(newNode, true);
}
};
總結
本文對紅黑樹進行瞭介紹，並對構造，插入，查找進行瞭模擬實現。
以上就是C++ STL容器詳解之紅黑樹部分模擬實現的詳細內容，更多關於C++ STL紅黑樹實現的資料請關註WalkonNet其它相關文章！
推薦閱讀：
- C++數據結構之紅黑樹的實現
- C++數據結構紅黑樹全面分析
- C++實現AVL樹的基本操作指南
- C++AVL樹4種旋轉詳講(左單旋、右單旋、左右雙旋、右左雙旋)
- C++ AVL樹插入新節點後的四種調整情況梳理介紹