C++超詳細(xì)分析紅黑樹
更新時(shí)間：2022年06月10日 11:02:06 作者：ymz123_
這一篇我要跟大家介紹二叉搜索樹中的另一顆樹——紅黑樹，它主要是通過控制顏色來控制自身的平衡，但它的平衡沒有AVL樹的平衡那么嚴(yán)格
紅黑樹
紅黑樹的概念
紅黑樹的概念 紅黑樹，是一種二叉搜索樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。 通過對(duì)任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍，因而是接近平衡的。
紅黑樹和AVL樹都是高效的平衡二叉樹，增刪改查的時(shí)間復(fù)雜度都是O()，紅黑樹不追求絕對(duì)平衡，其只需保證最長(zhǎng)路徑不超過最短路徑的2倍，相對(duì)而言，降低了插入和旋轉(zhuǎn)的次數(shù)，所以在經(jīng)常進(jìn)行增刪的結(jié)構(gòu)中性能比AVL樹更優(yōu)，而且紅黑樹實(shí)現(xiàn)比較簡(jiǎn)單，所以實(shí)際運(yùn)用中紅黑樹更多。
紅黑樹的性質(zhì)
- 每個(gè)結(jié)點(diǎn)不是紅色就是黑色
- 根節(jié)點(diǎn)是黑色的
- 如果一個(gè)結(jié)點(diǎn)是紅色的，則它的兩個(gè)孩子結(jié)點(diǎn)是黑色的
- 對(duì)于每個(gè)結(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)
- 每個(gè)葉子結(jié)點(diǎn)都是黑色的（此處的葉子節(jié)點(diǎn)指的是空結(jié)點(diǎn)，如上圖路徑數(shù)為11條）
紅黑樹結(jié)點(diǎn)的定義
enum Color {
BLACK,
RED
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;
T _data;
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col（RED)
，_data(data)
{}
};
紅黑樹的插入操作
約定：cur為當(dāng)前節(jié)點(diǎn)，p為父節(jié)點(diǎn)，g為祖父節(jié)點(diǎn)，u為叔叔節(jié)點(diǎn)
情況一
- 情況一：cur為紅，p為紅，g為黑，u存在且為紅注意：此處看到的樹，可能是一棵完整的樹，也可能是一棵子樹
- 解決方式：將p，u改為黑，g改為紅，然后把g當(dāng)成cur，繼續(xù)向上調(diào)整
如果g是根節(jié)點(diǎn)，調(diào)整完成后，需要將g改為黑色
如果g是子樹，g一定有雙親，且g的雙親如果是紅色，需要繼續(xù)向上調(diào)整。
情況二
情況二：cur為紅，p為紅，g為黑，u不存在/u為黑
解決方法：p為g的左孩子，cur為p的左孩子，則進(jìn)行右單旋；p為g的右孩子，cur為p的右孩子，則進(jìn)行左單旋。
p變黑，g變紅。
1.如果u節(jié)點(diǎn)不存在，則cur一定是新插入節(jié)點(diǎn)，因?yàn)槿绻鹀ur不是新插入節(jié)點(diǎn)，則cur和p一定有一個(gè)節(jié)點(diǎn)的顏色是黑色，就不滿足性質(zhì)4：每條路徑黑色節(jié)點(diǎn)個(gè)數(shù)相同。
2.如果u節(jié)點(diǎn)存在，則其一定是黑色的，cur一定不是新增節(jié)點(diǎn)，那么cur節(jié)點(diǎn)原來的顏色一定是黑色的，是作為子樹的祖父，由第一種情況變化過來的
情況三
情況三：cur為紅，p為紅，g為黑，u不存在/u為黑（折線型）
p為g的左孩子，cur為p的右孩子，則針對(duì)p做左單旋轉(zhuǎn)；
p為g的右孩子，cur為p的左孩子，則針對(duì)p做右單旋轉(zhuǎn)。
即轉(zhuǎn)換為了情況二。再對(duì)g做對(duì)于旋轉(zhuǎn)。即進(jìn)行雙旋轉(zhuǎn)。
// T->K set
// T->pair<const K, V> map
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin();
iterator end();
RBTree()
:_root(nullptr)
{}
// 拷貝構(gòu)造和賦值重載
// 析構(gòu)
Node* Find(const K& key);
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur), false);
}
}
// 新增節(jié)點(diǎn)，顏色是紅色，可能破壞規(guī)則3，產(chǎn)生連續(xù)紅色節(jié)點(diǎn)
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
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;
// 情況一：uncle存在且為紅，進(jìn)行變色處理，并繼續(xù)往上更新處理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} // 情況二+三：uncle不存在，或者存在且為黑，需要旋轉(zhuǎn)+變色處理
else
{
// 情況二：?jiǎn)涡?變色
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else // 情況三：雙旋 + 變色
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // (parent == grandfather->_right)
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
void RotateR(Node* parent);
void RotateL(Node* parent);
private:
Node* _root;
};
紅黑樹的驗(yàn)證
紅黑樹的檢測(cè)分為兩步：
- 檢測(cè)其是否滿足二叉搜索樹(中序遍歷是否為有序序列)
- 檢測(cè)其是否滿足紅黑樹的性質(zhì)
此處用未改造過的紅黑樹
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
pair<K, V> _kv;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
, _kv(kv)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree()
:_root(nullptr)
{}
bool Insert(const pair<K, V>& kv);
void RotateR(Node* parent);
void RotateL(Node* parent);
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
bool CheckRED_RED(Node* cur)
{
if (cur == nullptr)
{
return true;
}
if (cur->_col == RED && cur->_parent->_col == RED)
{
cout << "違反規(guī)則三，存在連續(xù)的紅色節(jié)點(diǎn)" << endl;
return false;
}
return CheckRED_RED(cur->_left)
&& CheckRED_RED(cur->_right);
}
// 檢查每條路徑黑色節(jié)點(diǎn)的數(shù)量
bool CheckBlackNum(Node* cur, int blackNum, int benchmark) {
if (cur == nullptr) {
if (blackNum != benchmark){
cout << "違反規(guī)則四：黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;
return false;}
return true;
}
if (cur->_col == BLACK)
++blackNum;
return CheckBlackNum(cur->_left, blackNum, benchmark)
&& CheckBlackNum(cur->_right, blackNum, benchmark);
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout << "根節(jié)點(diǎn)是紅色，違反規(guī)則二" << endl;
return false;
}
// 算出最左路徑的黑色節(jié)點(diǎn)的數(shù)量作為基準(zhǔn)值
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++benchmark;
}
cur = cur->_left;
}
int blackNum = 0;
return CheckRED_RED(_root) && CheckBlackNum(_root, blackNum, benchmark);
}
private:
Node* _root;
};
void TestRBTree1()
{
const int n = 1000000;
vector<int> a;
a.reserve(n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a.push_back(rand());
}
RBTree<int, int> t1;
for (auto e : a)
{
t1.Insert(make_pair(e, e));
}
cout << t1.IsBalance() << endl;
//t1.InOrder();
}
用紅黑樹封裝map、set
紅黑樹的迭代器
begin()與end()
begin()可以放在紅黑樹中最小節(jié)點(diǎn)(即最左側(cè)節(jié)點(diǎn))的位置
end()放在最大節(jié)點(diǎn)(最右側(cè)節(jié)點(diǎn))的下一個(gè)位置
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
//return left
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
操作符重載
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
RBTreeIterator(Node* node = nullptr)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator--()
{
// 跟++基本是反過來
return *this;
}
Self& operator++()
{
if (_node->_right)
{
// 右子樹中序第一個(gè)節(jié)點(diǎn)，也就是右子樹的最左節(jié)點(diǎn)
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else
{
// 當(dāng)前子樹已經(jīng)訪問完了，要去找祖先訪問，沿著到根節(jié)點(diǎn)的路徑往上走，
// 找孩子是父親左的那個(gè)父親節(jié)點(diǎn)
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
封裝map
#pragma once
#include "RBTree.h"
namespace MyMap
{
template < class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
void test_map()
{
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("debug", "找蟲子"));
dict.insert(make_pair("set", "集合"));
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
}
封裝set
#pragma once
#include "RBTree.h"
namespace MySet
{
template < class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
void test_set()
{
set<int> s;
s.insert(1);
s.insert(3);
s.insert(7);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(2);
s.insert(23);
s.insert(-2);
s.insert(-9);
s.insert(30);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
}
到此這篇關(guān)于C++超詳細(xì)分析紅黑樹的文章就介紹到這了,更多相關(guān)C++ 紅黑樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- C++詳細(xì)實(shí)現(xiàn)紅黑樹流程詳解
- C++實(shí)現(xiàn)紅黑樹應(yīng)用實(shí)例代碼
- C++?STL容器詳解之紅黑樹部分模擬實(shí)現(xiàn)
- C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹的實(shí)現(xiàn)
- C++數(shù)據(jù)結(jié)構(gòu)紅黑樹全面分析
- C++?RBTree紅黑樹的性質(zhì)與實(shí)現(xiàn)
- C++使用一棵紅黑樹同時(shí)封裝出map和set實(shí)例代碼
- C++紅黑樹應(yīng)用之手搓set和map
- C++實(shí)現(xiàn)紅黑樹核心插入實(shí)例代碼
相關(guān)文章
這篇文章主要介紹了c語言求階乘精確值示例,需要的朋友可以參考下2014-03-03
C++設(shè)計(jì)模式之簡(jiǎn)單工廠模式實(shí)例
這篇文章主要介紹了C++設(shè)計(jì)模式之簡(jiǎn)單工廠模式實(shí)例,工廠模式有一種非常形象的描述,建立對(duì)象的類就如一個(gè)工廠,而需要被建立的對(duì)象就是一個(gè)個(gè)產(chǎn)品,需要的朋友可以參考下2014-09-09
C++編寫DLL動(dòng)態(tài)鏈接庫(kù)的步驟與實(shí)現(xiàn)方法
這篇文章主要介紹了C++編寫DLL動(dòng)態(tài)鏈接庫(kù)的步驟與實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了C++導(dǎo)出類文件及生成與調(diào)用DLL動(dòng)態(tài)連接庫(kù)的相關(guān)操作技巧,需要的朋友可以參考下2016-08-08
這篇文章主要給大家介紹了關(guān)于利用C語言玩轉(zhuǎn)魔方陣的相關(guān)資料,文中詳細(xì)介紹了關(guān)于奇數(shù)魔方陣和4N 魔方陣的實(shí)現(xiàn)方法，通過示例代碼讓大家更好的參考學(xué)習(xí)，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-11-11
經(jīng)典的推箱子是一個(gè)的古老游戲，目的是在訓(xùn)練你的邏輯思考能力。在一個(gè)狹小的倉(cāng)庫(kù)中，要求把木箱放到指定的位置，稍不小心就會(huì)出現(xiàn)箱子無法移動(dòng)或者通道被堵住的情況，所以需要巧妙的利用有限的空間和通道，合理安排移動(dòng)的次序和位置，才能順利的完成任務(wù)2021-11-11
基于C語言實(shí)現(xiàn)點(diǎn)菜系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了基于C語言實(shí)現(xiàn)點(diǎn)菜系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-11-11
C語言非遞歸算法解決快速排序與歸并排序產(chǎn)生的棧溢出
上期我們講完了排序算法下，不知道小伙伴們有沒有發(fā)現(xiàn)一個(gè)問題，快速排序和歸并排序我們都是用遞歸來實(shí)現(xiàn)的，可能有小伙伴會(huì)問，如果說數(shù)據(jù)量很多話，棧區(qū)空間會(huì)不會(huì)不夠用呢？這期我們就來解決使用遞歸實(shí)現(xiàn)的排序?qū)е聴Ｒ绯鋈绾谓鉀Q2022-04-04
C++調(diào)用C函數(shù)報(bào)錯(cuò)無法解析的外部命令/無法解析的外部符號(hào)問題
這篇文章主要介紹了C++調(diào)用C函數(shù)報(bào)錯(cuò)無法解析的外部命令/無法解析的外部符號(hào)問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
詳解C語言中typedef和#define的用法與區(qū)別
這篇文章主要給大家介紹了關(guān)于C語言中typedef和#define的的用法、區(qū)別，以及陷阱。文中通過示例進(jìn)行了詳細(xì)講解，感興趣的小伙伴可以了解一下2022-07-07
C++小練習(xí)之高性能實(shí)現(xiàn)字符串分割
字符串分割是日常工作中比較常見的基礎(chǔ)函數(shù),通常大家會(huì)使用現(xiàn)成的基礎(chǔ)庫(kù),基礎(chǔ)庫(kù)的性能是否是最佳的,本文主要和大家探討一下如何最大限度的提升字符串分割的性能,希望對(duì)大家有所幫助2023-10-10