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