C++?RBTree紅黑樹的性質(zhì)與實現(xiàn)
一、紅黑樹的概念
紅黑樹，是一種二叉搜索樹，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是平衡的 。（既最長路徑長度不超過最短路徑長度的 2 倍）
ps:樹的路徑是從根節(jié)點走到空節(jié)點（此處為NIL 節(jié)點）才算一條路徑
二、紅黑樹的性質(zhì)
- 每個結(jié)點不是紅色就是黑色
- 根結(jié)點是黑色的
- 如果一個結(jié)點是紅色的，則它的兩個孩子結(jié)點是黑色的（沒有連續(xù)的紅色結(jié)點）
- 對于每個結(jié)點，從該節(jié)點到其所有后代葉結(jié)點的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點
- 每個葉子結(jié)點都是黑色的（此處的葉子結(jié)點指的是空節(jié)點,NIL節(jié)點），如果是空樹，空節(jié)點也是黑色，符合第一個性質(zhì)
理解最長路徑長度不超過最短路徑長度的 2 倍：
根據(jù)第三個性質(zhì)：紅黑樹不會出現(xiàn)連續(xù)的紅色結(jié)點，根據(jù)第四個性質(zhì)：從每個結(jié)點到所有后代結(jié)點的路徑上包含相同數(shù)目的黑色結(jié)點。
極端場景：最短路徑上全黑，一條路徑黑色節(jié)點的數(shù)量，最長路徑上是一黑一紅相間的路徑
三、紅黑樹節(jié)點的定義
三叉鏈結(jié)構(gòu)，對比AVL數(shù)節(jié)點的定義，把平衡因子替換成節(jié)點顏色，采用枚舉的方式：
//結(jié)點顏色
enum Color
{
RED,
BLACK,
};
template<class K, class V >
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}
};
這里可以清楚的看到，構(gòu)造結(jié)點時默認(rèn)設(shè)置為紅色,問題來了：
如果插入的是黑色結(jié)點那就是不符合第四個性質(zhì)（路徑上均包含相同的黑色結(jié)點），此時我們必須要去進(jìn)行維護(hù)每條路徑的黑色結(jié)點
如果插入的是紅色結(jié)點那就是不符合第三個性質(zhì)（沒有出現(xiàn)連續(xù)的紅色結(jié)點），但是我們并不一定需要調(diào)整，如果根剛好為黑色，就不需要進(jìn)行調(diào)整。
所以如果插入為紅色結(jié)點，不一定會破壞結(jié)構(gòu)，但是如果插入黑色結(jié)點我們就必須去進(jìn)行維護(hù)了
四、紅黑樹的插入
紅黑樹插入的操作部分和AVL樹的插入一樣：
- 找到待插入位置
- 將待插入結(jié)點插入到樹中
- 調(diào)整：若插入結(jié)點的父結(jié)點是紅色的，我們就需要對紅黑樹進(jìn)行調(diào)整
前兩步大差不差
因為新節(jié)點的默認(rèn)顏色是紅色，因此：如果其雙親節(jié)點的顏色是黑色，沒有違反紅黑樹任何性質(zhì)，則不需要調(diào)整；但當(dāng)新插入節(jié)點的雙親節(jié)點顏色為紅色時，就違反了性質(zhì)三不能有連在一起的紅色節(jié)點，此時需要對紅黑樹分情況來討論
關(guān)鍵在于對紅黑樹進(jìn)行調(diào)整：為了能夠展示出各種情況，這里有一個基本的模型：
約定:cur為當(dāng)前節(jié)點，p為父節(jié)點，g為祖父節(jié)點，u為叔叔節(jié)點
情況一：cur為紅，p為紅，g為黑，u存在且為紅 :
cur為紅，p為紅，g為黑，u存在且為紅
關(guān)鍵看u結(jié)點，根結(jié)點的顏色為黑色，不能有連續(xù)的紅色結(jié)點，所以上面的情況已經(jīng)出現(xiàn)連續(xù)的紅色結(jié)點了，此時我們需要進(jìn)行調(diào)整：
把p結(jié)點改為黑色，同時把u結(jié)點也改為黑色（符合性質(zhì)四：每條路徑上的黑色節(jié)點數(shù)量相同），最后在把g結(jié)點改為紅色；如果g是子樹的話，g一定會有雙親，為了維持每條路徑上黑色節(jié)點的數(shù)量，g必須變紅，不然會多出一個黑色節(jié)點，在把g結(jié)點當(dāng)做cur結(jié)點繼續(xù)往上調(diào)整，當(dāng)g為根結(jié)點時，在把g置為黑色：
代碼實現(xiàn)：
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
//情況一：u存在且為紅
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else//其他情況
{
}
}
else//parent==grandfater->_right
{
Node* uncle = grandfater->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
cur = grandfater;
parent = cur->_parent;
}
else
{
}
}
}
_root->_col = BLACK;
情況二：cur為紅，p為紅，g為黑，u不存在/u為黑，gpc在同一側(cè)：
此時u的情況：
如果u結(jié)點不存在，則cur一定是新增結(jié)點，因為如果cur不是新增結(jié)點：則cur和p一定有一個節(jié)點時黑色，就不滿足每條路徑都有相同的黑色結(jié)點的性質(zhì)。
如果u結(jié)點存在，則其一定是黑色的，那么c節(jié)點原來的顏色一定是黑色，在其子樹調(diào)整過程中變?yōu)榱思t色
如果p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋轉(zhuǎn)；
如果p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋轉(zhuǎn)，
同時，p、g變色–p變黑，g變紅
以下情況：u不存在，cur為新增節(jié)點，進(jìn)行右單旋：
以下情況：u結(jié)點存在且為黑：
情況三: cur為紅，p為紅，g為黑，u不存在/u為黑，gpc不在同一側(cè):
這時候我們就需要進(jìn)行雙旋了：
p為g的左孩子，cur為p的右孩子，對p做左單旋轉(zhuǎn)；
p為g的右孩子，cur為p的左孩子，對p做右單旋轉(zhuǎn); 旋轉(zhuǎn)之后則轉(zhuǎn)換成了情況2，在繼續(xù)進(jìn)行調(diào)整即可
五、代碼實現(xiàn)
送上源碼：
#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
enum Color
{
RED,
BLACK,
};
template<class K, class V >
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
RBTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{}
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool Insert(const 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* grandfater = parent->_parent;
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
//情況一：u存在且為紅
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
//向上調(diào)整
cur = grandfater;
parent = cur->_parent;
}
else
{
//情況2
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
//情況3
else
{
// g
// p
// c
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else//parent==grandfater->_right
{
Node* uncle = grandfater->_left;
//情況1：u存在且為紅色
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
grandfater->_col = RED;
//向上調(diào)整
cur = grandfater;
parent = cur->_parent;
}
else
{
//情況2：u不存在/u存在為黑色
//g
// p
// c
if (cur == parent->_right)
{
RotateL(grandfater);
grandfater->_col = RED;
parent->_col = BLACK;
}
//情況3
// g
// p
// c
else
{
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
//根變黑
_root->_col = BLACK;
return true;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (ppNode == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
subL->_right = parent;
if (ppNode == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
void InOrder()
{
_InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
bool Check(Node*root,int blackNum,int ref)
{
if (root == nullptr)
{
//cout << blackNum << endl;
if (blackNum != ref)
{
cout << "違反規(guī)則：本條路徑的黑色結(jié)點的數(shù)量根最左路徑不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "違反規(guī)則：出現(xiàn)連續(xù)的紅色結(jié)點" << endl;
return false;
}
if (root->_col == BLACK)
{
++blackNum;
}
return Check(root->_left,blackNum,ref)
&& Check(root->_right,blackNum,ref);
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col != BLACK)
{
return false;
}
int ref = 0;
Node* left = _root;
while (left)
{
if (left->_col == BLACK)
{
++ref;
}
left = left->_left;
}
return Check(_root,0,ref);
}
private:
Node* _root = nullptr;
};
void TestRBTree1()
{
//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
RBTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.InOrder();
cout << t.IsBalance() << endl;
}
void TestRBTree2()
{
srand(time(0));
const size_t N = 100000;
RBTree<int, int> t;
for (size_t i = 0; i < N; i++)
{
size_t x = rand();
t.Insert(make_pair(x, x));
}
cout << t.IsBalance() << endl;
}到此這篇關(guān)于C++ RBTree紅黑樹的性質(zhì)與實現(xiàn)的文章就介紹到這了,更多相關(guān)C++ RBTree紅黑樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
我們可以用string方法定義字符串變量。以下是具體實現(xiàn)代碼。需要的朋友可以過來參考下，希望對大家有所幫助2013-10-10
單例模式（Singleton Pattern）是最簡單的設(shè)計模式之一。這種類型的設(shè)計模式屬于創(chuàng)建型模式，它提供了一種創(chuàng)建對象的最佳方式，這種模式涉及到一個單一的類，該類負(fù)責(zé)創(chuàng)建自己的對象，同時確保只有單個對象被創(chuàng)建2022-06-06
C++實現(xiàn)LeetCode(57.插入?yún)^(qū)間)
這篇文章主要介紹了C++實現(xiàn)LeetCode(57.插入?yún)^(qū)間),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C語言實現(xiàn)的位圖算法,主要包括了位圖算法的定義與應(yīng)用,對于C程序算法設(shè)計的學(xué)習(xí)有一定的借鑒價值,需要的朋友可以參考下2014-09-09
stringstream操縱string的方法總結(jié)
下面小編就為大家?guī)硪黄猻tringstream操縱string的方法總結(jié)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
VS2010 boost標(biāo)準(zhǔn)庫開發(fā)環(huán)境安裝教程
這篇文章主要為大家詳細(xì)介紹了VS2010 boost標(biāo)準(zhǔn)庫開發(fā)環(huán)境的安裝教程，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-04-04
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)快速排序算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-08-08
c++ TCHAR轉(zhuǎn)string導(dǎo)致中文缺失或亂碼問題及解決
這篇文章主要介紹了c++ TCHAR轉(zhuǎn)string導(dǎo)致中文缺失或亂碼問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要介紹了C語言之通訊錄的模擬實現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
這篇文章主要為大家詳細(xì)介紹了基于實現(xiàn)Qt秒表設(shè)計，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08