为了map与set 的封装,我们进行了非常充足的知识储备!!!
首先,为了了解map 与 set 的底层原理我们开始学习二叉搜索树,二叉搜索树在二叉树的基础上增添了:
这样可以在一定程度上满足高效搜索的需求,但是在极端的情况(单子树情况)其效率会下降到O(n)。因此就有了改进的二叉搜索树:AVL树和红黑树。他们都增加一些特性使其最大程度上近似平衡二叉树!
AVL 树 和 红黑树 都是在保持二叉搜索树基本性质的基础上,通过旋转和重新平衡等操作,确保树的高度保持在一个相对平衡的状态,从而保证了操作的时间复杂度始终为 O(logn)。它们的出现大大提高了二叉搜索树在实际应用中的性能和稳定性。
AVL树增加了以下特性:
在平衡因子超出要求就会进行旋转,旋转分为:右单旋 ,左单旋,左右双旋,右左双旋。
红黑树加入以下特性:
在不满足规则时也会进行旋转。但是旋转的频率比AVL树要少很多,红黑树是只是接近平衡,AVL树几乎就是平衡的!
map与set大多数情况是用来检索的工具,我们底层使用红黑树来完成map与set的封装。
进行封装之前,我们先来实现一个非常重要的东西:迭代器
迭代器的好处是可以方便遍历。如果想要给红黑树增加迭代器,需要考虑以前问题:
接下来我们来逐个实现。
首先我们来搭建一下迭代器的框架
// 迭代器
//T 表示数据类型 Ref为引用 Ptr为指针
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;
}
bool operator!= (const Self& s)
{
return _node != s._node;
}
};
接下来我们来实现++和–的操作。
中序遍历的顺序是先遍历左边再遍历当前节点最后是右子树。所以在跌迭代器指向当前节点的时候,说明当前节点的左子树已经遍历完了,如果++,就要去找右边的最左节点。如果没有右子树,说明该节点以下的部分已经遍历完了,接下来要去向上进行,找到是祖先左边的节点:
//迭代器的++ 中序遍历的顺序
Self& operator++()
{
//首先,能访问到当前节点说明左子树的都已经访问过啦
//所以就要分类讨论
//如果右边有子树,就要去寻找右子树的最左节点
if (_node->_right)
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
//如果右边没有子树了,说明该节点以下的子树都已遍历完,那么就要向上进行
//找到祖先节点(注意祖先节点右边还没遍历)
//此时也要进行分类讨论
else
{
Node* cur = _node;
Node* parent = _node->_parent;
//_node == parent->_right
//说明parent的节点已经访问过了
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
–与++完全相反。
这样红黑树的迭代器就成功设置好了,我们的红黑树更加完美了!!!
实现了迭代器接下来我们就来实现map与set的封装
我们先来看我们写的红黑树的节点代码:
// 节点结构体
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
pair<K, V> _kv;
color _col;
RBTreeNode(pair<K, V> kv)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(kv),
_col(Red)
{}
};
可以发现,这个节点的设置是写死的,里面的数据就设置为了pair<K , V>
。如果我们想实现set的封装还要在写一份红黑树代码,因为set的节点数据是K
。这样就太不优雅了!
为了更好实现map与set的封装,我们来看STL源码里是如何实现的吧!
可以看到STL源码中使用了非常巧妙的模版来支持我们上层的map与set:
value
,用来表明储存什么数据类型,上层的红黑树通过什么value
就使用使用什么Key Value KeyOfValue
: K V
和 K
分别要提供给红黑树Key Value KeyOfValue
: <K , pair<K,V> ...>
<K , K ...>
这样实现了上层的map
与set
的模版参数并不一样,却可以使用同一个底层红黑树代码!!!十分巧妙!!!
我们按照源码改进我们的红黑树:
//-------------------------------------------
//---------------- 红黑树实现 -----------------
//-------------------------------------------
//-------- 适配map 与 set 的进阶版本 -----------
//-------------------------------------------
#include<utility>
enum color
{
Black,
Red
};
// 节点结构体
// T在这里是 pair<key , value>
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
color _col;
RBTreeNode(T data)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_data(data),
_col(Red)
{}
};
//适配map与set 的版本
// 迭代器
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;
}
bool operator!= (const Self& s)
{
return _node != s._node;
}
//迭代器的++ 中序遍历的顺序
Self& operator++()
{
}
Self& operator--()
{
}
};
//K 为键值 T 为储存的结构(pair<K ,V>) KeyOfValue 是取出Key的方式
template<class K, class T , class KeyOfValue>
class RBTree
{
public:
typedef _RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeNode<T> Node;
Iterator begin()
{
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return Iterator(cur);
}
Iterator end()
{
return Iterator(nullptr);
}
//右单旋
void RotateR(Node* parent)
{
}
//左右双旋
void RotateLR(Node* parent)
{
}
//右左双旋
void RotateRL(Node* parent)
{
}
//------------------
//返回需要比较的值
KeyOfValue kot;
//------------------
//插入函数
bool Insert(T data)
{
}
private:
void _IsBalance(Node* root , int num)
{
}
bool Check(Node* root, int blackNum, const int refNum)
{
}
void _InOrder(Node* cur)
{
}
RBTreeNode<T>* _root = nullptr;
};
注意插入函数等里面的比较方式统一改成类似kot(data) < kot(node.data)
的样子哦!!!因为map与set的取出key的方式不同!!!
实现了红黑树的改进,接下来就简单了!
在上层操作我们只需要调用对应的底层代码,给予对应的模版参数就好了!!!
K V
的模版参数的传入<K , pair<const K , V> , MapOfValue>
(注意键值不可更改哦,所以使用pair<const K , V>)++ -- !+
交给迭代器操作交给红黑树的迭代器。//----------------------------------
//---------- MAP 的实现 -----------
//----------------------------------
#include"RBTree.h"
#include<utility>
//层层递进,
//map 上层要提供 key value 键值对
//相应的要改造红黑树的代码 使其满足泛型编程
template<class K , class V>
class map
{
struct MapOfValue
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapOfValue>::Iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
bool Insert(pair<const K, V> kv)
{
return _t.Insert(kv);
}
void InOrder()
{
_t.InOrder();
}
private:
//底层是红黑树
//需要提供对应的键值 储存结构 比较方式
RBTree<K, pair<const K, V>, MapOfValue > _t;
};
这样就实现了map 的封装!!!
在上层操作我们只需要调用对应的底层代码,给予对应的模版参数就好了!!!
K
的模版参数的传入<K , const K , MapOfValue>
(注意键值不可更改哦,所以使用 const K )++ -- !+
交给迭代器操作交给红黑树的迭代器。//----------------------------------
//---------- SET 的实现 -----------
//----------------------------------
#include"RBTree.h"
#include<utility>
//层层递进,
//set 上层要提供 key 键值
//相应的要改造红黑树的代码 使其满足泛型编程
template<class K>
class set
{
struct SetOfValue
{
const K& operator()(const K& k)
{
return k;
}
};
public:
typedef typename RBTree<K, const K, SetOfValue>::Iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
bool Insert(K kv)
{
return _t.Insert(kv);
}
void InOrder()
{
_t.InOrder();
}
private:
//底层是红黑树
//需要提供对应的键值 储存结构 比较方式
RBTree<K, K, SetOfValue > _t;
};
这样就实现了set的封装!!!
通过近一周的学习,我们终于将map和set从零建立起来了,这里不仅需要二叉搜索树的知识还需要AVL树和红黑树的使用!!!甚至还需要对于模版的更深理解!!!
我们写完了发现上层的map和set并没有使用多少代码,大部分是调用底层的代码,所以只有根基稳固才能走到更远!!!
map和set的封装是很值得回味的内容!!!