C++?STL容器詳解之紅黑樹部分模擬實現(xiàn)
更新時間：2021年12月07日 17:01:37 作者：TT在長大
本文主要對紅黑樹進行了詳細介紹，并對其核心功能進行了模擬實現(xiàn)。文中的代碼對我們的學(xué)習(xí)或工作有一定的價值，感興趣的小伙伴可以了解一下
一、紅黑樹的概念
紅黑樹（Red Black Tree），是在計算機科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，是一種二叉搜索樹，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。
二、紅黑樹的性質(zhì)
1. 每個結(jié)點不是紅色就是黑色；
2. 根節(jié)點是黑色的；
3. 如果一個節(jié)點是紅色的，則它的兩個孩子結(jié)點是黑色的；
4. 對于每個結(jié)點，從該結(jié)點到其所有后代葉結(jié)點的簡單路徑上，均 包含相同數(shù)目的黑色結(jié)點；
5. 每個葉子結(jié)點都是黑色的(此處的葉子結(jié)點指的是空結(jié)點)；
滿足上面的性質(zhì)，紅黑樹就能保證其最長路徑中節(jié)點個數(shù)不會超過最短路徑節(jié)點個數(shù)的兩倍。
三、紅黑樹節(jié)點的定義
enum Colour //紅黑樹顏色枚舉
{
RED,
BLACK,
};
template<class K, class V>
struct RBTreeNode //節(jié)點結(jié)構(gòu)體
{
RBTreeNode<K, V>* _left; //左子樹
RBTreeNode<K, V>* _right; //右子樹
RBTreeNode<K, V>* _parent; //父節(jié)點
pair<K, V> _kv;
Colour _col;
RBTreeNode(const pair<K, V>& kv) //構(gòu)造函數(shù)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
插入時默認為紅色節(jié)點，因為紅色可能會破壞規(guī)則3，黑色一定會破壞規(guī)則4，所以默認紅色。
四、紅黑樹結(jié)構(gòu)?
為了后續(xù)實現(xiàn)關(guān)聯(lián)式容器簡單，紅黑樹的實現(xiàn)中增加一個頭結(jié)點，因為跟節(jié)點必須為黑色，為了與根節(jié)點進行區(qū)分，將頭結(jié)點給成黑色，并且讓頭結(jié)點的 parent 域指向紅黑樹的根節(jié)點，left域指向紅黑樹中最小的節(jié)點，right域指向紅黑樹中最大的節(jié)點，如下:
五、 紅黑樹的插入操作
紅黑樹是在二叉搜索樹的基礎(chǔ)上加上其平衡限制條件，因此紅黑樹的插入可分為兩步：
1. 按照二叉搜索的樹規(guī)則插入新節(jié)點：
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) //違反規(guī)則三
{
}
_root->_col = BLACK; //插入結(jié)束再次將根變?yōu)楹?
return make_pair(cur, true);
}
2. 檢測新節(jié)點插入后，紅黑樹的性質(zhì)是否造到破壞
因為新節(jié)點的默認顏色是紅色，因此：如果其雙親節(jié)點的顏色是黑色，沒有違反紅黑樹任何性質(zhì)，則不需要調(diào)整；但當(dāng)新插入節(jié)點的雙親節(jié)點顏色為紅色時，就違反了性質(zhì)三不能有連在一起的紅色節(jié)點，此時需要對紅黑樹分情況來討論：
cur為當(dāng)前節(jié)點，p為父節(jié)點，g為祖父節(jié)點，u為叔叔節(jié)點
情況一：cur為紅，p為紅，g為黑，u存在且為紅
如果g是根節(jié)點，調(diào)整完成后，需要將g改為黑色，如果g是子樹，g一定有父節(jié)點，且如果為紅色呃，繼續(xù)向上調(diào)整。
將p,u改為黑，g改為紅，然后把g當(dāng)成cur，繼續(xù)向上調(diào)整 。
情況二: cur為紅，p為紅，g為黑，u不存在/u為黑
u的情況有兩種：
1.如果u節(jié)點不存在，則cur一定是新插入節(jié)點，因為如果cur不是新插入節(jié)點，則cur和p一定有一個節(jié)點的顏色是黑色，就不滿足性質(zhì)4：每條路徑黑色節(jié)點個數(shù)相同。
2.如果u節(jié)點存在，則其一定是黑色的，那么cur節(jié)點原來的顏色一定是黑色的，現(xiàn)在看到其是紅色的原因是因為cur的子樹在調(diào)整的過程中將cur節(jié)點的顏色由黑色改成紅色。
p為g的左孩子，cur為p的左孩子，則進行右單旋轉(zhuǎn)；
p為g的右孩子，cur為p的右孩子，則進行左單旋轉(zhuǎn)。
p變黑，g變紅。
情況三: cur為紅，p為紅，g為黑，u不存在/u為黑
需要進行雙旋。
代碼實現(xiàn)：
while (parent && parent->_col == RED) //違反規(guī)則三
{
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) //單側(cè)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break; //黑色數(shù)量無變化，不需要向上
}
}
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) //單側(cè)
{
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 //節(jié)點結(jié)構(gòu)體
{
RBTreeNode<K, V>* _left; //左子樹
RBTreeNode<K, V>* _right; //右子樹
RBTreeNode<K, V>* _parent; //父節(jié)點
pair<K, V> _kv;
Colour _col;
RBTreeNode(const pair<K, V>& kv) //構(gòu)造函數(shù)
: _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是根節(jié)點，根新指向根節(jié)點的指針
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是根節(jié)點，根新指向根節(jié)點的指針
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) //違反規(guī)則三
{
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) //單側(cè)
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break; //黑色數(shù)量無變化，不需要向上
}
}
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) //單側(cè)
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else //折
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK; //插入結(jié)束再次將根變?yōu)楹?
return make_pair(newNode, true);
}
};
總結(jié)
本文對紅黑樹進行了介紹，并對構(gòu)造，插入，查找進行了模擬實現(xiàn)。
以上就是C++ STL容器詳解之紅黑樹部分模擬實現(xiàn)的詳細內(nèi)容，更多關(guān)于C++ STL紅黑樹實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
線性探測法的優(yōu)點：只要散列表未滿，總能找到一個不沖突的散列地址；缺點：每個產(chǎn)生沖突的記錄被散列到離沖突最近的空地址上，從而又增加了更多的沖突機會2022-05-05
在1999年版本的ISO C 標準中，宏可以象函數(shù)一樣，定義時可以帶有可變參數(shù)。宏的語法和函數(shù)的語法類似2013-09-09
位圖實際上就是一個數(shù)組，因為數(shù)組有隨機訪問的功能，比較方便查找，這個數(shù)組一般是整形，今天通過本文給大家分享c++位圖的實現(xiàn)原理及實現(xiàn)代碼，感興趣的朋友跟隨小編一起看看吧2021-05-05
這篇文章主要為大家詳細介紹了C++實現(xiàn)掃雷經(jīng)典小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
C++ min/max_element 函數(shù)用法詳解
這篇文章主要介紹了C++ min/max_element 函數(shù)用法，本文給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2020-02-02
這篇文章主要介紹了C++之關(guān)于string對象的大小比較方式,具有很好的 參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
C語言中二維數(shù)組作為函數(shù)參數(shù)來傳遞的三種方法
這篇文章主要給大家介紹了關(guān)于C語言中二維數(shù)組作為函數(shù)參數(shù)來傳遞的三種方法，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用C語言有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
這篇文章主要為大家詳細介紹了C語言單鏈表實現(xiàn)多項式相加，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
C語言中的下標運算符用于訪問數(shù)組或指針變量中的元素,它使用方括號 [] 來表示,并在方括號內(nèi)指定元素的索引位置,本文給大家詳細的講解一下C++的下標運算符,需要的朋友可以參考下2023-09-09
這篇文章介紹了C++超集C++/CLI模塊的基本類型，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-07-07