红黑树封装map和set（c++版）
前言
在前面，我们介绍了c++中map和set库的使用，也实现了一颗简单的红黑树。那么现在我们就利用这两部分的知识，实现一个简单的myMap和mySet。
源码阅读
在我们实现之前，我们可以阅读一些标准库的实现，学习标准库的实现思路。这里我们选取的是SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等⼏个头⽂件
中
下面我们就分别把这几个头文件中核心代码拎出来阅读一下
// set
#ifndef __SGI_STL_INTERNAL_TREE_H //条件编译
#include <stl_tree.h> //红黑树
#endif
#include <stl_set.h> //不允许键值冗余
#include <stl_multiset.h> //允许键值冗余// map
#ifndef __SGI_STL_INTERNAL_TREE_H //条件编译
#include <stl_tree.h> //红黑树
#endif
#include <stl_map.h> //不允许键值冗余
#include <stl_multimap.h> //允许键值冗余我们发现map和set都是包含其他头文件，调用其他头文件的实现，这里也是再封装一层的体现，方便调用者的使用
// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // 表示set的红黑树
};// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
typedef Key key_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; //表示map的红黑树
};Key是键；T是map中值的值；Compare是一个比较的仿函数，通过传入不同的仿函数，实现降序或升序；Alloc是空间配置器，我们不关注
不难发现，map和set共用了同一颗红黑树，这颗红黑树存在的是键值对。对于set来说键和值都是Key，对于map来说键是Key值是pair<const Key, T>的一个容器，作用是保证Key值不被修改
identity<value_type>和select1st<value_type>是两个仿函数，作用是从value_type类型中取出Key值的大小，本质上就是兼容上的处理，这个我们在后面还会展开。同理set传入两个Key类型给tree也是兼容上的处理。
下面我们就可以来看一下tree的实现
我们可以先来看看treeNode节点的实现
struct __rb_tree_node_base //节点的基类，定义了节点颜色，左右子节点和父节点这样的基础信息
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
};
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base//继承基类，添加节点存储的值
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
}；下面我们看一下tree的实现
// stl_tree.h
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc
= alloc>
class rb_tree {
protected:
typedef void* void_pointer;
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
typedef rb_tree_node* link_type;
typedef Key key_type;
typedef Value value_type;
public:
// insert⽤的是第⼆个模板参数左形参
pair<iterator,bool> insert_unique(const value_type& x); //插入，不允许键值冗余
// erase和find⽤第⼀个模板参数做形参
size_type erase(const key_type& x); //删除
iterator find(const key_type& x); //查找
protected:
size_type node_count; //记录树节点的数量
link_type header; //根节点
};我们发现这里的命令还是比较混乱的，我们建议后续的实现中，将键值定义为Key和Value，将红黑树存储的值定义为T，统一命名风格。我们这里也修改为这种命名风格
红黑树的实现
这里红黑树的实现我们复用我们之前实现的代码，这里实现的具体细节我们不在展开，需要进一步了解的可以查阅我们之前的博客
定义颜色
enum Color //颜色枚举
{
RED, //红
BLACK //黑
};定义节点
template<class T>
class RBTreeVal
{
template<class K, class T,class KFromT>
friend class RBTree; //将红黑树提前声明为友元类，方便红黑树使用节点
template<class T, class Ref,class Ptr>
friend class RBTreeIterator; //将迭代器提前声明为友元类，方便迭代器使用节点
public:
RBTreeVal(const T& t) //构造函数
:_t(t)
{}
private:
//左右子节点和父节点
RBTreeVal<T>* _left = nullptr;
RBTreeVal<T>* _right = nullptr;
RBTreeVal<T>* _parent = nullptr;
//存储数据
T _t = T();
//节点默认为红色
Color _col = RED;
};这里我们在实现迭代器的时候使用了模板，是普通迭代器和const迭代器复用同一个类，等到具体实现的时候我们会再介绍一次
KFromT是从T类型中得到K值的仿函数
定义红黑树
首先我们需要将红黑树的框架搭好
template<class K,class T,class KFromT>
class RBTree
{
typedef RBTreeVal<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;//普通迭代器
typedef RBTreeIterator<T, const T&, const T*> constIterator;//const迭代器
private:
Node* _root=nullptr; //根节点
};这里我们现将迭代器定义好，在后面再展开实现
加入红黑树旋转的逻辑
//左单选
void rotateL(Node*par)
{
Node* chi = par->_right;
Node* chiL = chi->_left;
par->_right = chiL;
if (chiL != nullptr)
{
chiL->_parent = par;
}
chi->_parent = par->_parent;
chi->_left = par;
par->_parent = chi;
if (chi->_parent != nullptr && chi->_parent->_left == par)
{
chi->_parent->_left = chi;
}
else if (chi->_parent != nullptr && chi->_parent->_right == par)
{
chi->_parent->_right = chi;
}
if (_root == par)
{
_root = chi;
}
}
//右单旋
void rotateR(Node* par)
{
Node* chi = par->_left;
Node* chiR = chi->_right;
par->_left = chiR;
if (chiR != nullptr)
{
chiR->_parent = par;
}
chi->_parent = par->_parent;
chi->_right = par;
par->_parent = chi;
if (chi->_parent != nullptr && chi->_parent->_left == par)
{
chi->_parent->_left = chi;
}
else if (chi->_parent != nullptr && chi->_parent->_right == par)
{
chi->_parent->_right = chi;
}
if (_root == par)
{
_root = chi;
}
}
//右左双旋
void rotateRL(Node* par)
{
Node* chi = par->_right;
rotateR(chi);
rotateL(par);
}
//左右双旋
void rotateLR(Node* par)
{
Node* chi = par->_left;
rotateL(chi);
rotateR(par);
}
统一接口的风格，传入旋转的支点节点就可以实现旋转
我想我们可能需要先实现迭代器，因为插入，寻找可能都需要用到迭代器
我们先搭建一个迭代器的框架
template<class T,class Ref,class Ptr>
class RBTreeIterator
{
typedef RBTreeVal<T> Node;
typedef RBTreeIterator<T,Ref,Ptr> Self;
template<class K, class T, class KFromT>
friend class RBTree;
public:
RBTreeIterator(Node* node=nullptr,Node* root = __nullptr)
:_node(node),
_root(root)
{}
private:
Node* _node = nullptr;//当前节点
Node* _root = nullptr;//根节点，
};
这里我们把迭代器就是封装一层Node*，采用中序遍历的方式，遍历结果是有序的
下面我们就可以加入迭代器++的逻辑
这里++的逻辑可能比较复杂，要分两种情况，如果此迭代器还有右子节点，则找右子树中的最左节点；如果此节点没有右节点，则代表这个节点所在的这颗子树是某个祖先节点的左子树，而左子树已经遍历完，这个祖先节点就是++后的下一个节点，或者这是最后一个有效节点此时会返回一个nullptr标记的迭代器
我们按照这个逻辑完成迭代器++
Self operator++()
{
if (_node->_right != nullptr)
{
Node* cut = _node->_right;
while ( cut->_left)
{
cut = cut->_left;
}
_node = cut;
return *this;
}
Node* par = _node->_parent;
Node* chi = _node;
while (par != nullptr)
{
if (par->_left == chi)
{
_node = par;
return *this;
}
chi = par;
par = par->_parent;
}
_node = nullptr;
return *this;
}--的逻辑和++的逻辑为镜像，注意的是，如果用到nullptr的迭代器则返回最后一个有效的节点，此时需要用到_root，如果是根节点--则返回nullptr节点
Self operator--()
{
if (_node == nullptr)
{
Node* cut = _root;
while (cut && cut->_right)
{
cut = cut->_right;
}
_node = cut;
return *this;
}
if (_node->_left != nullptr)
{
Node* cut = _node->_left;
while (cut->_right)
{
cut = cut->_right;
}
_node = cut;
return *this;
}
Node* par = _node->_parent;
Node* chi = _node;
while (par != nullptr)
{
if (par->_right == chi)
{
_node = par;
return *this;
}
chi = par;
par = par->_parent;
}
_node = nullptr;
return *this;
}实现迭代器 == 和 != 比较的逻辑，只需要比较地址是否相同即可
bool operator!=(const Self& s) const
{
return s._node != _node;
}
bool operator==(const Self& s) const
{
return s._node == _node;
}在加入迭代器取值的操作 * 和 ->
Ref operator*()
{
return _node->_t;
}
Ptr operator->()
{
return &_node->_t;
}
有了这些，我们就可以在红黑树中实现普通迭代器和const迭代器的begin和end了
Iterator begin()
{
if (_root == nullptr)
{
return Iterator(nullptr,_root);
}
Node* cut = _root;
while (cut->_left != nullptr)
{
cut = cut->_left;
}
return Iterator(cut, _root);
}
constIterator begin() const
{
if (_root == nullptr)
{
return constIterator(nullptr, _root);
}
Node* cut = _root;
while (cut->_left != nullptr)
{
cut = cut->_left;
}
return constIterator(cut, _root);
}
Iterator end()
{
return Iterator(nullptr, _root);
}
constIterator end() const
{
return constIterator(nullptr, _root);
}我们接着实现插入元素的逻辑。
插入节点传入的参数是T类型，仿函数KFromT会从T类型中返回K的值，返回值遵从标准库返回一个pair<Iterator,bool>，迭代器指向插入元素的位置，bool值返回插入是否成功，如果存在则返回失败，插入的逻辑和红黑树插入的逻辑相同，这里就不展开了
//插入元素
pair<Iterator,bool> insert(const T& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return { Iterator(_root,_root),true };
}
Node* chi = _root;
Node* par = nullptr;
KFromT tToK;
while (chi !=nullptr)
{
if (tToK(kv) > tToK(chi->_t))
{
par = chi;
chi = chi->_right;
}
else if (tToK(kv) < tToK(chi->_t))
{
par = chi;
chi = chi->_left;
}
else if (tToK(kv) == tToK(chi->_t))
{
//已经存在
return { Iterator(chi, _root), false };
}
else
{
assert(false);
}
}
chi = new Node(kv);
Node* rem = chi;
chi->_parent = par;
if (tToK( par->_t) > tToK(kv))
{
par->_left = chi;
}
else if (tToK(par->_t) < tToK(kv))
{
par->_right = chi;
}
else
{
assert(false);
}
while (par !=nullptr && par->_col != BLACK)
{
Node* gra = par->_parent;
if (gra == nullptr)
{
break;
}
Node* unc = nullptr;
if (gra->_left == par)
{
unc = gra->_right;
}
else if (gra->_right == par)
{
unc = gra->_left;
}
else
{
assert(false);
}
//叔叔存在且为红
if (unc != nullptr && unc->_col == RED)
{
unc->_col = BLACK;
par->_col = BLACK;
gra->_col = RED;
chi = gra;
par = chi->_parent;
}
else if (unc == nullptr || unc->_col == BLACK)
{
//右单旋
if (chi == par->_left && par == gra->_left)
{
rotateR(gra);
gra->_col = RED;
par->_col = BLACK;
}
//右左双旋
else if(chi == par->_left && par == gra->_right)
{
rotateRL(gra);
chi->_col = BLACK;
gra->_col = RED;
}
//左右双旋
else if (chi == par->_right && par == gra->_left)
{
rotateLR(gra);
chi->_col = BLACK;
gra->_col = RED;
}
//左单旋
else if (chi == par->_right && par == gra->_right)
{
rotateL(gra);
gra->_col = RED;
par->_col = BLACK;
}
else
{
assert(false);
}
break;
}
else
{
assert(false);
}
}
_root->_col = BLACK;
return { Iterator(rem,_root),true };
}查找的逻辑比较简单，和插入找合适位置的逻辑相似，返回对应的迭代器，不存在则返回最后一个元素迭代器的下一个位置标识即可，这里也不展开实现了
删除的代码我们也不再展开了，我们在红黑树的介绍中介绍过删除的逻辑，还是比较复杂的，感兴趣的读者可以自行找其他资料查看
map封装
这里我们就可以分装map了
template<class K,class V>
class Map
{
private:
struct KOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
RBTree<K, pair<const K, V>, KOfT> map;
public:
typedef typename RBTree<K, pair<const K, V>, KOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, KOfT>::constIterator c_iterator;
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return map.insert(kv);
}
iterator begin()
{
return map.begin();
}
iterator end()
{
return map.end();
}
c_iterator begin() const
{
return map.begin();
}
c_iterator end() const
{
return map.end();
}
};我们在实现一个重载[]的方法
V& operator[](const K& key)
{
pair<iterator, bool> ret = map.insert({key,V()});
return ret.first->second;
}set封装
template<class K>
class Set
{
private:
struct KOfT
{
const K& operator()(const K& kv)
{
return kv;
}
};
RBTree<K, const K, KOfT> set;
public:
typedef typename RBTree<K, const K, KOfT>::Iterator iterator;
typedef typename RBTree<K, const K, KOfT>::constIterator c_iterator;
pair<iterator,bool> insert(const K& kv)
{
return set.insert(kv);
}
iterator begin()
{
return set.begin();
}
iterator end()
{
return set.end();
}
c_iterator begin() const
{
return set.begin();
}
c_iterator end() const
{
return set.end;
}
};结语
这里实现的代码还是非常简陋的，只是搭好了一个框架，后续还可以进行升级和加入新的逻辑，本文只是抛砖引玉，更复杂的代码和逻辑我们就不再展开了
以上便是今天的全部内容。如果有帮助到你，请给我一个免费的赞。
因为这对我很重要。
编程世界的小比特，希望与大家一起无限进步。
感谢阅读！