C++?用紅黑樹模擬實現set、map的示例代碼
更新時間：2024年03月20日 08:29:09 作者：～yY…s<#>
set、map的底層結構是紅黑樹，它們的函數通過調用紅黑樹的接口來實現，本文主要介紹了C++?用紅黑樹模擬實現set、map，具有一定的參考價值，感興趣的可以了解一下
前言及準備：
set、map的底層結構是紅黑樹，它們的函數通過調用紅黑樹的接口來實現，紅黑樹一些接口需要通過樹形迭代器來實現。set是k模型，map是kv模型，紅黑樹要不要寫兩份呢？答案是不需要，只用一份即可，通過仿函數來控制。
定義樹的節(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個指針域，數據域用T來表示，如果是set，那么傳過來的是k模型；如果是map，是kv模型。新增的節(jié)點的顏色默認是紅色（根節(jié)點除外）。
一、紅黑樹接口
1.1 begin
返回的是紅黑樹的第一個節(jié)點，注意，這里的第一個的順序是按中序遍歷來的，所以，第一個節(jié)點的位置是樹的最左節(jié)點。
//返回的迭代器指向的數據可修改
iterator begin()
{
Node* subLeft = _root;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
return iterator(subLeft);
}
//返回的迭代器指向的數據不可修改
const_iterator begin() const
{
Node* subLeft = _root;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
return const_iterator(subLeft);
}
1.2 end
返回的是最后一個節(jié)點（最右側節(jié)點）的下一個位置。由于這里實現的紅黑樹沒有頭節(jié)點，所以只能給nullptr來勉強實現這個迭代器。但是這樣其實是不行的，因為對end()位置的迭代器進行 - - 操作，必須要能找最后一個元素，給nullptr就找不到了。如果有頭節(jié)點，那么end()的位置應該是在頭節(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的數據進行比較，看傳過來的類模板參數中的仿函數是set的還是map的。當然，這里只需寫好就行，不用關心傳過來的是什么，set和map的仿函數內部已經確定好了。
說明一下：
template<class K, class T, class KeyOfT>
這是該紅黑樹的類模板，K是Find()函數中要對比的數據類型，T是節(jié)點的數據域，可能是k模型，也有可能是kv模型。怎么確定呢？通過第三個類模板參數——仿函數來確定。仿函數傳的是set的，就是k模型；仿函數傳的是map的，就是kv模型。仿函數內部具體實現下面再說。
1.4 插入
為了接近STL庫中的insert函數，返回類型是pair，即插入成功，返回該節(jié)點的迭代器和true；插入失敗，說明該節(jié)點已經存在，返回該節(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;
//調整顏色
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;//經過情況二后跳出
}
}
}
_root->_col = BLACK;//統一處理，根必須是黑的
return make_pair(iterator(newnode), true);
}
1.5 左單旋和右單旋
這兩個就是之前的，這里不作重復敘述了
//左單旋
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é)點的父親的那個祖先
有點彎，再來圖捋一捋：
前置- -的邏輯與前置++剛好相反
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;
}
};
三、模擬實現set
set是k模型，仿函數返回的只有key值。其他接口調用紅黑樹的
template<class K>
class set
{
//仿函數
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;
};
四、模擬實現map
map是kv模型，仿函數返回的取kv中的key值。其他接口調用紅黑樹的，除此之外，多了一個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;
};到此這篇關于C++ 用紅黑樹模擬實現set、map的示例代碼的文章就介紹到這了,更多相關C++ 紅黑樹實現set、map內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++調用Go方法的字符串傳遞問題及解決方案，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
這篇文章主要為大家詳細介紹了C語言實現簡易的掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
本篇文章是對jaxb xjc編碼的問題進行了詳細的分析介紹，需要的朋友參考下2013-05-05
本篇文章是對橋接模式進行了詳細的分析介紹，需要的朋友參考下2013-05-05
以下實例是對使用c++實現x的y次冪的解決方法進行了介紹。需要的朋友參考下2013-05-05
這篇文章主要為大家詳細介紹了使用C語言實現掃雷小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
在之前的C++代碼訓練營系列中，我試圖用完成具體項目的方式給大家介紹C++，但后來大家反饋說這樣從C過渡到C++有點跟不上。于是我又專門設計了這個《從C到C++》的過渡專題，我準備通過10篇文章介紹一下C++和C的重要區(qū)別。2017-07-07
朋友們好,這篇播客我們繼續(xù)C++的初階學習，現在對我們對C++的靜態(tài)成員，友元，內部類知識點做出總結，整理出來一篇博客供我們一起復習和學習,如果文章中有理解不當的地方,還希望朋友們在評論區(qū)指出,我們相互學習,共同進步2022-06-06
在本篇文章里小編給大家分享了一篇關于c++中創(chuàng)建.in文件的方法步驟的內容以及相關知識點，需要的朋友們學習下。2019-07-07
這篇文章主要介紹了COM編程之什么是組件？COM組件是以Win32動態(tài)鏈接庫（DLLs）或可執(zhí)行文件（EXEs）的形式發(fā)布的可執(zhí)行代碼,需要的朋友可以參考下2014-10-10