【C++】--封装红⿊树实现mymap和myset
我们前面学习map和set的使用的时候，知道set是对应我们的key问题，然后map对应的是我们的key和value问题，所以这两者存储的数据是不一样的，然后其二者的底层又是使用的红黑树实现的，那么我们是否需要去对应其存储的数据的特点，然后分别弄一个红黑树呢？可以看到源码中，set和map是用的同一个红黑树。不过set中的红黑树的pair存储的数据是这样的：pair<K,K>。其让两个数据都存储k
一、map和set的源码和框架分析
我们前面学习map和set的使用的时候，知道set是对应我们的key问题，然后map对应的是我们的key和value问题，所以这两者存储的数据是不一样的，然后其二者的底层又是使用的红黑树实现的，那么我们是否需要去对应其存储的数据的特点，然后分别弄一个红黑树呢？
下面我们看看源码中是如何操作的：
set.h:
map.h：
可以看到源码中，set和map是用的同一个红黑树。
不过set中的红黑树的pair存储的数据是这样的：pair<K,K>。其让两个数据都存储key。
然后map中的pair就一个存储key一个存储value。
二、实现的基本框架
首先是我们的红黑树的框架，我们通过模板参数来控制。
我们节点存储的数据通过模板控制一个泛型，那么其可以传入一个pair类。
然后我们的树类，我们就使用两个模板参数，这是为了在一些成员函数需要单独使用key的时候使用的。
那么我们来看看set的结构：
可以看到我们在set中的红黑树的结点创建中传入的是两个参数，都是K。
下面是map的结构：
我们在map结构中的第二个模板参数传入的是一个pair。
三、insert插入的比较逻辑
我们知道无论是啥情况，我们的数据插入要比较的是关键码key。那么我们在插入函数中要如何进行比较呢?
首先就是我们的pair中是否有提供比较的逻辑，那么我们去库中看看：
// 小于操作符 < 的实现
template<class T1, class T2>
template<class U1, class U2>
bool pair<T1, T2>::operator<(const pair<U1, U2>& p) const {
// 先比较 first，如果 first 不同，直接返回结果
if (first < p.first) return true;
if (p.first < first) return false;
// first 相等时，再比较 second
return second < p.second;
}
// 等于操作符 == 的实现
template<class T1, class T2>
template<class U1, class U2>
bool pair<T1, T2>::operator==(const pair<U1, U2>& p) const {
return first == p.first && second == p.second;
}
// 不等于操作符 != 的实现
template<class T1, class T2>
template<class U1, class U2>
bool pair<T1, T2>::operator!=(const pair<U1, U2>& p) const {
return !(*this == p);
}
// 大于操作符 > 的实现
template<class T1, class T2>
template<class U1, class U2>
bool pair<T1, T2>::operator>(const pair<U1, U2>& p) const {
return p < *this;
}
// 小于等于操作符 <= 的实现
template<class T1, class T2>
template<class U1, class U2>
bool pair<T1, T2>::operator<=(const pair<U1, U2>& p) const {
return !(p < *this);
}
// 大于等于操作符 >= 的实现
template<class T1, class T2>
template<class U1, class U2>
bool pair<T1, T2>::operator>=(const pair<U1, U2>& p) const {
return !(*this < p);
}可以看到在库中pair的比较大小其实不适合我们红黑树中所需要的比较逻辑。
而且还有一个问题就是我们的红黑树是泛型实现的，那么存储的数据可能也不是pair，那么我们就要想个更好的方法了。
所以我们前面学习的仿函数在此处就起作用了，我们可以在set和map中分别实现一个SetKeyOfT、MapKeyOT。然后在RBTree中再添加一个模板参数KeyOfT仿函数，用来取出T类型对象中的key，然后进行比较。
在我们的红黑树的模板参数中添加多了一个仿函数模板参数。
然后我们在set和map的封装中，对于树的实例化中，我们将其对应的函数传入。
然后我们在红黑树中，对于数据的比较逻辑就可以通过仿函数提取出存储在pair中的key来进行比较了。
如上所示，通过实例化出仿函数的实例化对象，那么就可以使用其取得key了。
三、set和map迭代器的实现
iterator的实现思路大体上和list的iterator的是一致的，然后我们用一个类封装节点的指针，然后通过运算符重载的形式实现。
我们这里的迭代器的难点是operator++和operator--的实现。前面我们学习map和set的使用的时候，知道map和set的遍历走的是中序遍历：左根右的顺序，然后其begin()返回的是中序遍历的第一个节点的迭代器。
我们可以先在一个子树中来看迭代器++操作的逻辑，我们只考虑在一个子树中++，要如何找下一个节点。
迭代器++时，如果it指向的结点的右⼦树不为空，代表当前结点已经访问完了，要访问下⼀个结点 是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。
如上图，我们访问10的时候，其右边子树是非空的，那么我们就去右边子树找最小的，那么其最小的在最左边。
迭代器++时，如果it指向的结点的右⼦树空，代表当前结点已经访问完了且当前结点所在的⼦树也 访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上 找
那么此时我们it在25这个节点的话，那么其右边是空的，那么就表示我们当前节点的这个子树已经遍历完了，那么就要往根去走了。
如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结 点的⽗亲；如下图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。
如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前结点所在的⼦树访问完 了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找 到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。如下图：it指向15，15右为空，15是10 的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个 访问的结点就是18。
如果当前结点是⽗亲的右，根据中序左⼦树->根结点->右⼦树，当前当前结点所在的⼦树访问完 了，当前结点所在⽗亲的⼦树也访问完了，那么下⼀个访问的需要继续往根的祖先中去找，直到找 到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。如下图：it指向15，15右为空，15是10 的右，15所在⼦树话访问完了，10所在⼦树也访问完了，继续往上找，10是18的左，那么下⼀个 访问的结点就是18。
end()如何表⽰呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18 到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这是⽗亲为空了，那我们就把it中的结点指针 置为nullptr，我们⽤nullptr去充当end。需要注意的是stl源码空，红⿊树增加了⼀个哨兵位头结点 做为end()，这哨兵位头结点和根互为⽗亲，左指向最左结点，右指向最右结点。相⽐我们⽤ nullptr作为end()，差别不⼤，他能实现的，我们也能实现。只是--end()判断到结点时空，特殊处 理⼀下，让迭代器结点指向最右结点。具体参考迭代器--实现。
迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点-> 左⼦树，具体参考下⾯代码实现。
然后要注意的是map和set的迭代器都不支持修改。
代码如下：
四、operator[]
前面我们学习map的时候知道map支持[]实现数据的插入和修改的操作。那么我们的插入的话，就是复用我们的insert接口了。
[]的话其工作规则如下：
如果插入成功，那么返回的是一个pair的数据<插入数据对应的迭代器，true>。
如果插入失败，那么返回<返回已经存在的数据对应的迭代器，false>。
所以前面我们实现的红黑树中，其底层存储的数据类型我们时候pair也是有原因的。
五、完整代码
#pragma once
#include<utility>
#include<iostream>
//RBTree.h
using namespace std;
enum color
{
Red,
Black
};
template<class T>
struct RBTreeNode
{
T _date;
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
color _co;
RBTreeNode(const T&date)
:_date(data),
_parent(nullptr),
_left(nullptr),
_right(nullptr),
_co(Red)
{
}
};
template<class T, class Ref, class Ptr>
struct TreeIterator
{
typedef RBTreeNode<T> Node;
typedef TreeIterator<T, Ref, Ptr> Self;
Node* _node;
TreeIterator(Node* node)
:_node(node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator== (const Self& s) const
{
return _node == s._node;
}
Self& operator--()
{
// ...
return *this;
}
Self& operator++()
{
// 当前节点右不为空，下一个就是右子树的中序第一个（最左节点）
// 当前节点右为空，下一个孩子是父亲左的那个祖先节点
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
//此处的K是key，T是要存储的数据，这是为了map和set都可以用
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef TreeIterator<T, T&, T*> Iterator;
typedef TreeIterator<T, const T&, const T*> ConstIterator;
Iterator Begin()
{
Node* min = _root;
while (min && min->_left)
{
min = min->_left;
}
return Iterator(min);
}
Iterator End()
{
return Iterator(nullptr);
}
pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return { Iterator(_root), true };
}
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
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 { Iterator(cur), false };
}
}
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// 叔叔存在且为红->变色
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 叔叔不存在，或者叔叔存在且为黑->旋转+变色
{
if (cur == parent->_left)
{
// g
// p u
//c
// 右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
// 左右单旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // grandfather->_right == parent
{
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔存在且为红，-》变色即可
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 叔叔不存在，或者存在且为黑
{
// 情况二：叔叔不存在或者存在且为黑
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{ // g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return { Iterator(newnode), true };
}
Node* 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 cur;
}
}
return nullptr;
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
private:
Node* _root = nullptr;
};
#pragma once
#include"RBTree.h"
//myset.h
namespace cyy
{
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;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
pair<iterator, bool> Insert(const T& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K,SetKeyOfT>_t;
};
}#pragma once
#include"RBTree.h"
//mymap.h
namespace cyy
{
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;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
private:
RBTree<K, pair<K,V>,MapKeyOfT>_t;
};
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
30
0- 0
已为社区贡献1条内容
所有评论(0)