C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹的實(shí)現(xiàn)
一、什么是紅黑樹
紅黑樹在表意上就是一棵每個(gè)節(jié)點(diǎn)帶有顏色的二叉搜索樹，并通過(guò)對(duì)節(jié)點(diǎn)顏色的控制，使該二叉搜索樹達(dá)到盡量平衡的狀態(tài)。所謂盡量平衡的狀態(tài)就是：紅黑樹確保沒(méi)有一條路徑比其他路徑長(zhǎng)兩倍。
和AVL樹不同的是，AVL樹是一棵平衡樹，而紅黑樹可能平衡也可能不平衡(因?yàn)槭潜M量平衡的狀態(tài))
二、紅黑樹的約定
要實(shí)現(xiàn)一棵紅黑樹，即要紅黑樹確保沒(méi)有一條路徑比其他路徑長(zhǎng)兩倍。通過(guò)對(duì)節(jié)點(diǎn)顏色的約定來(lái)實(shí)現(xiàn)這一目標(biāo)。
1.根節(jié)點(diǎn)是黑色的。
2.如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子都是黑色的。
3.對(duì)于每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代節(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)量的黑色節(jié)點(diǎn)。
實(shí)現(xiàn)了這三條顏色規(guī)則的二叉搜索樹，即也實(shí)現(xiàn)了沒(méi)有一條路徑比其他路徑長(zhǎng)兩倍，即實(shí)現(xiàn)了一棵紅黑樹。
三、紅黑樹vsAVL
1、調(diào)整平衡的實(shí)現(xiàn)機(jī)制不同
紅黑樹根據(jù)節(jié)點(diǎn)顏色(同一父節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)，所有路徑上的黑色節(jié)點(diǎn)數(shù)目一樣)，一些約定和旋轉(zhuǎn)實(shí)現(xiàn)。
AVL根據(jù)樹的平衡因子(所有節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值不超過(guò)1)和旋轉(zhuǎn)決定。
2、紅黑樹的插入效率更高
紅黑樹是用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，紅黑樹并不追求“完全平衡”，它只要求部分地達(dá)到平衡要求，降低了對(duì)旋轉(zhuǎn)的要求，從而提高了性能
而AVL是嚴(yán)格平衡樹(高度平衡的二叉搜索樹)，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多。所以紅黑樹的插入效率更高
3、AVL查找效率高
如果你的應(yīng)用中，查詢的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除，那么選擇AVL樹，如果查詢和插入刪除次數(shù)幾乎差不多，應(yīng)選擇紅黑樹。即，有時(shí)僅為了排序（建立-遍歷-刪除），不查找或查找次數(shù)很少，R-B樹合算一些。
四、紅黑樹的實(shí)現(xiàn)
實(shí)現(xiàn)一棵紅黑樹，本質(zhì)是實(shí)現(xiàn)它的插入函數(shù)，使插入函數(shù)可以實(shí)現(xiàn)紅黑樹的顏色約定，它的實(shí)現(xiàn)分為兩步，即先找到插入的位置，再控制平衡。插入函數(shù)返回值設(shè)計(jì)為bool，插入成功返回true，失敗返回false。控制平衡時(shí)，需要關(guān)注四個(gè)節(jié)點(diǎn)，即新插入的節(jié)點(diǎn)，它的父節(jié)點(diǎn)，它的叔叔節(jié)點(diǎn)，它的祖父節(jié)點(diǎn)。
1.找到插入的位置
當(dāng)為第一個(gè)節(jié)點(diǎn)的時(shí)候，顏色設(shè)為黑，直接插入。
當(dāng)插入的不是第一個(gè)節(jié)點(diǎn)時(shí)，顏色設(shè)為紅，需要根據(jù)二叉搜索樹的性質(zhì)找到插入位置。并實(shí)現(xiàn)三叉鏈。
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)當(dāng)父節(jié)點(diǎn)為黑
當(dāng)父節(jié)點(diǎn)為黑的時(shí)候，由于插入的子節(jié)點(diǎn)的顏色為紅，對(duì)三個(gè)約定沒(méi)有任何影響，因此不需要調(diào)整平衡。
(2)判斷父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的位置
通過(guò)判斷父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的位置，來(lái)定義叔叔節(jié)點(diǎn)的位置，以及之后的旋轉(zhuǎn)方向的判斷。
while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//三種情況的處理
}
else
{
Node* uncle = grandfather->_left;
//三種情況的處理
}
首先需要使用大循環(huán)，這個(gè)循環(huán)是為情況1而準(zhǔn)備的，情況2和3直接跳出循環(huán)即可，因?yàn)橹挥星闆r1對(duì)上層循環(huán)有影響。
下面我們以父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的左側(cè)為例，右側(cè)同理。
(3)叔叔節(jié)點(diǎn)存在且為紅
解決方案：將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)設(shè)為黑，將祖父節(jié)點(diǎn)設(shè)為紅。然后將祖父節(jié)點(diǎn)作為新節(jié)點(diǎn)繼續(xù)向上平衡。如果祖父節(jié)點(diǎn)是根節(jié)點(diǎn)，那么需要再將其置為黑。
注意，這種情況和其他情況不同的是，需要將祖父節(jié)點(diǎn)作為新插入的節(jié)點(diǎn)繼續(xù)向上遍歷，這說(shuō)明需要一個(gè)循環(huán)。而其他類型的情況直接break跳出這個(gè)循環(huán)即可。
//第一種情況
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;
cur = grandfather;
parent = cur->_parent;
}
這種情況只需要控制顏色即可，但是要繼續(xù)向上循環(huán)。
(4)父節(jié)點(diǎn)為紅，叔叔不存在或存在且為黑，新插入的節(jié)點(diǎn)在父節(jié)點(diǎn)左側(cè)
解決方案：對(duì)祖父節(jié)點(diǎn)右旋操作，并將祖父節(jié)點(diǎn)置為紅，父節(jié)點(diǎn)置為黑。
關(guān)于旋轉(zhuǎn)的細(xì)節(jié)，我在AVL樹中有詳細(xì)的解釋：C++手撕AVL樹
//第二種情況，右單旋
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
(5)父節(jié)點(diǎn)為紅，叔叔不存在或存在且為黑，新插入的節(jié)點(diǎn)在父節(jié)點(diǎn)右側(cè)
解決方案：進(jìn)行雙旋，即對(duì)父節(jié)點(diǎn)進(jìn)行左單旋，祖父節(jié)點(diǎn)進(jìn)行右單旋。將子節(jié)點(diǎn)置為黑，將祖父節(jié)點(diǎn)置為紅。
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
(6)最后置黑
每一次插入都對(duì)根節(jié)點(diǎn)置為黑操作，因?yàn)榈谝环N情況可能導(dǎo)致根節(jié)點(diǎn)不是黑。同時(shí)對(duì)根節(jié)點(diǎn)置黑也并不違反三條規(guī)定。
3.測(cè)試代碼
當(dāng)我們處理完父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的左側(cè)后，處理父節(jié)點(diǎn)在祖父節(jié)點(diǎn)的右側(cè)。
全部處理之后，我們的插入代碼就完成了，接下來(lái)要對(duì)整個(gè)樹進(jìn)行測(cè)試，即對(duì)三個(gè)約定來(lái)進(jìn)行測(cè)試：
1.當(dāng)根節(jié)點(diǎn)為紅時(shí)，返回false。
2.判斷一個(gè)節(jié)點(diǎn)和其父節(jié)點(diǎn)的顏色是否都為紅，若都為紅返回false。
3.以最左的一條路徑上的根節(jié)點(diǎn)數(shù)量為基準(zhǔn)，通過(guò)遞歸遍歷每一條路徑上的根節(jié)點(diǎn)的數(shù)量，當(dāng)每條路徑遍歷節(jié)點(diǎn)到空時(shí)，將兩者進(jìn)行比較，如果最終結(jié)果不相等則返回false。
bool IsBalance()
{
if (_root && _root->_col == Red)
{
cout << "根節(jié)點(diǎn)不是黑色的" << endl;
return false;
}
int banchmark = 0;
//以最右邊一條路徑為基準(zhǔn)
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 << "黑色根節(jié)點(diǎn)數(shù)目不相等" << endl;
return false;
}
return true;
}
if (root->_col == Red && root->_parent->_col == Red)
{
cout << "出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)" << 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 << "根節(jié)點(diǎn)不是黑色的" << endl;
return false;
}
int banchmark = 0;
//以最右邊一條路徑為基準(zhǔn)
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 << "黑色根節(jié)點(diǎn)數(shù)目不相等" << endl;
return false;
}
return true;
}
if (root->_col == Red && root->_parent->_col == Red)
{
cout << "出現(xiàn)連續(xù)的紅色節(jié)點(diǎn)" << 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;
}
}
}
};
到此這篇關(guān)于C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++紅黑樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++ accumulate函數(shù)詳細(xì)介紹和具體案例
這篇文章主要介紹了C++ accumulate函數(shù)詳細(xì)介紹和具體案例，accumulate是numeric庫(kù)中的一個(gè)函數(shù)，主要用來(lái)對(duì)指定范圍內(nèi)元素求和，但也自行指定一些其他操作，如范圍內(nèi)所有元素相乘、相除等2022-08-08
C/C++?函數(shù)的存儲(chǔ)位置和占用空間詳解
Lambda函數(shù)的代碼部分在代碼段中，被捕獲的變量存儲(chǔ)在Lambda函數(shù)對(duì)象的內(nèi)部，這些變量的存儲(chǔ)位置取決于Lambda函數(shù)對(duì)象的存儲(chǔ)位置,這篇文章主要介紹了C/C++函數(shù)的存儲(chǔ)位置和占用空間,需要的朋友可以參考下2023-06-06
Qt音視頻開發(fā)之音頻播放QAudioOutput的實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)音頻播放QAudioOutput功能，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Qt開發(fā)有一定的幫助，需要的可以參考一下2023-03-03
基于C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的五子棋游戲
這篇文章主要為大家詳細(xì)介紹了基于C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
Libevent?是一個(gè)用C語(yǔ)言編寫的、輕量級(jí)的開源高性能事件通知庫(kù),主要有以下幾個(gè)亮點(diǎn)：事件驅(qū)動(dòng)（?event-driven）,高性能;輕量級(jí),專注于網(wǎng)絡(luò),這篇文章主要介紹了Libevent的使用及reactor模型,需要的朋友可以參考下2024-03-03
C語(yǔ)言實(shí)現(xiàn)BMP圖像開運(yùn)算處理
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)BMP圖像開運(yùn)算處理，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
C語(yǔ)言實(shí)現(xiàn)三子棋游戲（初級(jí)版）
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)三子棋游戲初級(jí)版，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-09-09
JSON是一種對(duì)源自Javascript的對(duì)象數(shù)據(jù)進(jìn)行編碼的格式,但現(xiàn)在被廣泛用作互聯(lián)網(wǎng)上的數(shù)據(jù)交換格式,本文主要介紹了Qt使用Json的項(xiàng)目實(shí)踐,詳細(xì)的介紹了主要使用的類以及Json實(shí)戰(zhàn),感興趣的可以了解一下2023-09-09
QT自定義QTextEdit實(shí)現(xiàn)大數(shù)據(jù)的實(shí)時(shí)刷新顯示功能實(shí)例
TextEdit是我們常用的Qt控件,用來(lái)顯示文本信息,下面這篇文章主要給大家介紹了關(guān)于QT自定義QTextEdit實(shí)現(xiàn)大數(shù)據(jù)的實(shí)時(shí)刷新顯示功能的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-05-05
C語(yǔ)言中的時(shí)間函數(shù)clock()和time()你都了解嗎
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言中的時(shí)間函數(shù)clock()和time()，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02