C++?用紅黑樹模擬實現(xiàn)set、map的示例代碼
更新時間：2024年03月20日 08:29:09 作者：～yY…s<#>
set、map的底層結(jié)構(gòu)是紅黑樹，它們的函數(shù)通過調(diào)用紅黑樹的接口來實現(xiàn)，本文主要介紹了C++?用紅黑樹模擬實現(xiàn)set、map，具有一定的參考價值，感興趣的可以了解一下
前言及準備：
set、map的底層結(jié)構(gòu)是紅黑樹，它們的函數(shù)通過調(diào)用紅黑樹的接口來實現(xiàn)，紅黑樹一些接口需要通過樹形迭代器來實現(xiàn)。set是k模型，map是kv模型，紅黑樹要不要寫兩份呢？答案是不需要，只用一份即可，通過仿函數(shù)來控制。
定義樹的節(jié)點：
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個指針域，數(shù)據(jù)域用T來表示，如果是set，那么傳過來的是k模型；如果是map，是kv模型。新增的節(jié)點的顏色默認是紅色（根節(jié)點除外）。
一、紅黑樹接口
1.1 begin
返回的是紅黑樹的第一個節(jié)點，注意，這里的第一個的順序是按中序遍歷來的，所以，第一個節(jié)點的位置是樹的最左節(jié)點。
//返回的迭代器指向的數(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
返回的是最后一個節(jié)點（最右側(cè)節(jié)點）的下一個位置。由于這里實現(xiàn)的紅黑樹沒有頭節(jié)點，所以只能給nullptr來勉強實現(xiàn)這個迭代器。但是這樣其實是不行的，因為對end()位置的迭代器進行 - - 操作，必須要能找最后一個元素，給nullptr就找不到了。如果有頭節(jié)點，那么end()的位置應(yīng)該是在頭節(jié)點的位置。
iterator end()
{
return iterator(nullptr);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
1.3 查找
查找的過程與之前寫的二叉搜索樹沒有多大區(qū)別，要注意的是返回類型，找到了，返回的是該節(jié)點的迭代器，找不到就返回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ù)進行比較，看傳過來的類模板參數(shù)中的仿函數(shù)是set的還是map的。當然，這里只需寫好就行，不用關(guān)心傳過來的是什么，set和map的仿函數(shù)內(nèi)部已經(jīng)確定好了。
說明一下：
template<class K, class T, class KeyOfT>
這是該紅黑樹的類模板，K是Find()函數(shù)中要對比的數(shù)據(jù)類型，T是節(jié)點的數(shù)據(jù)域，可能是k模型，也有可能是kv模型。怎么確定呢？通過第三個類模板參數(shù)——仿函數(shù)來確定。仿函數(shù)傳的是set的，就是k模型；仿函數(shù)傳的是map的，就是kv模型。仿函數(shù)內(nèi)部具體實現(xiàn)下面再說。
1.4 插入
為了接近STL庫中的insert函數(shù)，返回類型是pair，即插入成功，返回該節(jié)點的迭代器和true；插入失敗，說明該節(jié)點已經(jīng)存在，返回該節(jié)點的迭代器和false。
pair<iterator, bool> Insert(const T& data)
{
//為空
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//根節(jié)點都是黑色的，特殊處理
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é)點
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é)點
//父節(jié)點在爺爺節(jié)點的左邊，那么叔叔節(jié)點在右邊
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é)點在右邊，叔叔在左邊
{
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 左單旋和右單旋
這兩個就是之前的，這里不作重復(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 前置++
首先要清楚的是++到下一個節(jié)點位置是按中序遍歷走的，主要有兩種情況：
- 該節(jié)點有右子樹
- 該節(jié)點沒有右子樹
有右子樹
總結(jié)：有右子樹++后的下一個節(jié)點是右子樹的最左節(jié)點
沒有右子樹
總結(jié)：沒有右子樹++后下一個節(jié)點是祖先節(jié)點中左孩子是當前節(jié)點（原來節(jié)點的位置）或者左孩子是當前節(jié)點的父親的那個祖先
有點彎，再來圖捋一捋：
前置- -的邏輯與前置++剛好相反
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)
{
//下一個節(jié)點在右子樹的最左邊
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
//右子樹不存在
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//cur是parent的左子樹，parent就是下一個
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//前置--
Self& operator--()//與前置++的邏輯相反
{
//左子樹存在
if (_node->_left)
{
//下一個節(jié)點是左子樹的最右一個
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
//左子樹不存在
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//cur是parent的右子樹時parent就是下一個
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;
}
};
三、模擬實現(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;
};
四、模擬實現(xiàn)map
map是kv模型，仿函數(shù)返回的取kv中的key值。其他接口調(diào)用紅黑樹的，除此之外，多了一個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++ 用紅黑樹模擬實現(xiàn)set、map的示例代碼的文章就介紹到這了,更多相關(guān)C++ 紅黑樹實現(xiàn)set、map內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++中的內(nèi)存分區(qū)介紹,C++的內(nèi)存劃分為棧區(qū)、堆區(qū)、全局區(qū)/靜態(tài)區(qū)、字符串常量和代碼區(qū),本文分別對他們一一說明,需要的朋友可以參考下2015-07-07
淺談十進制小數(shù)和二進制小數(shù)之間的轉(zhuǎn)換
下面小編就為大家?guī)硪黄獪\談十進制小數(shù)和二進制小數(shù)之間的轉(zhuǎn)換。小編覺得挺不錯的現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
基于MATLAB神經(jīng)網(wǎng)絡(luò)圖像識別的高識別率代碼
今天小編就為大家分享一篇關(guān)于基于MATLAB神經(jīng)網(wǎng)絡(luò)圖像識別的高識別率代碼，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03
這篇文章主要介紹了C++ 中的臨時對象的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-08-08
這篇文章主要介紹了C語言解決螺旋矩陣算法問題的代碼示例,螺旋矩陣中的數(shù)字由第一行開始到右邊不斷變大,向下變大,向左變大,向上變大,如此循環(huán)...需要的朋友可以參考下2016-04-04
本文主要介紹了C語言實現(xiàn)動態(tài)鏈表的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
這篇文章主要介紹了C語言中的指針以及二級指針代碼詳解，小編覺得還是挺不錯的，具有一定借鑒價值,需要的朋友可以參考下2018-01-01
使用VS2019編譯CEF2623項目的libcef_dll_wrapper.lib的方法
這篇文章主要介紹了使用VS2019編譯CEF2623項目的libcef_dll_wrapper.lib的方法，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04
C++實現(xiàn)LeetCode(156.二叉樹的上下顛倒)
這篇文章主要介紹了C++實現(xiàn)LeetCode(156.二叉樹的上下顛倒),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了Qt6.0開發(fā)環(huán)境搭建步驟(圖文)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03