C++?用紅黑樹模擬實(shí)現(xiàn)set、map的示例代碼
更新時(shí)間：2024年03月20日 08:29:09 作者：～yY…s<#>
set、map的底層結(jié)構(gòu)是紅黑樹，它們的函數(shù)通過調(diào)用紅黑樹的接口來實(shí)現(xiàn)，本文主要介紹了C++?用紅黑樹模擬實(shí)現(xiàn)set、map，具有一定的參考價(jià)值，感興趣的可以了解一下
前言及準(zhǔn)備：
set、map的底層結(jié)構(gòu)是紅黑樹，它們的函數(shù)通過調(diào)用紅黑樹的接口來實(shí)現(xiàn)，紅黑樹一些接口需要通過樹形迭代器來實(shí)現(xiàn)。set是k模型，map是kv模型，紅黑樹要不要寫兩份呢？答案是不需要，只用一份即可，通過仿函數(shù)來控制。
定義樹的節(jié)點(diǎn)：
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Colour _col;
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_col(RED)
{}
};
紅黑樹有3個(gè)指針域，數(shù)據(jù)域用T來表示，如果是set，那么傳過來的是k模型；如果是map，是kv模型。新增的節(jié)點(diǎn)的顏色默認(rèn)是紅色（根節(jié)點(diǎn)除外）。
一、紅黑樹接口
1.1 begin
返回的是紅黑樹的第一個(gè)節(jié)點(diǎn)，注意，這里的第一個(gè)的順序是按中序遍歷來的，所以，第一個(gè)節(jié)點(diǎn)的位置是樹的最左節(jié)點(diǎn)。
//返回的迭代器指向的數(shù)據(jù)可修改
iterator begin()
{
Node* subLeft = _root;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
return iterator(subLeft);
}
//返回的迭代器指向的數(shù)據(jù)不可修改
const_iterator begin() const
{
Node* subLeft = _root;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
return const_iterator(subLeft);
}
1.2 end
返回的是最后一個(gè)節(jié)點(diǎn)（最右側(cè)節(jié)點(diǎn)）的下一個(gè)位置。由于這里實(shí)現(xiàn)的紅黑樹沒有頭節(jié)點(diǎn)，所以只能給nullptr來勉強(qiáng)實(shí)現(xiàn)這個(gè)迭代器。但是這樣其實(shí)是不行的，因?yàn)閷?duì)end()位置的迭代器進(jìn)行 - - 操作，必須要能找最后一個(gè)元素，給nullptr就找不到了。如果有頭節(jié)點(diǎn)，那么end()的位置應(yīng)該是在頭節(jié)點(diǎn)的位置。
iterator end()
{
return iterator(nullptr);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
1.3 查找
查找的過程與之前寫的二叉搜索樹沒有多大區(qū)別，要注意的是返回類型，找到了，返回的是該節(jié)點(diǎn)的迭代器，找不到就返回end()。
iterator Find(const K& key)
{
KeyOfT kot;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return iterator(cur);
}
}
return end();
}
咋知道是set還是map的數(shù)據(jù)進(jìn)行比較，看傳過來的類模板參數(shù)中的仿函數(shù)是set的還是map的。當(dāng)然，這里只需寫好就行，不用關(guān)心傳過來的是什么，set和map的仿函數(shù)內(nèi)部已經(jīng)確定好了。
說明一下：
template<class K, class T, class KeyOfT>
這是該紅黑樹的類模板，K是Find()函數(shù)中要對(duì)比的數(shù)據(jù)類型，T是節(jié)點(diǎn)的數(shù)據(jù)域，可能是k模型，也有可能是kv模型。怎么確定呢？通過第三個(gè)類模板參數(shù)——仿函數(shù)來確定。仿函數(shù)傳的是set的，就是k模型；仿函數(shù)傳的是map的，就是kv模型。仿函數(shù)內(nèi)部具體實(shí)現(xiàn)下面再說。
1.4 插入
為了接近STL庫(kù)中的insert函數(shù)，返回類型是pair，即插入成功，返回該節(jié)點(diǎn)的迭代器和true；插入失敗，說明該節(jié)點(diǎn)已經(jīng)存在，返回該節(jié)點(diǎn)的迭代器和false。
pair<iterator, bool> Insert(const T& data)
{
//為空
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//根節(jié)點(diǎn)都是黑色的，特殊處理
return make_pair(iterator(_root), true);
}
//非空
KeyOfT kot;
Node* cur = _root;
Node* parent = nullptr;
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)
cur = new Node(data);//紅色的
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
Node* newnode = cur;
//調(diào)整顏色
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;//爺爺節(jié)點(diǎn)
//父節(jié)點(diǎn)在爺爺節(jié)點(diǎn)的左邊，那么叔叔節(jié)點(diǎn)在右邊
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情況一：叔叔存在且為紅
if (uncle && uncle->_col == RED)
{
grandfather->_col = RED;
uncle->_col = parent->_col = BLACK;
cur = grandfather;//爺爺不是根，向上更新
parent = cur->_parent;
}
//情況二：叔叔不存在/存在且為黑
else
{
//單旋
if (cur == parent->_left)
{
RotateR(grandfather);//右單旋
parent->_col = BLACK;//變色
grandfather->_col = RED;
}
//左右雙旋
// cur == parent->_right
else
{
RotateL(parent);//先左單旋
RotateR(grandfather);//再右單旋
grandfather->_col = RED;//變色
cur->_col = BLACK;
}
}
}
else//父節(jié)點(diǎn)在右邊，叔叔在左邊
{
Node* uncle = grandfather->_left;
//情況一：叔叔存在且為紅
if (uncle && uncle->_col == RED)
{
grandfather->_col = RED;
uncle->_col = parent->_col = BLACK;
cur = grandfather;//爺爺不是根，向上更新
parent = cur->_parent;
}
//情況二：叔叔不存在/存在且為黑
else
{
//單旋
if (cur == parent->_right)
{
RotateL(grandfather);//左單旋
parent->_col = BLACK;//變色
grandfather->_col = RED;
}
//右左雙旋
// cur == parent->_left
else
{
RotateR(parent);//先右單旋
RotateL(grandfather);//再左單旋
grandfather->_col = RED;//變色
cur->_col = BLACK;
}
break;//經(jīng)過情況二后跳出
}
}
}
_root->_col = BLACK;//統(tǒng)一處理，根必須是黑的
return make_pair(iterator(newnode), true);
}
1.5 左單旋和右單旋
這兩個(gè)就是之前的，這里不作重復(fù)敘述了
//左單旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
//不為空
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = subR;
//處理parent如果為根
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
//不為根，處理與ppnode的連接
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;
}
subL->_right = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}
二、樹形迭代器（正向）
2.1 前置++
首先要清楚的是++到下一個(gè)節(jié)點(diǎn)位置是按中序遍歷走的，主要有兩種情況：
- 該節(jié)點(diǎn)有右子樹
- 該節(jié)點(diǎn)沒有右子樹
有右子樹
總結(jié)：有右子樹++后的下一個(gè)節(jié)點(diǎn)是右子樹的最左節(jié)點(diǎn)
沒有右子樹
總結(jié)：沒有右子樹++后下一個(gè)節(jié)點(diǎn)是祖先節(jié)點(diǎn)中左孩子是當(dāng)前節(jié)點(diǎn)（原來節(jié)點(diǎn)的位置）或者左孩子是當(dāng)前節(jié)點(diǎn)的父親的那個(gè)祖先
有點(diǎn)彎，再來圖捋一捋：
前置- -的邏輯與前置++剛好相反
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
//前置++
Self& operator++()
{
//右子樹存在
if (_node->_right)
{
//下一個(gè)節(jié)點(diǎn)在右子樹的最左邊
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
//右子樹不存在
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//cur是parent的左子樹，parent就是下一個(gè)
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//前置--
Self& operator--()//與前置++的邏輯相反
{
//左子樹存在
if (_node->_left)
{
//下一個(gè)節(jié)點(diǎn)是左子樹的最右一個(gè)
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
//左子樹不存在
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//cur是parent的右子樹時(shí)parent就是下一個(gè)
while (parent && parent->_left == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
三、模擬實(shí)現(xiàn)set
set是k模型，仿函數(shù)返回的只有key值。其他接口調(diào)用紅黑樹的
template<class K>
class set
{
//仿函數(shù)
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;
//迭代器
iterator begin()
{
return _t.begin();
}
const_iterator begin() const
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator end() const
{
return _t.end();
}
//插入
pair<iterator, bool> Insert(const K& key)
{
return _t.Insert(key);
}
//查找
iterator Find(const K& key)
{
_t.Find(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
四、模擬實(shí)現(xiàn)map
map是kv模型，仿函數(shù)返回的取kv中的key值。其他接口調(diào)用紅黑樹的，除此之外，多了一個(gè)operator[]
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
//迭代器
iterator begin()
{
return _t.begin();
}
const_iterator begin() const
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator end() const
{
return _t.end();
}
//插入
pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
//查找
iterator Find(const K& key)
{
_t.Find(key);
}
//operator[]
V& operator[](const K& key)
{
pair<iterator, bool> ret = Insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};到此這篇關(guān)于C++ 用紅黑樹模擬實(shí)現(xiàn)set、map的示例代碼的文章就介紹到這了,更多相關(guān)C++ 紅黑樹實(shí)現(xiàn)set、map內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++調(diào)用Go方法的字符串傳遞問題及解決方案，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易的掃雷游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易的掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
本篇文章是對(duì)jaxb xjc編碼的問題進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
用代碼和UML圖化解設(shè)計(jì)模式之橋接模式的深入分析
本篇文章是對(duì)橋接模式進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
以下實(shí)例是對(duì)使用c++實(shí)現(xiàn)x的y次冪的解決方法進(jìn)行了介紹。需要的朋友參考下2013-05-05
這篇文章主要為大家詳細(xì)介紹了使用C語(yǔ)言實(shí)現(xiàn)掃雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-05-05
在之前的C++代碼訓(xùn)練營(yíng)系列中，我試圖用完成具體項(xiàng)目的方式給大家介紹C++，但后來大家反饋說這樣從C過渡到C++有點(diǎn)跟不上。于是我又專門設(shè)計(jì)了這個(gè)《從C到C++》的過渡專題，我準(zhǔn)備通過10篇文章介紹一下C++和C的重要區(qū)別。2017-07-07
C++類與對(duì)象深入之靜態(tài)成員與友元及內(nèi)部類詳解
朋友們好,這篇播客我們繼續(xù)C++的初階學(xué)習(xí)，現(xiàn)在對(duì)我們對(duì)C++的靜態(tài)成員，友元，內(nèi)部類知識(shí)點(diǎn)做出總結(jié)，整理出來一篇博客供我們一起復(fù)習(xí)和學(xué)習(xí),如果文章中有理解不當(dāng)?shù)牡胤?還希望朋友們?cè)谠u(píng)論區(qū)指出,我們相互學(xué)習(xí),共同進(jìn)步2022-06-06
在本篇文章里小編給大家分享了一篇關(guān)于c++中創(chuàng)建.in文件的方法步驟的內(nèi)容以及相關(guān)知識(shí)點(diǎn)，需要的朋友們學(xué)習(xí)下。2019-07-07
這篇文章主要介紹了COM編程之什么是組件？COM組件是以Win32動(dòng)態(tài)鏈接庫(kù)（DLLs）或可執(zhí)行文件（EXEs）的形式發(fā)布的可執(zhí)行代碼,需要的朋友可以參考下2014-10-10