C語(yǔ)言實(shí)現(xiàn)紅黑樹詳細(xì)步驟+代碼
更新時(shí)間：2022年01月13日 10:29:14 作者：IT莫扎特
大家好，本篇文章主要講的是C語(yǔ)言實(shí)現(xiàn)紅黑樹詳細(xì)步驟+代碼，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下
紅黑樹的概念
紅黑樹，是一種二叉搜索樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。 通過對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，因而是接近平衡的
概念總結(jié)：
紅黑樹是二叉搜索樹的升級(jí)，結(jié)點(diǎn)里面存放的成員col標(biāo)記當(dāng)前結(jié)點(diǎn)的顏色，它的最長(zhǎng)路徑最多是最短路徑的二倍，紅黑樹通過各個(gè)結(jié)點(diǎn)著色方式的限制接近平衡二叉樹，但是不同于AVL的是AVL是一顆高度平衡的二叉樹，紅黑樹只是接近平衡
紅黑樹的性質(zhì)
每個(gè)結(jié)點(diǎn)不是紅色就是黑色根節(jié)點(diǎn)是黑色的如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子結(jié)點(diǎn)是黑色的對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑上，均 包含相同數(shù)目的黑色結(jié)點(diǎn)每個(gè)葉子結(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、葉子是黑色，表示空的位置
最長(zhǎng)路徑和最短路徑概念：
最短路徑：從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)每一條路徑的結(jié)點(diǎn)顏色都是黑色的不包含紅色
最長(zhǎng)路徑：紅黑交替，黑色結(jié)點(diǎn)和紅色結(jié)點(diǎn)的個(gè)數(shù)相等
思考：為什么滿足上面的性質(zhì)，紅黑樹就能保證：其最長(zhǎng)路徑中節(jié)點(diǎn)個(gè)數(shù)不會(huì)超過最短路徑節(jié)點(diǎn)個(gè)數(shù)的兩倍？
假設(shè)結(jié)點(diǎn)個(gè)數(shù)為N，那么最短路徑就是logN，最長(zhǎng)路徑就是2 * logN，所有并不存在最長(zhǎng)路徑超過最短路徑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對(duì)象
//節(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)的個(gè)數(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)在父親的左邊，會(huì)出現(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) //對(duì)應(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的右邊)：這里會(huì)引發(fā)雙旋
RotateL(parent); //以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋
RotateR(grandfather); //以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn)
//旋轉(zhuǎn)完后cur會(huì)去做樹的根，那么設(shè)置為黑色，
//為了保證每條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)相同，grandfather結(jié)點(diǎn)顏色設(shè)置為紅
cur->_col = BLACK;
grandfather->_col = RED; //黑色 結(jié)點(diǎn)個(gè)數(shù)相同
}
}
}
else //父親在右子樹
{
Node* uncle = grandfather->_left; //叔叔在左子樹
if (uncle&& uncle->_col == RED) //情況一處理：叔叔存在，且叔叔的顏色是紅色的（包含了父親的顏色是紅色的情況）
{
//根據(jù)情況一處理即可：叔叔和父親變黑，
//祖父變紅(目的是為了每條路徑的黑色結(jié)點(diǎn)個(gè)數(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) //對(duì)應(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的右邊)：這里會(huì)引發(fā)雙旋 RotateL(parent); //以parent為旋轉(zhuǎn)點(diǎn)進(jìn)行左單旋 RotateR(grandfather); //以grandfather為旋轉(zhuǎn)點(diǎn)進(jìn)行右單旋轉(zhuǎn) //旋轉(zhuǎn)完后cur會(huì)去做樹的根，那么設(shè)置為黑色， //為了保證每條路徑的黑色結(jié)點(diǎn)個(gè)數(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、不會(huì)出現(xiàn)連續(xù)的紅色結(jié)點(diǎn)
3、所有路徑的黑色結(jié)點(diǎn)個(gè)數(shù)是相同的
*/
bool _CheckBlance(Node* root, int isBlackNum, int count)
{
if (!root)
{
if (isBlackNum != count)
{
printf("黑色結(jié)點(diǎn)個(gè)數(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)的個(gè)數(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)的個(gè)數(shù)必須是相同的，
int isBlcakNum = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK) isBlcakNum++; // 統(tǒng)計(jì)某一條路徑的所以黑色結(jié)點(diǎn)個(gè)數(shù)
left = left->_left;
}
//檢查連續(xù)的紅色結(jié)點(diǎn)，檢查每一條路徑的黑色結(jié)點(diǎn)個(gè)數(shù)是否相等
return _CheckBlance(_root, isBlcakNum ,0);
}
紅黑樹與AVl樹的比較
紅黑樹與AVL樹的比較
紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的
時(shí)間復(fù)雜度都是O( log n)，紅黑樹不追求絕對(duì)平衡，其只需保證最長(zhǎng)路徑不超過最短路徑的2倍，相對(duì)而言，降低了插入和旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)，而且紅黑樹實(shí)現(xiàn)比較簡(jiǎn)單，所以實(shí)際運(yùn)用中紅黑樹更多。
紅黑樹的應(yīng)用
C++ STL庫(kù) – map/set、mutil_map/mutil_setJava 庫(kù)linux內(nèi)核其他一些庫(kù)
完整代碼博主已經(jīng)放在git上了，讀者可以參考
紅黑樹實(shí)現(xiàn).
總結(jié)
到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)紅黑樹詳細(xì)步驟+代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言紅黑樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關(guān)文章
C++?數(shù)據(jù)結(jié)構(gòu)超詳細(xì)講解順序表
程序中經(jīng)常需要將一組數(shù)據(jù)元素作為整體管理和使用，需要?jiǎng)?chuàng)建這種元素組，用變量記錄它們，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化，順序表則是將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示2022-03-03
今天小編就為大家分享一篇關(guān)于如何寫出優(yōu)美的C語(yǔ)言代碼，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-01-01
C++中priority_queue的使用與模擬實(shí)現(xiàn)
本文主要介紹了C++中priority_queue的使用與模擬實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
通俗易懂講解C語(yǔ)言與Java中二叉樹的三種非遞歸遍歷方式
二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多的數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變過來的。二叉樹的前，中，后3種遍歷方式，因?yàn)闃涞亩x本身就是遞歸定義的，所以采用遞歸的方法來實(shí)現(xiàn)是很簡(jiǎn)單的2021-09-09
C++11中，線程我們可以理解為對(duì)應(yīng)一個(gè)thread對(duì)象，任務(wù)可以理解為要執(zhí)行的函數(shù)，通常是耗時(shí)的函數(shù)。線程過多或者頻繁創(chuàng)建和銷毀線程會(huì)帶來調(diào)度開銷，進(jìn)而影響緩存局部性和整體性能2021-12-12
C語(yǔ)言運(yùn)算符的優(yōu)先級(jí)和結(jié)合性實(shí)例詳解
本文主要介紹C語(yǔ)言運(yùn)算符的知識(shí),這里對(duì)運(yùn)算符的優(yōu)先級(jí)和結(jié)合性做出了詳解,并附實(shí)例代碼,希望能幫助有需要的小伙伴2016-07-07
數(shù)據(jù)結(jié)構(gòu)之位圖（bitmap）詳解
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之位圖詳解,本文講解了位圖的基本知識(shí)、位圖的實(shí)現(xiàn)方法、位圖的應(yīng)用等內(nèi)容,需要的朋友可以參考下2014-08-08
這篇文章主要為大家介紹了C++入門之內(nèi)存處理，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-11-11
本文分別給大家介紹了2個(gè)C++在Linux平臺(tái)和windows平臺(tái)下實(shí)現(xiàn)字符串模糊匹配的方法，基本的核心思想都是一樣的，均是使用fnmatch函數(shù)，有需要的小伙伴可以參考下。2016-04-04
其實(shí)這兩個(gè)東西挺難理解的，應(yīng)該也沒有那么重要，了解一下好了，主要還是要多多理解數(shù)組指針的運(yùn)算2013-08-08