網(wǎng)站首頁 編程語言 正文
紅黑樹的概念
紅黑樹，是一種二叉搜索樹，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的
概念總結(jié)：
紅黑樹是二叉搜索樹的升級，結(jié)點里面存放的成員col標(biāo)記當(dāng)前結(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é)點比當(dāng)前結(jié)點大
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first) //插入結(jié)點比當(dāng)前結(jié)點小
{
parent = cur;
cur = cur->_left;
}
else
{
return { cur, false }; //插入失敗
}
}
cur = new Node(kv);
cur->_col = RED; //新增結(jié)點顏色默認(rèn)設(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é)點之后，
導(dǎo)致失去了紅黑樹的性質(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樹都是高效的平衡二叉樹，增刪改查的
時間復(fù)雜度都是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é)
原文鏈接：https://blog.csdn.net/m0_53421868/article/details/122394877
相關(guān)推薦
- 2022-06-16 .Net?Core解決WebAPI中返回時間格式帶T的問題_實用技巧
- 2022-07-18 C++函數(shù)模板和類模板詳解
- 2022-03-26 C語言實現(xiàn)字符串替換的示例代碼_C 語言
- 2023-04-07 C語言如何計算字符串長度_C 語言
- 2022-09-22 Linux 內(nèi)存和SWAP使用
- 2022-05-12 Python 正則替換內(nèi)容
- 2022-11-06 SQL?Server?Reporting?Services?匿名登錄的問題及解決方案_MsSql
- 2022-05-21 python實現(xiàn)會員信息管理系統(tǒng)(List)_python
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速