??歡迎來(lái)到數(shù)據(jù)結(jié)構(gòu)專(zhuān)欄~~封裝Map和Set
- (???(??? )??,我是Scort
- 目前狀態(tài)：大三非科班啃C++中
- ??博客主頁(yè)：張小姐的貓~江湖背景
- 快上車(chē)??，握好方向盤(pán)跟我有一起打天下嘞！
- 送給自己的一句雞湯??：
- ??真正的大師永遠(yuǎn)懷著一顆學(xué)徒的心
- 作者水平很有限，如果發(fā)現(xiàn)錯(cuò)誤，可在評(píng)論區(qū)指正，感謝??
- ????歡迎持續(xù)關(guān)注！
一. 紅黑樹(shù)源碼
雖然 set 參數(shù)只有 key，但是介于 map 除了 key 還有 value；我們?nèi)稳粚?duì)一棵KV模型的紅黑樹(shù)進(jìn)行封裝，
//枚舉顏色
enum Colour
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;//三叉鏈
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;//存儲(chǔ)鍵值對(duì)
Colour _col;//節(jié)點(diǎn)顏色
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
template<class K, class V>
struct RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//如果是空樹(shù)，則插入節(jié)點(diǎn)作為root節(jié)點(diǎn)
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;//根節(jié)點(diǎn)必須是黑色
return true; //插入成功
}
//按二叉搜索樹(shù)的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first > cur->_kv.first)//待插入結(jié)點(diǎn)的key值大于當(dāng)前結(jié)點(diǎn)的key值
{
//往節(jié)點(diǎn)的右子樹(shù)走
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first)//待插入結(jié)點(diǎn)的key值小于當(dāng)前結(jié)點(diǎn)的key值
{
//往節(jié)點(diǎn)的左子樹(shù)走
parent = cur;
cur = cur->_left;
}
else//插入的值等于當(dāng)前的節(jié)點(diǎn)，返回失敗
{
return false;
}
}
//將節(jié)點(diǎn)鏈接到樹(shù)上
cur = new Node(kv);//構(gòu)造節(jié)點(diǎn)
cur->_col = RED;
if (kv.first < parent->_kv.first) //判斷鏈接左還是右？
{
//插入到左邊
parent->_left = cur;
cur->_parent = parent;
}
else if (kv.first > parent->_kv.first)
{
//插入到右邊
parent->_right = cur;
cur->_parent = parent;
}
//如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，則需要對(duì)紅黑樹(shù)進(jìn)行操作
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
assert(grandfather->_col == BLACK);
//關(guān)鍵看叔叔 ~ 判斷叔叔的位置
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情況1：uncle存在且為紅 + 繼續(xù)往上處理
if (uncle && uncle->_col == RED)
{
//變色：p和u變黑，g變紅
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//繼續(xù)往上調(diào)整
cur = grandfather;
parent = cur->_parent;
}
else //情況2 + 情況3：uncle不存在 + uncle存在且為黑
{
//情況二：?jiǎn)涡?+ 變色
// g
// p u
//c
if (cur = parent->_left)
{
RotateR(grandfather);//右旋
//顏色調(diào)整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_right
{
//情況三：左右雙旋 + 變色
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
//調(diào)整顏色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else //parent == grandfather->_right
{
Node* uncle = grandfather->_left;
//情況1：uncle存在且為紅 + 繼續(xù)往上處理
if (uncle && uncle->_col == RED)
{
//變色：p和u變黑，g變紅
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//繼續(xù)往上調(diào)整
cur = grandfather;
parent = cur->_parent;
}
else //情況2 + 情況3：uncle不存在 + uncle存在且為黑
{
//情況二：?jiǎn)涡?+ 變色
// g
// u p
// c
if (cur = parent->_right)
{
RotateL(grandfather);//左單 旋
//顏色調(diào)整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_left
{
//情況三：右左雙旋 + 變色
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
//調(diào)整顏色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;//不管什么，最后根要變黑
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout << "根節(jié)點(diǎn)不是黑色" << 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;//以最左的路徑進(jìn)行
}
return PrevCheck(_root, 0, benchmark);
}
private:
bool PrevCheck(Node* root, int blackNum, int& benchmark)
{
if (root == nullptr)
{
//cout << blackNum << endl;
//return;
if (benchmark == 0)
{
benchmark = blackNum;
return true;
}
if (blackNum != benchmark)
{
cout << "某條黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;
return false;
}
else
{
return true;
}
}
if (root->_col == BLACK)
{
++blackNum;
}
//檢測(cè)它的父親
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在連續(xù)的紅色節(jié)點(diǎn)" << endl;
return false;
}
return PrevCheck(root->_left, blackNum, benchmark)
&& PrevCheck(root->_right, blackNum, benchmark);
}
void _InOrder(Node* root)
{
if (root == nullptr)//空樹(shù)也是紅黑樹(shù)
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
//左單旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//建立subRL與parent之間的聯(lián)系
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//建立parent與subR之間的聯(lián)系
subR->_left = parent;
parent->_parent = subR;
//建立subR與parentParent之間的聯(lián)系
if (parentParent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
//右單旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//建立subLR與parent之間的聯(lián)系
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//建立parent與subL之間的聯(lián)系
subL->_right = parent;
parent->_parent = subL;
//建立subL與parentParent之間的聯(lián)系
if (parentParent == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
//左右雙旋
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}
//右左雙旋
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}
private:
Node* _root = nullptr;
};
二. 觀察源碼
??底層RBTree的結(jié)構(gòu)
RBTree是根據(jù)傳的Value的值來(lái)判斷是什么類(lèi)型，也就是一棵泛型的RBTree，通過(guò)不同的實(shí)例化，實(shí)現(xiàn)出了Map和Set（傳Key就是Set，傳pair就是Map）
??底層的Key和Map
可見(jiàn)set傳的是Key，Map傳的是pair
二. 參數(shù)的適配
為了實(shí)現(xiàn)泛型RBTree，對(duì)此我們將紅黑樹(shù)第二個(gè)模板參數(shù)的名字改為T，讓自動(dòng)識(shí)別是map還是set
template<class K, class T>
struct RBTree
T模板參數(shù)可能只是鍵值Key，也可能是由Key和Value共同構(gòu)成的鍵值對(duì)。如果是set容器，那么它傳入底層紅黑樹(shù)的模板參數(shù)就是Key和Key：
template<class K>
class set
{
public：
//...
private:
RBTree<K, K> _t;
};
但如果是map容器，那么它傳入底層紅黑樹(shù)的模板參數(shù)就是Key以及Key和Value構(gòu)成的鍵值對(duì)：
template<class K, class V>
class map
{
public:
//...
private:
RBTree<K, pair<K, V>> _t;
};
那么問(wèn)題來(lái)了：如果只看T的判斷的話，是不是可以只保留第二個(gè)模板參數(shù)呢？
1??對(duì)于Insert來(lái)說(shuō)確實(shí)是這樣的，因?yàn)榇藭r(shí)紅黑樹(shù)的第二個(gè)模板參數(shù)當(dāng)中也是有鍵值Key的，但是Key實(shí)際上是不可以省略的！
2??對(duì)于set容器來(lái)說(shuō)，省略紅黑樹(shù)的第一個(gè)參數(shù)當(dāng)然沒(méi)問(wèn)題，因?yàn)閟et傳入紅黑樹(shù)的第二個(gè)參數(shù)與第一個(gè)參數(shù)是一樣的。但是對(duì)于map容器來(lái)說(shuō)就不行了，因?yàn)閙ap容器所提供的接口當(dāng)中有些是只要求給出鍵值Key的，比如find和erase
三. 數(shù)據(jù)的存儲(chǔ)
紅黑樹(shù)的模板參數(shù)變成了K和T，那節(jié)點(diǎn)存的是什么呢？
看了源碼得知
- set容器：K和T都代表鍵值Key
- map容器：K代表鍵值Key，T代表由Key和Value構(gòu)成的鍵值對(duì)
對(duì)于set容器來(lái)說(shuō)，底層紅黑樹(shù)結(jié)點(diǎn)當(dāng)中存儲(chǔ)K和T都是一樣的，但是對(duì)于map容器來(lái)說(shuō)，底層紅黑樹(shù)就只能存儲(chǔ)T了。由于底層紅黑樹(shù)并不知道上層容器到底是map還是set，因此紅黑樹(shù)的結(jié)點(diǎn)當(dāng)中直接存儲(chǔ)T就行了
這樣一來(lái)就可以實(shí)現(xiàn)泛型樹(shù)了，當(dāng)上層容器是set的時(shí)候，結(jié)點(diǎn)當(dāng)中存儲(chǔ)的是鍵值Key；當(dāng)上層容器是map的時(shí)候，結(jié)點(diǎn)當(dāng)中存儲(chǔ)的就是<Key, Value>鍵值對(duì)
template<class T>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;//三叉鏈
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
T _data;//存儲(chǔ)的數(shù)據(jù)
Colour _col;//節(jié)點(diǎn)顏色
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
四. 仿函數(shù)的支持
那我們插入比較的時(shí)候用data去比較嗎？
- 對(duì)于set而言是
Key，可以比較 - 但是對(duì)于map是
pair，那我們要取其中的first來(lái)比較，但是我們能取first嗎？ - 這個(gè)地方的data有可能是map；也有可能是set
那就只能我們自己實(shí)現(xiàn)一個(gè)仿函數(shù)了，如果是map那就是用于獲取T當(dāng)中的鍵值Key，當(dāng)紅黑樹(shù)比較的時(shí)候就是仿函數(shù)去獲取
仿函數(shù)，就是使一個(gè)類(lèi)的使用看上去像一個(gè)函數(shù)。其實(shí)現(xiàn)就是類(lèi)中實(shí)現(xiàn)一個(gè)
operator()，這個(gè)類(lèi)就有了類(lèi)似函數(shù)的行為，就是一個(gè)仿函數(shù)類(lèi)了
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
底層的紅黑樹(shù)不知道上層傳的是map還是set，因此當(dāng)需要進(jìn)行兩個(gè)結(jié)點(diǎn)鍵值的比較時(shí)，底層紅黑樹(shù)都會(huì)通過(guò)傳入的仿函數(shù)來(lái)獲取鍵值Key，進(jìn)而進(jìn)行兩個(gè)結(jié)點(diǎn)鍵值的比較
set的仿函數(shù)不可缺
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
}
private:
RBTree<K, K, SetKeyOfT> _t;
所以set容器傳入底層紅黑樹(shù)的就是set的仿函數(shù)，map容器傳入底層紅黑樹(shù)的就是map的仿函數(shù)
//查找函數(shù)
Node* Find(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(data) > kot(cur->_data))//待插入結(jié)點(diǎn)的key值大于當(dāng)前結(jié)點(diǎn)的key值
{
//往節(jié)點(diǎn)的右子樹(shù)走
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))//待插入結(jié)點(diǎn)的key值小于當(dāng)前結(jié)點(diǎn)的key值
{
//往節(jié)點(diǎn)的左子樹(shù)走
parent = cur;
cur = cur->_left;
}
else//插入的值等于當(dāng)前的節(jié)點(diǎn)，返回失敗
{
return false;
}
}
注意：
- 1??所有進(jìn)行節(jié)點(diǎn)鍵值比較的地方，均需要通過(guò)仿函數(shù)獲取對(duì)應(yīng)節(jié)點(diǎn)的鍵值后再進(jìn)行鍵值的比較
- 2??map和set的底層是一棵泛型紅黑樹(shù)實(shí)例化而來(lái)，實(shí)際上不是同一棵紅黑樹(shù)
五. 迭代器實(shí)現(xiàn)
??正向迭代器
紅黑樹(shù)的正向迭代器實(shí)際上就是對(duì)結(jié)點(diǎn)指針進(jìn)行了封裝，因此在正向迭代器當(dāng)中實(shí)際上就只有一個(gè)成員變量，那就是結(jié)點(diǎn)的指針！
//正向迭代器
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;//節(jié)點(diǎn)類(lèi)型
typedef __RBTreeIterator<T, Ref, Ptr> Self;//正向迭代器類(lèi)型
Node* _node;//封裝節(jié)點(diǎn)的指針
}
通過(guò)一個(gè)節(jié)點(diǎn)的指針就可以封裝出迭代器！
__RBTreeIterator(Node* node)
:_node(node)
{}
當(dāng)我們對(duì)正向迭代器進(jìn)行解引用操作時(shí)，我們直接返回對(duì)應(yīng)結(jié)點(diǎn)數(shù)據(jù)的引用即可
Ref operator*()
{
return _node->_data;//返回節(jié)點(diǎn)數(shù)據(jù)的引用
}
以及成員訪問(wèn)操作符 ->：
Ptr operator->()
{
return &_node->_data;//返回節(jié)點(diǎn)數(shù)據(jù)的指針
}
當(dāng)然，正向迭代器當(dāng)中至少還需要重載==和!=運(yùn)算符，實(shí)現(xiàn)時(shí)直接判斷兩個(gè)迭代器所封裝的結(jié)點(diǎn)是否是同一個(gè)即可
bool operator!=(const Self& s) const
{
return _node != s._node//判斷兩個(gè)正向迭代器所封裝的結(jié)點(diǎn)是否是同一個(gè)
}
bool operator==(const Self& s) const
{
return _node == s._node//同上
}
重頭戲才剛剛開(kāi)始！真正的難點(diǎn)實(shí)際上++和--運(yùn)算符的重載
一個(gè)結(jié)點(diǎn)的正向迭代器進(jìn)行++操作后，應(yīng)該根據(jù)紅黑樹(shù)中序遍歷的序列找到當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
具體思路如下：
- 當(dāng)前節(jié)點(diǎn)的右子樹(shù)不為空，
++就是找 右子樹(shù)中序的第一個(gè)（最左節(jié)點(diǎn)） - 如果節(jié)點(diǎn)的右子樹(shù)為空，
++就是找到 孩子在祖先左邊的祖先
Self& operator++()
{
if (_node->_right)
{
//尋找該節(jié)點(diǎn)右子樹(shù)中的最左節(jié)點(diǎn)
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;//給給變成該節(jié)點(diǎn)
}
else
{
//找孩子在祖先左邊的祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right) //判斷parent不為空，空就崩了
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
同理， -- 的邏輯是一樣的：
- 當(dāng)前節(jié)點(diǎn)的左子樹(shù)不為空，
--就是找 左子樹(shù)中序的第一個(gè)（最右節(jié)點(diǎn)） - 如果節(jié)點(diǎn)的左子樹(shù)為空，
--就是找到 孩子在祖先右邊的祖先
Self& operator--()
{
if (_node->_left)//結(jié)點(diǎn)的左子樹(shù)不為空
{
//尋找該節(jié)點(diǎn)左子樹(shù)中的最右節(jié)點(diǎn)
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;//給給變成該節(jié)點(diǎn)
}
else//結(jié)點(diǎn)的左子樹(shù)為空
{
//找孩子在祖先右邊的祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left) //判斷parent不為空，空就崩了
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
我們實(shí)現(xiàn)迭代器的時(shí)候會(huì)將迭代器類(lèi)型進(jìn)行 typedef 方便調(diào)用，完事了不要忘了迭代器還有兩個(gè)成員函數(shù) begin（） 和 end（） ；
-
begin（）返回中序序列當(dāng)中第一個(gè)結(jié)點(diǎn)的正向迭代器，即最左節(jié)點(diǎn) -
end （）返回中序序列當(dāng)中最后一個(gè)結(jié)點(diǎn)下一個(gè)位置的正向迭代器，這里直接用空指針構(gòu)造一個(gè)正向迭代器（不嚴(yán)謹(jǐn)?shù)奶幚恚?/li>
template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator<T, T&, T*> iterator;//正向迭代器
iterator begin()
{
//尋找最左節(jié)點(diǎn)
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
//返回最左結(jié)點(diǎn)的正向迭代器
return iterator(left);
}
iterator end()
{
//返回空節(jié)點(diǎn)的迭代器
return iterator(nullptr);
}
}
實(shí)際上，上述所實(shí)現(xiàn)的迭代器是有缺陷的，因?yàn)槔碚撋衔覀儗?duì)end()位置的正向迭代器進(jìn)行–操作后，應(yīng)該得到最后一個(gè)結(jié)點(diǎn)的正向迭代器，但我們實(shí)現(xiàn)end()時(shí)，是直接返回由nullptr構(gòu)造得到的正向迭代器的，因此上述實(shí)現(xiàn)的代碼無(wú)法完成此操作
所以我們不妨看看 C++ STL 庫(kù)的實(shí)現(xiàn)邏輯
庫(kù)里面是采用了類(lèi)似雙向鏈表的處理，給整個(gè)紅黑樹(shù)造了一個(gè)哨兵位節(jié)點(diǎn)，該節(jié)點(diǎn)左邊指向最小的最左節(jié)點(diǎn)，右邊指向最大的右節(jié)點(diǎn)，同時(shí)還有一個(gè)非常 bug 的設(shè)計(jì)就是這里哨兵位節(jié)點(diǎn) header 的紅黑樹(shù)頭結(jié)點(diǎn)之間的 parent 相互指向
在該結(jié)構(gòu)下，實(shí)現(xiàn) begin() 時(shí)，直接用頭結(jié)點(diǎn)的左孩子構(gòu)造一個(gè)正向迭代器即可，實(shí)現(xiàn) rbegin() 時(shí)，直接用頭結(jié)點(diǎn)的右孩子構(gòu)造一個(gè)反向迭代器即可，嚴(yán)謹(jǐn)?shù)倪^(guò)程是先構(gòu)造正向迭代器，再用正向迭代器構(gòu)造反向迭代器，end（） 和 rend（） 此時(shí)就不需要什么 nullptr 了，直接有頭結(jié)點(diǎn)（哨兵位）進(jìn)行迭代器構(gòu)造即可，這樣就能完成一個(gè)邏輯完整的迭代器了
??反向迭代器
上面得知：反向迭代器的嚴(yán)謹(jǐn)構(gòu)造過(guò)程是用正向迭代器進(jìn)行封裝，我們可以將
template<class Iterator>//迭代器適配器
struct ReverseIterator
{
typedef ReverseIterator<Iterator> Self; //反向迭代器
typedef typename Iterator::reference Ref; //指針的引用
typedef typename Iterator::pointer Ptr; //結(jié)點(diǎn)指針
Iterator _it; //反向迭代器封裝的正向迭代器
//構(gòu)造函數(shù)
ReverseIterator(Iterator it)
:_it(it) //根據(jù)所給正向迭代器構(gòu)造一個(gè)反向迭代器
{}
Ref operator*()
{
return *_it; //調(diào)用正向迭代器的operator*返回引用
}
Ptr operator->()
{
return _it.operator->(); //調(diào)用正向迭代器的operator->返回指針
}
Self& operator++() //前置++
{
--_it; //調(diào)用正向迭代器的前置--
return *this;
}
//前置--
Self& operator--()
{
++_it; //調(diào)用正向迭代器的前置++
return *this;
}
bool operator!=(const Self& s) const
{
return _it != s._it;
}
bool operator==(const Self& s) const
{
return _it == s._it;
}
};
Set的實(shí)現(xiàn)
都是接上紅黑樹(shù)的接口即可
namespace ljj
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//typename告訴編譯器這一大坨是類(lèi)型，不是靜態(tài)變量
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);//調(diào)用紅黑樹(shù)的insert
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}
Map的實(shí)現(xiàn)
map 也和 set 同理，復(fù)用紅黑樹(shù)的底層接口實(shí)現(xiàn)，此外還需要實(shí)現(xiàn) [] 運(yùn)算符的重載：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-806523.html
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typename告訴編譯器這一大坨是類(lèi)型，不是靜態(tài)變量
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);//調(diào)用紅黑樹(shù)的insert
}
//【】的底層調(diào)用就是Insert
V& operator[](const K& key)
{
pair<iterator, bool> ret = Insert(make_pair(K, V()));//插入成功就是當(dāng)前的迭代器，失敗就是之前的迭代器
return ret.first->second;
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
紅黑樹(shù)的代碼
//枚舉顏色
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;//三叉鏈
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//pair<K, V> _kv;//存儲(chǔ)鍵值對(duì)
T _data;
Colour _col;//節(jié)點(diǎn)顏色
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
//正向迭代器
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;//節(jié)點(diǎn)類(lèi)型
typedef __RBTreeIterator<T, Ref, Ptr> Self;//正向迭代器類(lèi)型
Node* _node;//封裝節(jié)點(diǎn)的指針
__RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;//返回節(jié)點(diǎn)數(shù)據(jù)的引用
}
Ptr operator->()
{
return &_node->_data;//返回節(jié)點(diǎn)數(shù)據(jù)的指針
}
bool operator!=(const Self& s) const
{
return _node != s._node;//判斷兩個(gè)正向迭代器所封裝的結(jié)點(diǎn)是否是同一個(gè)
}
bool operator==(const Self& s) const
{
return _node == s._node;//同上
}
Self& operator++()
{
if (_node->_right)
{
//尋找該節(jié)點(diǎn)右子樹(shù)中的最左節(jié)點(diǎn)
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;//給給變成該節(jié)點(diǎn)
}
else
{
//找孩子在祖先左邊的祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right) //判斷parent不為空，空就崩了
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)//結(jié)點(diǎn)的左子樹(shù)不為空
{
//尋找該節(jié)點(diǎn)左子樹(shù)中的最右節(jié)點(diǎn)
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;//給給變成該節(jié)點(diǎn)
}
else//結(jié)點(diǎn)的左子樹(shù)為空
{
//找孩子在祖先右邊的祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left) //判斷parent不為空，空就崩了
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator<T, T&, T*> iterator;//正向迭代器
iterator begin()
{
//尋找最左節(jié)點(diǎn)
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
//返回最左結(jié)點(diǎn)的正向迭代器
return iterator(left);
}
iterator end()
{
//返回空節(jié)點(diǎn)的迭代器
return iterator(nullptr);
}
//如果是空樹(shù)，則插入節(jié)點(diǎn)作為root節(jié)點(diǎn)
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//根節(jié)點(diǎn)必須是黑色
return make_pair(iterator(_root), true); //插入成功
}
//按二叉搜索樹(shù)的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(data) > kot(cur->_data))//待插入結(jié)點(diǎn)的key值大于當(dāng)前結(jié)點(diǎn)的key值
{
//往節(jié)點(diǎn)的右子樹(shù)走
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))//待插入結(jié)點(diǎn)的key值小于當(dāng)前結(jié)點(diǎn)的key值
{
//往節(jié)點(diǎn)的左子樹(shù)走
parent = cur;
cur = cur->_left;
}
else//插入的值等于當(dāng)前的節(jié)點(diǎn)，返回失敗
{
return make_pair(iterator(cur), false);
}
}
//將節(jié)點(diǎn)鏈接到樹(shù)上
cur = new Node(data);//構(gòu)造節(jié)點(diǎn)
Node* newnode = cur;
cur->_col = RED;
if (kot(data) < kot(parent->_data)) //判斷鏈接左還是右？
{
//插入到左邊
parent->_left = cur;
cur->_parent = parent;
}
else if (kot(data) > kot(parent->_data))
{
//插入到右邊
parent->_right = cur;
cur->_parent = parent;
}
//如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，則需要對(duì)紅黑樹(shù)進(jìn)行操作
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
assert(grandfather->_col == BLACK);
//關(guān)鍵看叔叔 ~ 判斷叔叔的位置
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情況1：uncle存在且為紅 + 繼續(xù)往上處理
if (uncle && uncle->_col == RED)
{
//變色：p和u變黑，g變紅
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//繼續(xù)往上調(diào)整
cur = grandfather;
parent = cur->_parent;
}
else //情況2 + 情況3：uncle不存在 + uncle存在且為黑
{
//情況二：?jiǎn)涡?+ 變色
// g
// p u
//c
if (cur = parent->_left)
{
RotateR(grandfather);//右旋
//顏色調(diào)整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_right
{
//情況三：左右雙旋 + 變色
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
//調(diào)整顏色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else //parent == grandfather->_right
{
Node* uncle = grandfather->_left;
//情況1：uncle存在且為紅 + 繼續(xù)往上處理
if (uncle && uncle->_col == RED)
{
//變色：p和u變黑，g變紅
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//繼續(xù)往上調(diào)整
cur = grandfather;
parent = cur->_parent;
}
else //情況2 + 情況3：uncle不存在 + uncle存在且為黑
{
//情況二：?jiǎn)涡?+ 變色
// g
// u p
// c
if (cur = parent->_right)
{
RotateL(grandfather);//左單 旋
//顏色調(diào)整
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur == parent->_left
{
//情況三：右左雙旋 + 變色
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
//調(diào)整顏色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;//不管什么，最后根要變黑
return make_pair(iterator(newnode), true);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout << "根節(jié)點(diǎn)不是黑色" << 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;//以最左的路徑進(jìn)行
}
return PrevCheck(_root, 0, benchmark);
}
private:
bool PrevCheck(Node* root, int blackNum, int& benchmark)
{
if (root == nullptr)
{
//cout << blackNum << endl;
//return;
if (benchmark == 0)
{
benchmark = blackNum;
return true;
}
if (blackNum != benchmark)
{
cout << "某條黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;
return false;
}
else
{
return true;
}
}
if (root->_col == BLACK)
{
++blackNum;
}
//檢測(cè)它的父親
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在連續(xù)的紅色節(jié)點(diǎn)" << endl;
return false;
}
return PrevCheck(root->_left, blackNum, benchmark)
&& PrevCheck(root->_right, blackNum, benchmark);
}
void _InOrder(Node* root)
{
if (root == nullptr)//空樹(shù)也是紅黑樹(shù)
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
//左單旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//建立subRL與parent之間的聯(lián)系
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//建立parent與subR之間的聯(lián)系
subR->_left = parent;
parent->_parent = subR;
//建立subR與parentParent之間的聯(lián)系
if (parentParent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
//右單旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//建立subLR與parent之間的聯(lián)系
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//建立parent與subL之間的聯(lián)系
subL->_right = parent;
parent->_parent = subL;
//建立subL與parentParent之間的聯(lián)系
if (parentParent == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
//左右雙旋
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}
//右左雙旋
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}
private:
Node* _root = nullptr;
};
??寫(xiě)在最后
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-806523.html
到了這里，關(guān)于【高階數(shù)據(jù)結(jié)構(gòu)】封裝Map和Set的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
