網站首頁 編程語言 正文
紅黑樹的概念
紅黑樹，是一種二叉搜索樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的
概念總結：
紅黑樹是二叉搜索樹的升級，結點里面存放的成員col標記當前結點的顏色，它的最長路徑最多是最短路徑的二倍，紅黑樹通過各個結點著色方式的限制接近平衡二叉樹，但是不同于AVL的是AVL是一顆高度平衡的二叉樹，紅黑樹只是接近平衡
紅黑樹的性質
每個結點不是紅色就是黑色根節點是黑色的如果一個節點是紅色的，則它的兩個孩子結點是黑色的對于每個結點，從該結點到其所有后代葉結點的簡單路徑上，均 包含相同數目的黑色結點每個葉子結點都是黑色的(此處的葉子結點指的是空結點)
紅黑樹性質總結：
1、紅黑樹結點的顏色只能是紅色或者黑色
2、紅黑樹根節點必須是黑色
3、紅黑樹并沒有連續的紅色結點
4、紅黑樹中從根到葉子的每一條路徑都包含相同的黑色結點
5、葉子是黑色，表示空的位置
最長路徑和最短路徑概念：
最短路徑：從根結點到葉子結點每一條路徑的結點顏色都是黑色的不包含紅色
最長路徑：紅黑交替，黑色結點和紅色結點的個數相等
思考：為什么滿足上面的性質，紅黑樹就能保證：其最長路徑中節點個數不會超過最短路徑節點個數的兩倍？
假設結點個數為N，那么最短路徑就是logN，最長路徑就是2 * logN，所有并不存在最長路徑超過最短路徑2倍的情況
紅黑樹的定義與樹結構
//枚舉紅黑顏色
enum colour
{
RED,
BLACK,
};
//定義紅黑樹結點結構
template<class K,class V>
struct RBTreeNode
{
//構造
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對象
//節點的顏色
colour _col; //定義枚舉變量
};
//定義紅黑樹
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//構造
RBTree()
:_root(nullptr)
{}
private:
Node* _root; //定義樹的根節點
};
插入
插入過程類似搜索樹的插入，重要的是維護紅黑樹的性質
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)//插入結點比當前結點大
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first) //插入結點比當前結點小
{
parent = cur;
cur = cur->_left;
}
else
{
return { cur, false }; //插入失敗
}
}
cur = new Node(kv);
cur->_col = RED; //新增結點顏色默認設置為RED
//判斷插入結點是否在parent的左邊或者右邊
if (parent->_kv.first > kv.first) //左邊
{
parent->_left = cur;
cur->_parent = parent;
}
else //右邊
{
parent->_right = cur;
cur->_parent = parent;
}
/* 紅黑樹性質處理：
如果這棵樹一開始是符合紅黑樹的性質，但在新增結點之后，
導致失去了紅黑樹的性質，這里需要控制結點的顏色和限制
每條路徑上黑色結點的個數，以上情況都要處理
*/
while (parent && parent->_col == RED) //父親存在且父親為紅色
{
Node* grandfather = parent->_parent; //祖父
//父親出現在祖父的左邊需要考慮的情況
if(parent == grandfather ->left)
{
//1、uncle存在，uncle為紅色
/*
如果parent和uncle都存在并且都為紅色這是情況一，
需要將parent和uncle的顏色變成紅色，祖父顏色變成黑色
更新cur、parent、grandfather、uncle 繼續向上調整
*/
//2、uncle不存在
/* 這里考慮兩種旋轉情況，直線單旋轉，折線雙旋
/*
cur出現在parent的左邊 ,右單旋轉
經過右單旋后，parent去做樹的根,祖父做為右子樹
//調節結點顏色
parent->_col = BLACK;
grandfather->_col = RED;
*/
/*
cur出現在parent的右邊，左右雙旋
經過雙旋后，cur作為樹的根，grandfather為右子樹
調節結點顏色
cur->_col = BLACK;
grandfather->_col = RED;
*/
*/
}
else //父親出現在祖父的右邊
{
Node* uncle = grandfather->_left; //叔叔在左子樹
/*
情況一：叔叔存在，且叔叔和父親都是紅色，那么就需要將父親
和叔叔結點的顏色變成黑色，再將祖父的顏色變成紅色，
繼續向上調整，更新孩子、父親、祖父、叔叔的位置
*/
/*
情況二：叔叔不存在
/*
1、新增結點出現在父親的右邊，直線情況，左單旋處理
旋轉完后parent去做父親的根，grandfather做父親
的左子樹
//調節顏色，根為黑，左右孩子為紅
2、新增結點出現在父親的左邊，會出現折現的情況，
引發雙旋，旋轉完后，cur變成根，
parent和grandfaher去做cur的左右孩子
//調節顏色,根結點為黑，左右孩子為紅
*/
*/
}
}
//如果父親不存在為了保證根結點是黑色的，這里一定得將根結點處理為黑色
_root->_col = BLACK;
}
新增結點插入后維護紅黑樹性質的主邏輯
//1、父親一定存在的情況，叔叔存在/不存在 父親叔叔結點顏色為紅色
while (parent && parent->_col == RED) //父親存在且父親為紅色
{
Node* grandfather = parent->_parent; //祖父
//如果父親和叔叔結點顏色都是紅色
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) //對應情況：uncle存在且為紅
{
//處理：父親和叔叔變成黑色，祖父變成紅色，繼續向上調整
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//向上調整
cur = grandfather; //調整孩子
parent = cur->_parent;//調整父親
}
else //uncle不存在，uncle存在且為黑
{
//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉點進行右單旋轉，
//旋轉完后將祖父的顏色變成紅色，將父親的顏色變成黑色
if (parent->_left == cur)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //parent->_right == cur
{
//折線情況(cur在parent的右邊)：這里會引發雙旋
RotateL(parent); //以parent為旋轉點進行左單旋
RotateR(grandfather); //以grandfather為旋轉點進行右單旋轉
//旋轉完后cur會去做樹的根，那么設置為黑色，
//為了保證每條路徑的黑色結點個數相同，grandfather結點顏色設置為紅
cur->_col = BLACK;
grandfather->_col = RED; //黑色 結點個數相同
}
}
}
else //父親在右子樹
{
Node* uncle = grandfather->_left; //叔叔在左子樹
if (uncle&& uncle->_col == RED) //情況一處理：叔叔存在，且叔叔的顏色是紅色的（包含了父親的顏色是紅色的情況）
{
//根據情況一處理即可：叔叔和父親變黑，
//祖父變紅(目的是為了每條路徑的黑色結點個數相同)，繼續向上
cur = grandfather; //孩子
parent = cur->_parent;//父親
}
else //叔叔不存在
{
if (cur == parent->_right) //新增結點在父親的右邊，直線情況左單旋處理
{
//左單旋轉，以grandfather為旋轉點，旋轉完后parent去做新的根，grandfather去做左子樹
RotateL(grandfather);
//調節顏色
grandfather->_col = RED;
parent->_col = BLACK;
}
else //新增結點在父親的左邊，折線情況，引發雙旋
{
//處理：以parenrt為旋轉點做右單旋，再以grandfather為旋轉點做左單旋
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) //對應情況：uncle存在且為紅
{
//處理：父親和叔叔變成黑色，祖父變成紅色，繼續向上調整
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//向上調整
cur = grandfather; //調整孩子
parent = cur->_parent;//調整父親
}
else //uncle不存在，uncle存在且為黑
{
//直線情況(cur在parent的左邊)：只考慮單旋，以grandfather為旋轉點進行右單旋轉，
//旋轉完后將祖父的顏色變成紅色，將父親的顏色變成黑色
if (parent->_left == cur)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //parent->_right == cur
{
//雙旋轉
}
}
//折線情況(cur在parent的右邊)：這里會引發雙旋 RotateL(parent); //以parent為旋轉點進行左單旋 RotateR(grandfather); //以grandfather為旋轉點進行右單旋轉 //旋轉完后cur會去做樹的根，那么設置為黑色， //為了保證每條路徑的黑色結點個數相同，grandfather結點顏色設置為紅 cur->_col = BLACK; grandfather->_col = RED;
旋轉
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;
}
}
驗證
/*
紅黑樹的幾點性質在于：
1、根結點必須是紅色的
2、不會出現連續的紅色結點
3、所有路徑的黑色結點個數是相同的
*/
bool _CheckBlance(Node* root, int isBlackNum, int count)
{
if (!root)
{
if (isBlackNum != count)
{
printf("黑色結點個數不均等\n");
return false;
}
return true; //遍歷完整棵樹，如果以上列舉的非法情況都不存在就返回true
}
//檢查是否出現連續的紅色結點
if (root->_col == RED && root->_parent->_col == RED)
{
printf("出現了連續的紅色結點\n");
return false;
}
//走前序遍歷的過程中記錄每一條路徑黑色結點的個數
if (root->_col == BLACK) count++;
//遞歸左右子樹
return _CheckBlance(root->_left, isBlackNum, count) &&
_CheckBlance(root->_right, isBlackNum, count);
}
//驗證紅黑樹
bool CheckBlance()
{
if (!_root) return true; //樹為null
//根結點是黑色的
if (_root->_col != BLACK)
{
printf("根結點不是黑色的\n");
return false;
}
//每一條路徑黑色結點的個數必須是相同的，
int isBlcakNum = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK) isBlcakNum++; // 統計某一條路徑的所以黑色結點個數
left = left->_left;
}
//檢查連續的紅色結點，檢查每一條路徑的黑色結點個數是否相等
return _CheckBlance(_root, isBlcakNum ,0);
}
紅黑樹與AVl樹的比較
紅黑樹與AVL樹的比較
紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的
時間復雜度都是O( log n)，紅黑樹不追求絕對平衡，其只需保證最長路徑不超過最短路徑的2倍，相對而言，降低了插入和旋轉的次數，所以在經常進行增刪的結構中性能比AVL樹更優，而且紅黑樹實現比較簡單，所以實際運用中紅黑樹更多。
紅黑樹的應用
C++ STL庫 – map/set、mutil_map/mutil_setJava 庫linux內核其他一些庫
完整代碼博主已經放在git上了，讀者可以參考
紅黑樹實現.
總結
原文鏈接：https://blog.csdn.net/m0_53421868/article/details/122394877
相關推薦
- 2022-06-20 正則表達式之字符串模式匹配實例詳解_正則表達式
- 2022-06-10 ASP.NET?Core使用EF查詢數據_實用技巧
- 2022-05-15 Pycharm創建Django項目示例實踐_python
- 2024-03-15 docker刪除、停止所有容器或鏡像
- 2022-08-20 Python為什么要保留顯式的self_python
- 2022-12-15 conda創建環境過程出現"Solving?environment:?failed"報錯的詳細解決方
- 2022-01-16 npm：使用npm link來調試本地的包
- 2022-07-13 Springboot 項目中使用 @RestControllerAdvice 注解不生效
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速