網站首頁 編程語言 正文
一、什么是紅黑樹
紅黑樹在表意上就是一棵每個節點帶有顏色的二叉搜索樹，并通過對節點顏色的控制，使該二叉搜索樹達到盡量平衡的狀態。所謂盡量平衡的狀態就是：紅黑樹確保沒有一條路徑比其他路徑長兩倍。
和AVL樹不同的是，AVL樹是一棵平衡樹，而紅黑樹可能平衡也可能不平衡(因為是盡量平衡的狀態)
二、紅黑樹的約定
要實現一棵紅黑樹，即要紅黑樹確保沒有一條路徑比其他路徑長兩倍。通過對節點顏色的約定來實現這一目標。
1.根節點是黑色的。
2.如果一個節點是紅色的，則它的兩個孩子都是黑色的。
3.對于每個節點，從該節點到其所有后代節點的簡單路徑上，均包含相同數量的黑色節點。
實現了這三條顏色規則的二叉搜索樹，即也實現了沒有一條路徑比其他路徑長兩倍，即實現了一棵紅黑樹。
三、紅黑樹vsAVL
1、調整平衡的實現機制不同
紅黑樹根據節點顏色(同一父節點出發到葉子節點，所有路徑上的黑色節點數目一樣)，一些約定和旋轉實現。
AVL根據樹的平衡因子(所有節點的左右子樹高度差的絕對值不超過1)和旋轉決定。
2、紅黑樹的插入效率更高
紅黑樹是用非嚴格的平衡來換取增刪節點時候旋轉次數的降低，任何不平衡都會在三次旋轉之內解決，紅黑樹并不追求“完全平衡”，它只要求部分地達到平衡要求，降低了對旋轉的要求，從而提高了性能
而AVL是嚴格平衡樹(高度平衡的二叉搜索樹)，因此在增加或者刪除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多。所以紅黑樹的插入效率更高
3、AVL查找效率高
如果你的應用中，查詢的次數遠遠大于插入和刪除，那么選擇AVL樹，如果查詢和插入刪除次數幾乎差不多，應選擇紅黑樹。即，有時僅為了排序（建立-遍歷-刪除），不查找或查找次數很少，R-B樹合算一些。
四、紅黑樹的實現
實現一棵紅黑樹，本質是實現它的插入函數，使插入函數可以實現紅黑樹的顏色約定，它的實現分為兩步，即先找到插入的位置，再控制平衡。插入函數返回值設計為bool，插入成功返回true，失敗返回false。控制平衡時，需要關注四個節點，即新插入的節點，它的父節點，它的叔叔節點，它的祖父節點。
1.找到插入的位置
當為第一個節點的時候，顏色設為黑，直接插入。
當插入的不是第一個節點時，顏色設為紅，需要根據二叉搜索樹的性質找到插入位置。并實現三叉鏈。
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = Black;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
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 false;
}
}
cur = new Node(kv);
cur->_col= Red;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}2.控制平衡
(1)當父節點為黑
當父節點為黑的時候，由于插入的子節點的顏色為紅，對三個約定沒有任何影響，因此不需要調整平衡。
(2)判斷父節點在祖父節點的位置
通過判斷父節點在祖父節點的位置，來定義叔叔節點的位置，以及之后的旋轉方向的判斷。
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//三種情況的處理
}
else
{
Node* uncle = grandfather->_left;
//三種情況的處理
}
首先需要使用大循環，這個循環是為情況1而準備的，情況2和3直接跳出循環即可，因為只有情況1對上層循環有影響。
下面我們以父節點在祖父節點的左側為例，右側同理。
(3)叔叔節點存在且為紅
解決方案：將父節點和叔叔節點設為黑，將祖父節點設為紅。然后將祖父節點作為新節點繼續向上平衡。如果祖父節點是根節點，那么需要再將其置為黑。
注意，這種情況和其他情況不同的是，需要將祖父節點作為新插入的節點繼續向上遍歷，這說明需要一個循環。而其他類型的情況直接break跳出這個循環即可。
//第一種情況
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
cur = grandfather;
parent = cur->_parent;
}
這種情況只需要控制顏色即可，但是要繼續向上循環。
(4)父節點為紅，叔叔不存在或存在且為黑，新插入的節點在父節點左側
解決方案：對祖父節點右旋操作，并將祖父節點置為紅，父節點置為黑。
關于旋轉的細節，我在AVL樹中有詳細的解釋：C++手撕AVL樹
//第二種情況，右單旋
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
(5)父節點為紅，叔叔不存在或存在且為黑，新插入的節點在父節點右側
解決方案：進行雙旋，即對父節點進行左單旋，祖父節點進行右單旋。將子節點置為黑，將祖父節點置為紅。
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
(6)最后置黑
每一次插入都對根節點置為黑操作，因為第一種情況可能導致根節點不是黑。同時對根節點置黑也并不違反三條規定。
3.測試代碼
當我們處理完父節點在祖父節點的左側后，處理父節點在祖父節點的右側。
全部處理之后，我們的插入代碼就完成了，接下來要對整個樹進行測試，即對三個約定來進行測試：
1.當根節點為紅時，返回false。
2.判斷一個節點和其父節點的顏色是否都為紅，若都為紅返回false。
3.以最左的一條路徑上的根節點數量為基準，通過遞歸遍歷每一條路徑上的根節點的數量，當每條路徑遍歷節點到空時，將兩者進行比較，如果最終結果不相等則返回false。
bool IsBalance()
{
if (_root && _root->_col == Red)
{
cout << "根節點不是黑色的" << endl;
return false;
}
int banchmark = 0;
//以最右邊一條路徑為基準
Node* left = _root;
while (left)
{
if (left->_col == Black)
{
++banchmark;
}
left = left->_left;
}
int blackNum = 0;
return _IsBalance(_root, banchmark, blackNum);
}
bool _IsBalance(Node* root, int banchmark, int blackNum)
{
if (root == nullptr)
{
if (banchmark != blackNum)
{
cout << "黑色根節點數目不相等" << endl;
return false;
}
return true;
}
if (root->_col == Red && root->_parent->_col == Red)
{
cout << "出現連續的紅色節點" << endl;
return false;
}
if (root->_col == Black)
{
++blackNum;
}
return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
}五、完整代碼
1.test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"RBtree.h"
#include<vector>
int main()
{
RBTree<int, int> t;
vector<int> v;
srand(time(0));
int N = 100000;
int count = 0;
for (int i = 0; i < N; i++)
{
v.push_back(rand());
}
for (auto e : v)
{
pair<int,int> kv(e, e);
t.insert(kv);
if (t.IsBalance())
{
cout << "insert" << e << endl;
count++;
cout << count << endl;
}
else
{
cout << e << "插入失敗" << endl;
cout << "不是平衡的" << endl;
break;
}
}
}2.RBTree.h
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Color
{
Red,
Black
};
template<class K,class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
Color _col;
RBTreeNode(pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(Red)
, _kv(kv)
{}
};
template<class K,class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
private:
Node* _root;
public:
RBTree()
:_root(nullptr)
{}
bool IsBalance()
{
if (_root && _root->_col == Red)
{
cout << "根節點不是黑色的" << endl;
return false;
}
int banchmark = 0;
//以最右邊一條路徑為基準
Node* left = _root;
while (left)
{
if (left->_col == Black)
{
++banchmark;
}
left = left->_left;
}
int blackNum = 0;
return _IsBalance(_root, banchmark, blackNum);
}
bool _IsBalance(Node* root, int banchmark, int blackNum)
{
if (root == nullptr)
{
if (banchmark != blackNum)
{
cout << "黑色根節點數目不相等" << endl;
return false;
}
return true;
}
if (root->_col == Red && root->_parent->_col == Red)
{
cout << "出現連續的紅色節點" << endl;
return false;
}
if (root->_col == Black)
{
++blackNum;
}
return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
}
//右單旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curL = cur->_left;
Node* curR = cur->_right;
Node* parentParent = parent->_parent;
parent->_left = curR;
if (curR)
curR->_parent = parent;
cur->_right = parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = cur;
cur->_parent = parentParent;
}
else if (parentParent->_right == parent)
{
parentParent->_right = cur;
cur->_parent = parentParent;
}
else
{
assert(false);
}
}
}
//左單旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curL = cur->_left;
Node* parentParent = parent->_parent;
parent->_right = curL;
if (curL)
curL->_parent = parent;
cur->_left = parent;
parent->_parent = cur;
if (parent == _root)
{
_root = cur;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = cur;
cur->_parent = parentParent;
}
else if (parentParent->_right == parent)
{
parentParent->_right = cur;
cur->_parent = parentParent;
}
else
{
assert(false);
}
}
}
bool insert(pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = Black;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
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 false;
}
}
cur = new Node(kv);
cur->_col= Red;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//第一種情況
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
cur = grandfather;
parent = cur->_parent;
}
else
{
//第二種情況，右單旋
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
//第三種情況，左右雙旋
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
_root->_col = Black;
}
else
{
Node* uncle = grandfather->_left;
//第一種情況
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
cur = grandfather;
parent = cur->_parent;
}
else
{
//第二種情況，左單旋
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
//第三種情況，右左雙旋
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
_root->_col = Black;
}
}
}
};
原文鏈接：https://blog.csdn.net/qq_51492202/article/details/126179804
相關推薦
- 2022-05-27 C++左值與右值,右值引用,移動語義與完美轉發詳解_C 語言
- 2022-09-25 TCP協議和UDP協議
- 2022-04-01 helm install Error: timed out waiting for the cond
- 2022-05-22 Python數據結構之隊列詳解_python
- 2022-06-06 解決Unity無限滾動復用列表的問題_C#教程
- 2022-05-15 C++的數據共享與保護你了解嗎_C 語言
- 2022-04-10 Mybatis if, set, where 動態sql和sql片段的使用
- 2022-07-10 css選擇器優先級問題
- 最近更新
-
- 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加速