C語言實(shí)現(xiàn)紅黑樹詳細(xì)步驟+代碼
更新時間：2022年01月13日 10:29:14 作者：IT莫扎特
大家好，本篇文章主要講的是C語言實(shí)現(xiàn)紅黑樹詳細(xì)步驟+代碼，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下
紅黑樹的概念
紅黑樹，是一種二叉搜索樹，但在每個結(jié)點(diǎn)上增加一個存儲位表示結(jié)點(diǎn)的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的
概念總結(jié)：
紅黑樹是二叉搜索樹的升級，結(jié)點(diǎn)里面存放的成員col標(biāo)記當(dāng)前結(jié)點(diǎn)的顏色，它的最長路徑最多是最短路徑的二倍，紅黑樹通過各個結(jié)點(diǎn)著色方式的限制接近平衡二叉樹，但是不同于AVL的是AVL是一顆高度平衡的二叉樹，紅黑樹只是接近平衡
紅黑樹的性質(zhì)
每個結(jié)點(diǎn)不是紅色就是黑色根節(jié)點(diǎn)是黑色的如果一個節(jié)點(diǎn)是紅色的，則它的兩個孩子結(jié)點(diǎn)是黑色的對于每個結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡單路徑上，均 包含相同數(shù)目的黑色結(jié)點(diǎn)每個葉子結(jié)點(diǎn)都是黑色的(此處的葉子結(jié)點(diǎn)指的是空結(jié)點(diǎn))
紅黑樹性質(zhì)總結(jié)：
1、紅黑樹結(jié)點(diǎn)的顏色只能是紅色或者黑色
2、紅黑樹根節(jié)點(diǎn)必須是黑色
3、紅黑樹并沒有連續(xù)的紅色結(jié)點(diǎn)
4、紅黑樹中從根到葉子的每一條路徑都包含相同的黑色結(jié)點(diǎn)
5、葉子是黑色，表示空的位置
最長路徑和最短路徑概念：
最短路徑：從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)每一條路徑的結(jié)點(diǎn)顏色都是黑色的不包含紅色
最長路徑：紅黑交替，黑色結(jié)點(diǎn)和紅色結(jié)點(diǎn)的個數(shù)相等
思考：為什么滿足上面的性質(zhì)，紅黑樹就能保證：其最長路徑中節(jié)點(diǎn)個數(shù)不會超過最短路徑節(jié)點(diǎn)個數(shù)的兩倍？
假設(shè)結(jié)點(diǎn)個數(shù)為N，那么最短路徑就是logN，最長路徑就是2 * logN，所有并不存在最長路徑超過最短路徑2倍的情況
紅黑樹的定義與樹結(jié)構(gòu)
//枚舉紅黑顏色
enum colour
{
RED,
BLACK,
};
//定義紅黑樹結(jié)點(diǎn)結(jié)構(gòu)
template<class K,class V>
struct RBTreeNode
{
//構(gòu)造
RBTreeNode(const pair<K, V>& kv = {0,0})
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
,_col(BLACK)
{ }
//定義三叉鏈
RBTreeNode<K, V>* _left; //左孩子
RBTreeNode<K, V>* _right;//右孩子
RBTreeNode<K, V>* _parent; //父親
pair<K, V> _kv; //pair對象
//節(jié)點(diǎn)的顏色
colour _col; //定義枚舉變量
};
//定義紅黑樹
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//構(gòu)造
RBTree()
:_root(nullptr)
{}
private:
Node* _root; //定義樹的根節(jié)點(diǎn)
};
插入
插入過程類似搜索樹的插入，重要的是維護(hù)紅黑樹的性質(zhì)
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (!_root) //空樹處理
{
_root = new Node(kv);
_root->_col = BLACK;
return { _root, true };
}
//二叉搜索樹的插入邏輯
Node* cur = _root, * parent = nullptr;
while (cur)
{
if (cur->_kv.first < kv.first)//插入結(jié)點(diǎn)比當(dāng)前結(jié)點(diǎn)大
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first) //插入結(jié)點(diǎn)比當(dāng)前結(jié)點(diǎn)小
{
parent = cur;
cur = cur->_left;
}
else
{
return { cur, false }; //插入失敗
}
}
cur = new Node(kv);
cur->_col = RED; //新增結(jié)點(diǎn)顏色默認(rèn)設(shè)置為RED
//判斷插入結(jié)點(diǎn)是否在parent的左邊或者右邊
if (parent->_kv.first > kv.first) //左邊
{
parent->_left = cur;
cur->_parent = parent;
}
else //右邊
{
parent->_right = cur;
cur->_parent = parent;
}
/* 紅黑樹性質(zhì)處理：
如果這棵樹一開始是符合紅黑樹的性質(zhì)，但在新增結(jié)點(diǎn)之后，
導(dǎo)致失去了紅黑樹的性質(zhì)，這里需要控制結(jié)點(diǎn)的顏色和限制
每條路徑上黑色結(jié)點(diǎn)的個數(shù)，以上情況都要處理
*/
while (parent && parent->_col == RED) //父親存在且父親為紅色
{
Node* grandfather = parent->_parent; //祖父
//父親出現(xiàn)在祖父的左邊需要考慮的情況
if(parent == grandfather ->left)
{
//1、uncle存在，uncle為紅色
/*
如果parent和uncle都存在并且都為紅色這是情況一，
需要將parent和uncle的顏色變成紅色，祖父顏色變成黑色
更新cur、parent、grandfather、uncle 繼續(xù)向上調(diào)整
*/
//2、uncle不存在
/* 這里考慮兩種旋轉(zhuǎn)情況，直線單旋轉(zhuǎn)，折線雙旋
/*
cur出現(xiàn)在parent的左邊 ,右單旋轉(zhuǎn)
經(jīng)過右單旋后，parent去做樹的根,祖父做為右子樹
//調(diào)節(jié)結(jié)點(diǎn)顏色
parent->_col = BLACK;
grandfather->_col = RED;
*/
/*
cur出現(xiàn)在parent的右邊，左右雙旋
經(jīng)過雙旋后，cur作為樹的根，grandfather為右子樹
調(diào)節(jié)結(jié)點(diǎn)顏色
cur->_col = BLACK;
grandfather->_col = RED;
*/
*/
}
else //父親出現(xiàn)在祖父的右邊
{
Node* uncle = grandfather->_left; //叔叔在左子樹
/*
情況一：叔叔存在，且叔叔和父親都是紅色，那么就需要將父親
和叔叔結(jié)點(diǎn)的顏色變成黑色，再將祖父的顏色變成紅色，
繼續(xù)向上調(diào)整，更新孩子、父親、祖父、叔叔的位置
*/
/*
情況二：叔叔不存在
/*
1、新增結(jié)點(diǎn)出現(xiàn)在父親的右邊，直線情況，左單旋處理
旋轉(zhuǎn)完后parent去做父親的根，grandfather做父親
的左子樹
//調(diào)節(jié)顏色，根為黑，左右孩子為紅
2、新增結(jié)點(diǎn)出現(xiàn)在父親的左邊，會出現(xiàn)折現(xiàn)的情況，
引發(fā)雙旋，旋轉(zhuǎn)完后，cur變成根，
parent和grandfaher去做cur的左右孩子
//調(diào)節(jié)顏色,根結(jié)點(diǎn)為黑，左右孩子為紅
*/
*/
}
}
//如果父親不存在為了保證根結(jié)點(diǎn)是黑色的，這里一定得將根結(jié)點(diǎn)處理為黑色
_root->_col = BLACK;
}
新增結(jié)點(diǎn)插入后維護(hù)紅黑樹性質(zhì)的主邏輯
//1、父親一定存在的情況，叔叔存在/不存在 父親叔叔結(jié)點(diǎn)顏色為紅色
while (parent && parent->_col == RED) //父親存在且父親為紅色
{
Node* grandfather = parent->_parent; //祖父
//如果父親和叔叔結(jié)點(diǎn)顏色都是紅色
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) //對應(yīng)情況：uncle存在且為紅
{
//處理：父親和叔叔變成黑色，祖父變成紅色，繼續(xù)向上調(diào)整
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//向上調(diào)整
cur = grandfather; //調(diào)整孩子
parent = cur->_parent;//調(diào)整父親
}
else //uncle不存在，uncle存在且為黑
{
//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)，
//旋轉(zhuǎn)完后將祖父的顏色變成紅色，將父親的顏色變成黑色
if (parent->_left == cur)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //parent->_right == cur
{
//折線情況(cur在parent的右邊)：這里會引發(fā)雙旋
RotateL(parent); //以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
RotateR(grandfather); //以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)
//旋轉(zhuǎn)完后cur會去做樹的根，那么設(shè)置為黑色，
//為了保證每條路徑的黑色結(jié)點(diǎn)個數(shù)相同，grandfather結(jié)點(diǎn)顏色設(shè)置為紅
cur->_col = BLACK;
grandfather->_col = RED; //黑色 結(jié)點(diǎn)個數(shù)相同
}
}
}
else //父親在右子樹
{
Node* uncle = grandfather->_left; //叔叔在左子樹
if (uncle&& uncle->_col == RED) //情況一處理：叔叔存在，且叔叔的顏色是紅色的（包含了父親的顏色是紅色的情況）
{
//根據(jù)情況一處理即可：叔叔和父親變黑，
//祖父變紅(目的是為了每條路徑的黑色結(jié)點(diǎn)個數(shù)相同)，繼續(xù)向上
cur = grandfather; //孩子
parent = cur->_parent;//父親
}
else //叔叔不存在
{
if (cur == parent->_right) //新增結(jié)點(diǎn)在父親的右邊，直線情況左單旋處理
{
//左單旋轉(zhuǎn)，以grandfather為旋轉(zhuǎn)點(diǎn)，旋轉(zhuǎn)完后parent去做新的根，grandfather去做左子樹
RotateL(grandfather);
//調(diào)節(jié)顏色
grandfather->_col = RED;
parent->_col = BLACK;
}
else //新增結(jié)點(diǎn)在父親的左邊，折線情況，引發(fā)雙旋
{
//處理：以parenrt為旋轉(zhuǎn)點(diǎn)做右單旋，再以grandfather為旋轉(zhuǎn)點(diǎn)做左單旋
RotateR(parent); //右旋
RotateL(grandfather); //左旋
parent->_col = grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
_root->_col = BLACK;
}
拆解討論：
以下只列舉parent在grandfather左邊的情況，而parent在grandfather右邊的情況處理方式只是反過來的，讀者可以自行畫圖，這里僅留參考代碼
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) //對應(yīng)情況：uncle存在且為紅
{
//處理：父親和叔叔變成黑色，祖父變成紅色，繼續(xù)向上調(diào)整
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//向上調(diào)整
cur = grandfather; //調(diào)整孩子
parent = cur->_parent;//調(diào)整父親
}
else //uncle不存在，uncle存在且為黑
{
//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)，
//旋轉(zhuǎn)完后將祖父的顏色變成紅色，將父親的顏色變成黑色
if (parent->_left == cur)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //parent->_right == cur
{
//雙旋轉(zhuǎn)
}
}
//折線情況(cur在parent的右邊)：這里會引發(fā)雙旋 RotateL(parent); //以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋 RotateR(grandfather); //以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn) //旋轉(zhuǎn)完后cur會去做樹的根，那么設(shè)置為黑色， //為了保證每條路徑的黑色結(jié)點(diǎn)個數(shù)相同，grandfather結(jié)點(diǎn)顏色設(shè)置為紅 cur->_col = BLACK; grandfather->_col = RED;
旋轉(zhuǎn)
void RotateR(Node* parent) //右單旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent; //防止subLR為nullptr
subL->_right = parent;
Node* parent_parent = parent->_parent; //指針備份
parent->_parent = subL;
if (_root == parent) //如果parent就是樹的根
{
_root = subL; //subL取代parent
_root->_parent = nullptr;
}
else //如果parent并不是樹的根
{
if (parent_parent->_left == parent) parent->_left = subL;
else parent_parent->_right = subL;
subL->_parent = parent_parent; //subL去做parent_parent的孩子
}
}
//左單旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
subR->_left = parent;
Node* parent_parent = parent->_parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent_parent->_left == parent) parent_parent->_left = subR;
else parent_parent->_right = subR;
subR->_parent = parent_parent;
}
}
驗(yàn)證
/*
紅黑樹的幾點(diǎn)性質(zhì)在于：
1、根結(jié)點(diǎn)必須是紅色的
2、不會出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)
3、所有路徑的黑色結(jié)點(diǎn)個數(shù)是相同的
*/
bool _CheckBlance(Node* root, int isBlackNum, int count)
{
if (!root)
{
if (isBlackNum != count)
{
printf("黑色結(jié)點(diǎn)個數(shù)不均等\n");
return false;
}
return true; //遍歷完整棵樹，如果以上列舉的非法情況都不存在就返回true
}
//檢查是否出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)
if (root->_col == RED && root->_parent->_col == RED)
{
printf("出現(xiàn)了連續(xù)的紅色結(jié)點(diǎn)\n");
return false;
}
//走前序遍歷的過程中記錄每一條路徑黑色結(jié)點(diǎn)的個數(shù)
if (root->_col == BLACK) count++;
//遞歸左右子樹
return _CheckBlance(root->_left, isBlackNum, count) &&
_CheckBlance(root->_right, isBlackNum, count);
}
//驗(yàn)證紅黑樹
bool CheckBlance()
{
if (!_root) return true; //樹為null
//根結(jié)點(diǎn)是黑色的
if (_root->_col != BLACK)
{
printf("根結(jié)點(diǎn)不是黑色的\n");
return false;
}
//每一條路徑黑色結(jié)點(diǎn)的個數(shù)必須是相同的，
int isBlcakNum = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK) isBlcakNum++; // 統(tǒng)計某一條路徑的所以黑色結(jié)點(diǎn)個數(shù)
left = left->_left;
}
//檢查連續(xù)的紅色結(jié)點(diǎn)，檢查每一條路徑的黑色結(jié)點(diǎn)個數(shù)是否相等
return _CheckBlance(_root, isBlcakNum ,0);
}
紅黑樹與AVl樹的比較
紅黑樹與AVL樹的比較
紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的
時間復(fù)雜度都是O( log n)，紅黑樹不追求絕對平衡，其只需保證最長路徑不超過最短路徑的2倍，相對而言，降低了插入和旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)，而且紅黑樹實(shí)現(xiàn)比較簡單，所以實(shí)際運(yùn)用中紅黑樹更多。
紅黑樹的應(yīng)用
C++ STL庫 – map/set、mutil_map/mutil_setJava 庫linux內(nèi)核其他一些庫
完整代碼博主已經(jīng)放在git上了，讀者可以參考
紅黑樹實(shí)現(xiàn).
總結(jié)
到此這篇關(guān)于C語言實(shí)現(xiàn)紅黑樹詳細(xì)步驟+代碼的文章就介紹到這了,更多相關(guān)C語言紅黑樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關(guān)文章
本篇文章是基礎(chǔ)篇，適合c語言剛?cè)腴T的朋友，本文主要介紹了c語言的操作符基礎(chǔ)理論，希望可以幫助大家快速入門c語言的世界，更好的理解c語言2021-08-08
這篇文章主要介紹了C語言泛型編程,針對泛型的用法做了深入淺出的實(shí)例介紹,是C程序設(shè)計中非常實(shí)用的技巧,需要的朋友可以參考下2014-09-09
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡單猜拳小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-03-03
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)萬年歷,文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10
C++標(biāo)準(zhǔn)庫實(shí)現(xiàn)WAV文件讀寫的操作
本文將使用標(biāo)準(zhǔn)C++庫實(shí)現(xiàn)對數(shù)據(jù)為PCM格式的WAV文件的讀寫操作，只使用標(biāo)準(zhǔn)C++庫函數(shù)，不依賴于其他的庫，對C++標(biāo)準(zhǔn)庫實(shí)現(xiàn)WAV文件讀寫相關(guān)知識感興趣的朋友一起看看吧2022-01-01
對比C語言中memccpy()函數(shù)和memcpy()函數(shù)的用法
這篇文章主要介紹了對比C語言中memccpy()函數(shù)和memcpy()函數(shù)的用法,二者都是用于復(fù)制內(nèi)存內(nèi)容,注意區(qū)別,需要的朋友可以參考下2015-08-08
這篇文章主要介紹了c++難以發(fā)現(xiàn)的bug(有趣)的相關(guān)資料,需要的朋友可以參考下2017-10-10
匯編語言中有一種移位指令叫做循環(huán)左移（ROL）,下面這篇文章主要給大家介紹了關(guān)于C語言字符串左旋的兩種實(shí)現(xiàn)方法,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-02-02
在C++中實(shí)現(xiàn)aligned_malloc的方法
這篇文章主要介紹了在C++中實(shí)現(xiàn)aligned_malloc的方法，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-03-03
下面小編就為大家?guī)硪黄猚++ 端口掃描程序?qū)崿F(xiàn)案例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05