什么是紅黑樹？本篇文章讓你徹底理解！
1. 紅黑樹的概念
紅黑樹，是一種二叉搜索樹，但在每個結(jié)點上增加一個存儲位表示結(jié)點的顏色，可以是Red或Black。 通過對任何一條從根到葉子的路徑上各個結(jié)點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。
2. 紅黑樹的性質(zhì)
2.1. 每個結(jié)點不是紅色就是黑色
2.2. 根節(jié)點是黑色的
2.3. 如果一個節(jié)點是紅色的，則它的兩個孩子結(jié)點是黑色的（不會出現(xiàn)連在一起的紅色節(jié)點）
2.4. 對于每個結(jié)點，從該結(jié)點到其所有后代葉結(jié)點的簡單路徑上，均包含相同數(shù)目的黑色結(jié)點（在計算一條路徑中黑色節(jié)點個數(shù)的時候要帶上葉子節(jié)點，因為葉子節(jié)點也是黑色的，也就是空節(jié)點）。
2.5. 每個葉子結(jié)點都是黑色的(此處的葉子結(jié)點指的是空結(jié)點)（為了保證空樹也是紅黑樹）
2.6.紅黑樹確保沒有一條路徑會比其他路徑長出倆倍（紅黑樹前面的性質(zhì)保證了當(dāng)前的性質(zhì)）
3. 紅黑樹的實現(xiàn)
3.1. 帶頭節(jié)點的紅黑樹
這里我們將紅黑樹的實現(xiàn)給為帶頭的紅黑樹，因為紅黑樹是map和set的底層數(shù)據(jù)結(jié)構(gòu)這里我們實現(xiàn)出來紅黑樹就可以直接用當(dāng)前我們實現(xiàn)的帶頭紅黑樹來實現(xiàn)map和set至于頭節(jié)點的給出是為了方便于map和set的遍歷，在STL中我們區(qū)間給出都是左閉右開區(qū)間的，既然紅黑樹作為map和set的底層數(shù)據(jù)結(jié)構(gòu)那么我們就一定有位置要來放map和set的迭代器，那么就可以將begin位置的迭代器放在head的左，end位置的迭代器可以放在head位置。這里我們將紅黑樹頭節(jié)點的顏色給為紅色。
3.2. 紅黑樹的節(jié)點
3.3. 紅黑樹插入節(jié)點的分析（實現(xiàn)紅黑樹最最最關(guān)鍵的一步）
可以看到我們上面在紅黑樹節(jié)點的構(gòu)造的時候?qū)⒐?jié)點的默認顏色給為紅色，那么我們在插入節(jié)點的時候就要特別考慮性質(zhì)3：不可以有兩個紅色節(jié)點連在一起。這里我們可以一共可以分為兩大類，一類將節(jié)點插入當(dāng)前紅黑樹的左子樹中，另一類就是將節(jié)點插入紅黑樹的右子樹當(dāng)中。
第一大類（將節(jié)點插入紅黑樹的左子樹中）
第一種情況（叔叔節(jié)點存在而且為紅色，這里將節(jié)點插入紅黑樹的內(nèi)測還是內(nèi)測處理方式是一樣的）
1.我們插入節(jié)點的parent節(jié)點為黑色：那么這種情況是不需要調(diào)整的。
2.我們插入節(jié)點的parent節(jié)點為紅色，而且插入節(jié)點的叔叔節(jié)點也存在而且為紅色的，那么當(dāng)前節(jié)點插入之后就違反了紅黑樹的性質(zhì)3，就需要對當(dāng)前樹進行調(diào)整。這里解決的時候我們就將當(dāng)前parent節(jié)點和叔叔節(jié)點u的顏色變?yōu)楹谏?/p>
為什么要這樣做呢？
答案：這里我們將cur節(jié)點插入之后要解決當(dāng)前parent和cur顏色都為紅色的問題，那么只能將cur和parnet其中一個節(jié)點的顏色變?yōu)楹谏?，但是肯定不能將cur節(jié)點變?yōu)楹谏?，因為這樣在包含cur的路徑中就多一個黑色節(jié)點，那么我們就要將除包含cur之外的路徑中的黑色節(jié)點全部都減少一個，又因為此時cur是新插入的節(jié)點如果將cur顏色變?yōu)楹谏敲创藭r就只有一條路徑黑色節(jié)點個數(shù)+1，如果要調(diào)整的話，其他所有節(jié)點中黑色節(jié)點個數(shù)都要減少一個這樣肯定是不行的，那么我們只能將parent節(jié)點的顏色變?yōu)楹谏敲串?dāng)parent節(jié)點變?yōu)楹谏笪覀兛梢钥吹皆诎琾arent的路徑中黑色節(jié)點增加，但是包含parent節(jié)點的路徑一定包含parent的雙親節(jié)點也就是g節(jié)點那么我們將雙親節(jié)點g顏色改為紅色，那么不就將包含parent路徑的黑色節(jié)點個數(shù)減少一個了嗎。然后我們發(fā)現(xiàn)又出現(xiàn)新的問題了，就是原本包含u節(jié)點的路徑因為g節(jié)點變?yōu)榱思t色那么包含u節(jié)點的路徑中少了一個黑色節(jié)點（因為包含u節(jié)點的路徑一定包含g節(jié)點）那么我們此時只要將u節(jié)點的顏色變?yōu)楹谏纯伞?/p>
上面將parent和u的節(jié)點更新為紅色之后，我們還要考慮g節(jié)點讓我們更新為紅色之后那它的雙親節(jié)點是否存在，是否是紅色節(jié)點：
相關(guān)視頻推薦
5種紅黑樹的場景，從Linux內(nèi)核談到Nginx源碼，聽完醍醐灌頂
5種紅黑樹的用途，從應(yīng)用到內(nèi)核場景的優(yōu)缺點
如果g的雙親不存在：
那么此時g就是根節(jié)點那么我們此時需要將g顏色更新為黑色，因為紅黑樹的根節(jié)點必須是黑色的。
如果g的雙親存在：
分為兩種情況：1、g的雙親為黑色那么調(diào)整結(jié)束直接退出。2、如果g的雙親為紅色（而且g的叔叔為紅色，這里如果g的叔叔為黑色我們下面會討論）那么我們更新cur和parent繼續(xù)當(dāng)前的調(diào)整過程。
我們可以總結(jié)一下我們的第一種情況：
第二種情況（叔叔節(jié)點存在而且一定為黑色或者叔叔節(jié)點不存在）
當(dāng)前cur節(jié)點是新插入節(jié)點，那么叔叔節(jié)點一定是不存在的
當(dāng)前cur不是新插入節(jié)點，那么就和我們第一種情況，我們更新完祖父節(jié)點后祖父節(jié)點還有叔叔節(jié)點的情況這時叔叔節(jié)點一定是黑色的，其實下面這種情況的出現(xiàn)就是為了解決上面第一種情況：更新完祖父節(jié)點之后祖父節(jié)點還有叔叔節(jié)點且叔叔節(jié)點為黑色。
那么我們?nèi)绾谓鉀Q當(dāng)前場景呢？
我們這里一共給出三步：
1.將parent節(jié)點改為黑色
2.將g節(jié)點改為紅色
3.將g節(jié)點右單旋
當(dāng)叔叔節(jié)點不存在也是一樣的做法
我們總結(jié)一下第二種情況：第二種情況其實就是對第一種情況其中的一種情況的分析解決。
第三種情況：第三種情況其實就是對第二種情況的變種，cur在parent的右側(cè)。
如果你可以堅持看到這里，恭喜你你已經(jīng)理解了手撕紅黑樹中基本最難的地方了，馬上就能撕碎紅黑樹！??！
情況三的解決方案：（其實情況三就是轉(zhuǎn)化為情況二來解決的）
至此我們就將紅黑樹插入的第一大類看完了，接下來就是第二大類基本就和我們的第一大類一樣，不同的地方就是第二大類將節(jié)點插入到紅黑樹的右子樹。
第二大類（將節(jié)點插入紅黑樹的右子樹中）
第一種情況：插入節(jié)點的parent節(jié)點為紅色而且叔叔節(jié)點存在為紅色（這里將節(jié)點插入紅黑樹的內(nèi)測還是內(nèi)測處理方式是一樣的）
那么我們和第一類中一樣也分為g有雙親節(jié)點（g的叔叔為紅色，g的叔叔為黑色兩種情況）和沒有雙親節(jié)點。
g沒有雙親節(jié)點：沒有雙親節(jié)點我們將g顏色更新為紅色直接返回即可。
g的雙親節(jié)點如果存在:那么我們就又分為兩種情況一種是雙親節(jié)點為黑色節(jié)點那么調(diào)整結(jié)束滿足紅黑樹性質(zhì)，另一種雙親節(jié)點為紅色那么，就又分為兩種情況：一種是當(dāng)前叔叔節(jié)點為紅色那么我們重復(fù)當(dāng)前的調(diào)整步驟，另一種就是我們下面情況二要討論的叔叔節(jié)點為黑色。
第二情況：叔叔節(jié)點存在但顏色一定是黑色||叔叔節(jié)點不存在
如果叔叔節(jié)點u為黑色節(jié)點當(dāng)前節(jié)點一定不是新插入節(jié)點。
那么就是我們遺留的第一種情況中未處理的情況就是下面這種情況：
由于與第一大類中第二種情況類似我們這里直接將解決方式給出，這里的叔叔節(jié)點不存在也是同樣的做法
第三種情況：叔叔節(jié)點存在但顏色一定是黑色||將節(jié)點插入內(nèi)側(cè)
4. 紅黑樹模擬實現(xiàn)
看到這里恭喜你，你已經(jīng)徹底掌握了紅黑樹的插入，接下來你可以動手試一下紅黑樹的模擬實現(xiàn)，這里我也給出紅黑樹的模擬實現(xiàn)代碼可以作為參考。
#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
// 節(jié)點的顏色
//我們可以使用 #define 定義常量，為什么非要使用枚舉？ 枚舉的優(yōu)點：
//1. 增加代碼的可讀性和可維護性
//2. 和#define定義的標識符比較枚舉有類型檢查，更加嚴謹。
//3. 防止了命名污染（封裝）
//4. 便于調(diào)試
//5. 使用方便，一次可以定義多個常量
//6. 這些可能取值都是有值的，默認從0開始，一次遞增1，當(dāng)然在定義的時候也可以賦初值。
enum Color{ RED, BLACK };
// 紅黑樹節(jié)點的定義
template<class ValueType>
struct RBTreeNode
{
RBTreeNode(const ValueType& data = ValueType(), Color color = RED)
//這里構(gòu)造節(jié)點的時候顏色默認給為紅色因為如果給為黑色就有可能會破壞當(dāng)前紅黑樹的性質(zhì)，導(dǎo)致每條路徑的黑色節(jié)點個數(shù)不同
: _Left(nullptr), _Right(nullptr), _Parent(nullptr)
, _data(data), _color(color)
{}
RBTreeNode<ValueType>* _Left; // 節(jié)點的左孩子
RBTreeNode<ValueType>* _Right; // 節(jié)點的右孩子
RBTreeNode<ValueType>* _Parent; // 節(jié)點的雙親(紅黑樹需要旋轉(zhuǎn)，為了實現(xiàn)簡單給出該字段)
ValueType _data; // 節(jié)點的值域
Color _color; // 節(jié)點的顏色
};
//紅黑樹迭代器：
template<class T, class Ref, class Ptr>
struct RBTree_iterator
{
typedef RBTreeNode<T> Node;
typedef RBTree_iterator<T, Ref, Ptr> self;
//構(gòu)造函數(shù)就將紅黑樹的節(jié)點指針傳入進來：
RBTree_iterator(Node* node = nullptr)
:_pnode(node)
{}
//迭代器解引用：
Ref operator*()
{
return _pnode->_data;
}
Ptr operator->()
{
return (&operator*());
}
//迭代器加加:前置加加
self operator++()
{
Increament();
return *this;
}
self operator++(int)
{
self temp = *this;
Increament();
return temp;
}
self operator--()
{
Decreament();
return *this;
}
self operator--(int)
{
self temp = *this;
Decreament();
return temp;
}
//將當(dāng)前迭代器指針的值放到后面大的值上
void Increament()
{
//如果當(dāng)前迭代器存在右子樹的時候我們將_pnode更新到右子樹
if (_pnode->_Right)
{
_pnode = _pnode->_Right;
//去右子樹中找最小的節(jié)點：
while (_pnode->_Left)
{
_pnode = _pnode->_Left;
}
}
else
{
Node* parent = _pnode->_Parent;
while (parent->_Right == _pnode)
{
_pnode = parent;
parent = _pnode->_Parent;
}
///----------------------------->>>>>>>>>>>一定要注意下面的情況當(dāng)紅黑樹沒有右子樹，那么當(dāng)前的head節(jié)點的右就指向
//紅黑樹的根那么此時如果將_pnode放在parent處那么就相當(dāng)于將while循環(huán)中的做了無用功。
if (_pnode->_Right != parent)
{
_pnode = parent;
}
}
}
void Decreament()
{
if (_pnode->_Parent->_Parent == _pnode&&_pnode->_color == RED)
{//當(dāng)前節(jié)點是head節(jié)點的時候那么我們就要找到當(dāng)最右邊節(jié)點也就是最大節(jié)點，而判斷當(dāng)前節(jié)點是否是最大的節(jié)點的時候
//不可只有一個_pnode->_Parent->_Parent因為根節(jié)點也滿足這個條件，因為我們將紅黑樹的head節(jié)點設(shè)為紅色所以我們加上_color==RED
_pnode = _pnode->_Right;
}
//如果當(dāng)前的pnode的左子樹存在那么我們就將節(jié)點放在左子樹
else if (_pnode->_Left)
{
_pnode = _pnode->_Left;
while (_pnode->_Right)
{
_pnode = _pnode->_Right;
}
}
else
{
Node* parent = _pnode->_Parent;
//這里如果_pnode到了begin的位置就不可以再減了
while (_pnode == parent->_Left)
{
_pnode = parent;
parent = _pnode->_Parent;
}
_pnode = parent;
}
}
bool operator==(const self &s)const
{
return _pnode == s._pnode;
}
bool operator!=(const self &s)const
{
return _pnode != s._pnode;
}
Node* _pnode;
};
template<class T,class Keyofvalue>
class RBtree{
typedef RBTreeNode<T> Node;
public:
typedef RBTree_iterator<T, T&, T*> RBiterator;
public:
RBtree()
:_head(new Node()), _size(0)
{
_head->_Left = _head;
_head->_Right = _head;
}
pair<RBiterator,bool> insert(const T &val)//插入節(jié)點
{
Keyofvalue key;
//先按照二叉搜索樹的方式插入
Node* new_node=nullptr;
Node*& _root = get_root();
if (_root == nullptr)
{//為空樹
_root = new Node(val, RED);
_root->_Parent = _head;
new_node = _root;
//_head->_Parent = _root;
}
else
{//樹非空
Node* cur = _root;
Node* parent = _head;
while (cur)
{
parent = cur;
if (key(val) < key(cur->_data))
{
cur = cur->_Left;
}
else if (key(val)>key(cur->_data))
{
cur = cur->_Right;
}
else
{//我們這里不允許插入相同值域的節(jié)點
return make_pair(RBiterator(cur),false);
}
}
cur = new Node(val);
new_node = cur;
if (key(val) < key(parent->_data))
{
parent->_Left = cur;
}
else
{
parent->_Right = cur;
}
cur->_Parent = parent;
//插入成功之后我們調(diào)整當(dāng)前紅黑樹的節(jié)點：
//這里我們在插入紅黑樹中調(diào)整的時候只有當(dāng)?shù)谝恢星闆r才繼續(xù)向上更新節(jié)點，那么我們只要考慮第一中情況的終止條件即可
//第一中情況中如果parent為紅色節(jié)點那么當(dāng)前節(jié)點就需要繼續(xù)向上更新，但是我們將head節(jié)點也設(shè)為紅色那么當(dāng)我們parent
//節(jié)點更新到head節(jié)點那么當(dāng)前也就不更新了
while (parent != _head&&parent->_color == RED)
{
//插入節(jié)點雙親為黑色：
if (parent->_color == BLACK)
{
break;
}
else
{//插入節(jié)點雙親為紅色
Node* grandparent = parent->_Parent;//這里如果雙親的節(jié)點是紅色那么雙親一定是有雙親節(jié)點的
if (parent == grandparent->_Left)
{//第一大類插入節(jié)點在紅黑樹的左子樹：
Node* uncle = grandparent->_Right;//當(dāng)前節(jié)點的叔叔節(jié)點
if (uncle&&uncle->_color == RED)
{//第一種情況：叔叔節(jié)點存在而且為紅色：
parent->_color = BLACK;
uncle->_color = BLACK;
grandparent->_color = RED;
cur = grandparent;
parent = cur->_Parent;
}
//第二三種情況：
else
{
//因為我們要將第三種情況轉(zhuǎn)化為第二種情況處理所以我們先寫第三種情況：cur插在內(nèi)側(cè)
if (cur == parent->_Right)
{
rotate_left(parent);
std::swap(parent, cur);
}
//第二種情況：先將parent和grandparent顏色互換然后右旋
parent->_color = BLACK;
grandparent->_color = RED;
rotate_right(grandparent);
}
}
else
{//第二大類插入節(jié)點在紅黑樹的右子樹：
Node* uncle = grandparent->_Left;//當(dāng)前節(jié)點的叔叔節(jié)點
if (uncle&&uncle->_color == RED)
{//第一種情況：叔叔節(jié)點存在而且為紅色：
parent->_color = BLACK;
uncle->_color = BLACK;
grandparent->_color = RED;
cur = grandparent;
parent = cur->_Parent;
}
//第二三種情況：
else
{
//因為我們要將第三種情況轉(zhuǎn)化為第二種情況處理所以我們先寫第三種情況：cur插在內(nèi)側(cè)
if (cur == parent->_Left)
{
rotate_right(parent);
std::swap(parent, cur);
}
//第二種情況：先將parent和grandparent顏色互換然后右旋
parent->_color = BLACK;
grandparent->_color = RED;
rotate_left(grandparent);
}
}
}
}
}
_root->_color = BLACK;
_head->_Left = get_mostleftnode();
_head->_Right = get_mostrightnode();
return make_pair(RBiterator(new_node), true);
}
//這里的銷毀節(jié)點一定要傳&因為因為下面要修改root=nullptr的時候要將指針所指向的地址修改為nullptr不然如果后面再調(diào)用destroy的時候
//其實root所指向的地址并沒有指向nullptr所以就有可能出錯。
void Destroy(Node* &root)
{
if (root)
{
Destroy(root->_Left);
Destroy(root->_Right);
delete root;
root = nullptr;
}
}
void Clear()
{
Destroy(get_root());
_size = 0;
}
~RBtree()
{
Destroy(get_root());
delete _head;
}
//查找方法
RBiterator Find(T value)
{
Keyofvalue key;
Node* cur = get_root();
while (cur)
{
if (key(cur->_data) < key(value))
{
cur = cur->_Right;
}
else if (key(cur->_data)>key(value))
{
cur = cur->_Left;
}
else
{
return RBiterator(cur);
}
}
return End();
}
RBiterator End()
{
return RBiterator(_head);
}
RBiterator Begin()
{
return RBiterator(_head->_Left);
}
size_t Size()const
{
return _size;
}
bool Empty()const
{
return _size == 0;
}
//中序遍歷//
void inoder()
{
cout << "中序遍歷結(jié)果為：";
Node* _root = get_root();
mid(_root);
cout << endl;
}
/判斷當(dāng)前樹是否是紅黑樹//
bool isRBtree()
{
Node* root = get_root();
if (root == nullptr)
{
return true;
}
//判斷根節(jié)點是否是黑色節(jié)點：
if (root->_color == RED)
{
return false;
}
//判斷每條路徑中黑色節(jié)點個數(shù)是否相同
size_t black_count = 0;
Node* cur = root;
while (cur)
{
if (cur->_color == BLACK)
{
black_count++;
}
cur = cur->_Left;
}
int k = 0;
return _isRBtree(black_count, k, root);
}
//判斷紅黑樹中是否滿足性質(zhì)三（兩個紅色節(jié)點不挨在一起）性質(zhì)四（每條路徑中黑色節(jié)點樹相同）
bool _isRBtree(size_t black_count, int k, Node* root)
{
if (root == nullptr)
{
if (k != black_count)
{
cout << "當(dāng)前樹不是紅黑樹，有一條路徑黑色節(jié)點個數(shù)為：" << k << "少于路徑節(jié)點：" << black_count << endl;
return false;
}
return true;
}
if (root->_color == BLACK)
{
k++;
}
else
{
if (root->_Parent->_color == RED)
{
cout << "當(dāng)前樹不是紅黑樹,有兩個紅色節(jié)點挨在一起。" << endl;
return false;
}
}
return _isRBtree(black_count, k, root->_Left) && _isRBtree(black_count, k, root->_Right);
}
/
void Swap(RBtree<T,Keyofvalue> _t)
{
std::swap(_head, _t._head);
}
private:
//中序遍歷：
void mid(Node* root)
{
if (root)
{
mid(root->_Left);
cout << root->_data << " ";
mid(root->_Right);
}
}
//這里因為我們紅黑樹中沒有設(shè)置根節(jié)點在代碼實現(xiàn)的時候不容易理解所以這里我們寫一個私有函數(shù)返回紅黑樹的根節(jié)點：
Node* &get_root()
{
return _head->_Parent;
}
//獲取最左側(cè)節(jié)點也就是最小節(jié)點：
Node* get_mostleftnode()
{
Node* _root = get_root();
if (_root)
{
while (_root->_Left)
{
_root = _root->_Left;
}
}
return _root;
}
//獲取最右側(cè)節(jié)點也就是最大節(jié)點：
Node* get_mostrightnode()
{
Node* _root = get_root();
if (_root)
{
while (_root->_Right)
{
_root = _root->_Right;
}
}
return _root;
}
//左單旋
void rotate_left(Node* parent)
{
Node* pparent = parent->_Parent;
Node* subR = parent->_Right;
Node* subRL = subR->_Left;
parent->_Right = subRL;
//更新subRL的雙親：
if (subRL)
{
subRL->_Parent = parent;
}
subR->_Left = parent;
parent->_Parent = subR;
subR->_Parent = pparent;
if (pparent == _head)//------------------------------------->>>>一定要注意這里的pparent如果是頭節(jié)點那么一定要將pparent的指向為subR
{
_head->_Parent = subR;
}
if (pparent)
{
if (pparent->_Left == parent)
{
pparent->_Left = subR;
}
else
{
pparent->_Right = subR;
}
}
}
//右單旋
void rotate_right(Node* parent)
{
Node* subL = parent->_Left;
Node* subLR = subL->_Right;
Node* pparent = parent->_Parent;
parent->_Left = subLR;
//如果subLR存在那么將其父節(jié)點更新
if (subLR)
{
subLR->_Parent = parent;
}
//將parent右旋下來：
subL->_Right = parent;
//parent旋下來就要更新parent的父節(jié)點
parent->_Parent = subL;
//此時subL就要更新父節(jié)點
subL->_Parent = pparent;
if (pparent == _head)
{
_head->_Parent = subL;
}
if (pparent)
{
if (parent == pparent->_Right)
{
pparent->_Right = subL;
}
else
{
pparent->_Left = subL;
}
}
}
private:
size_t _size;
Node* _head;
};
5. 基于紅黑樹的map的模擬實現(xiàn)
#pragma once
#include"RBtree.hpp"
//紅黑樹里面放的鍵值對
namespace wbx
{
template<class K,class V>
class map
{
public:
typedef pair<K,V> valuetype;
//這里是因為我們紅黑樹中存放的是鍵值對，而我們紅黑樹在實現(xiàn)的時候只有一個模板類型參數(shù)，
//也就是我們要存放在紅黑樹中的節(jié)點，而我們的map是用pair（鍵值對來存放節(jié)點的）但是比較
//的時候我們是通過pair中的key值來比較的，所以我們這里就要定義一個類來返回我們map中要
//比較的類型。
struct Keyofvalue
{
const K&operator()(const valuetype &value)
{
return value.first;
}
};
typedef RBtree<valuetype,Keyofvalue> Tree;
typedef typename Tree::RBiterator iterator;
map()
:_t()
{}
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
size_t size()const
{
return _t.Size();
}
size_t empty()const
{
return _t.Empty();
}
//這里map的operator[]我們實現(xiàn)的時候直接用insert來實現(xiàn)，這里我們在紅黑樹中實現(xiàn)insert的時候
//是不允許插入相同的元素的，所以這里我們operator[]如果是一個新的key值那么我們就將其直接
//插入了如果是一個原有的key值那么紅黑樹中的inset插入就會將它的迭代器返回那么我們這里將
//返回的迭代器解引用得到它的value值的引用那么我就可以對其進行修改
V& operator[](const K& key)
{
return (*(_t.insert(make_pair(key, V() ) ).first ) ).second;
}
pair<iterator, bool> insert(const valuetype& val)
{
return _t.insert(val);
}
void swap(map<K, V>& m)
{
_t.Swap(m._t);
}
void clear()
{
_t.Clear();
}
iterator find(const K& key )
{
return _t.Find(make_pair(key,V()));
}
private:
Tree _t;
};
};
6. 基于紅黑樹的set的模擬實現(xiàn)
#pragma once
#include"RBtree.hpp"
//紅黑樹里面放的鍵值對
namespace wbx
{
template<class K>
class set
{
public:
typedef K valuetype;
struct Keyofvalue
{
const K&operator()(const valuetype &value)
{
return value;
}
};
typedef RBtree<valuetype, Keyofvalue> Tree;
typedef typename Tree::RBiterator iterator;
set()
:_t()
{}
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
size_t size()const
{
return _t.Size();
}
size_t empty()const
{
return _t.Empty();
}
pair<iterator, bool> insert(const valuetype& val)
{
return _t.insert(val);
}
void swap(set<K>& s)
{
_t.Swap(s._t);
}
void clear()
{
_t.Clear();
}
iterator find(const valuetype& key)
{
return _t.Find(key);
}
private:
Tree _t;
};
};
end
更多信息可以來這里獲取==>>電子技術(shù)應(yīng)用-AET<<
電子技術(shù)應(yīng)用專欄作家 一口linux
原文鏈接：https://mp.weixin.qq.com/s/MGUMK8SQLD7unuIaRegsZQ