C++:map&set 对红黑树的封装
C++的STL库中,把红黑树封装为了两个容器map
与set
,本博客将基于红黑树,来实现map
和set
的封装。如果不了解红黑树,可见博客[数据结构/C++:红黑树]
将红黑树封装为泛型
我们现有如下结构的红黑树:
enum Colour
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
pair<K, V> _kv;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};
基本结构:RBTreeNode
是红黑树的节点,RBTree
则是红黑树本体,RBTree
内部的_root
是整颗红黑树的根。
这颗红黑树有一个问题,在于它的节点,存储的值是pair<K, V> _kv;
,也就是键值对的形式来存储数据。但是在STL中,set
是只存储key
值的,只有map
存储键值对。如果我们要使得红黑树可以同时作为map
和set
的底层,那么我们就要想办法让这个红黑树的节点可以存储多种类型的数据。也就是让节点RBTreeNode
内部存储泛型:
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data;
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
我们把原先的模板template<class K, class V>
换成了template<class T>
,并把pair<K, V> _kv;
改为了T _data;
,此时我们存储的数据就不一定是键值对的格式了。
当我们需要存储键值对,那么
T
就是pair<K, V>
当我们只存储key
值,那么T
就是K
相应的,我们的RBTree
主体也要修改一下:
template<class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
private:
Node* _root = nullptr;
};
现在我们先尝试对红黑树进行封装,写出一个map
和set
的基本框架:
mySet.h
:
template<class K>
class set
{
public:
private:
RBTree<K> _t;
};
myMap.h
:
template<class K, class V>
class map
{
public:
private:
RBTree<pair<K, V>> _t;
};
经过这一层封装,我们的map
和set
的基本框架就有了,但是有一个小问题:map
和set
中的key
值是不可以修改的,所以我们要给K的类型加上const
修饰。不过要注意map
中的value
是可以修改的,所以不是给pair
加上const
修饰,而是只修饰K。
mySet.h
:
template<class K>
class set
{
public:
private:
RBTree<const K> _t;
};
myMap.h
:
template<class K, class V>
class map
{
public:
private:
RBTree<pair<const K, V>> _t;
};
Find接口
到此为止,我们仅完成了基本框架的搭建,接下来我们看看红黑树的Find
接口:
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
cur = cur->_right;
else if (cur->_kv.first > key)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
以上Find
接口,是在红黑树没有修改前的接口,我们看看它目前有什么问题:
- 我们已经把模板从
template<class K, class V>
换成了template<class T>
,此时已经没有K
这个类型了,我们在给Find
传参的时候,不可以直接传const K& key
但是我们既然要在红黑树中查找,一定是要查key
的,也就是说,我们不可以遗漏K
这个类型,因此我们的模板参数要再加一个K
,变成:template<class K, class T>
。前面的K
用于传入key
的类型,后面的T
用于传入红黑树存储的数据类型。
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
private:
Node* _root = nullptr;
};
cur->_kv.first
这个过程是有问题的,其意图通过找到key
值,然后比较当前节点与查找节点的大小,来决定下一步去左子树还是右子树找节点。但是我们对RBTreeNode
改造后,其内部存储的已经不是_kv
了,而是_data
,对于set
而言,这个_data
是没有first
这个成员的,因此我们不能直接通过_kv.first
这种方式来访问key
。
这个问题的关键在于,我们想要拿到红黑树节点中的key
值,但是对于map
而言,这个key
是_data
中的成员变量first
;而对于set
而言,这个key
就是_data
。也就是map
和set
取用key
值的方式不同,我们无法统一处理。
为了解决这个问题,我们就要想办法,用统一的方式从_data
中获得map
和set
的key
。此时可以在红黑树的外部写仿函数,然后在仿函数的内部返回key
值。对于红黑树而言,不论是什么类型,只需要向仿函数传入_data
,然后接受返回值就可以拿到key
。
这里我们给红黑树传入第三个模板参数KeyOfT
:
template<class K, class T, class keyOfT>//keyOfT仿函数,取出T对象中的key
class RBTree
{
typedef RBTreeNode<T> Node;
public:
private:
Node* _root = nullptr;
};
接着就是set
的仿函数:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
对于set
而言,T
就是K
,也就是_data
的类型为K
,要从_data
中得到key
,直接返回_data
即可。
map
的仿函数:
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
对于map
而言,T
是pair<K, V>
,也就是_data
的类型为pair<K, V>
,要从_data
中得到key
,需要返回_data
的第一个成员first
。
然后我们再对Find
接口进行改造,把所有需要取用key
的地方都改用仿函数:
bool 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 true;
}
return false;
}
其中kot
就是仿函数keyOfT
实例化出的对象。
当前框架如下:
RBTree
:
template<class K, class T, class keyOfT>//keyOfT仿函数,取出T对象中的key
class RBTree
{
typedef RBTreeNode<T> Node;
public:
private:
Node* _root = nullptr;
};
mySet.h
:
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
myMap.h
:
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
bool find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
迭代器
先搭建出一个迭代器iterator
的基本框架:
template<class T, class Ptr, class Ref>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ptr, Ref> 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;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
在此我不讲解这个框架是如何搭建的了,如果不明白,可见博客[C++:迭代器的封装思想]
现在的主要问题在于:迭代器应该如何行动,走到下一个节点?
通过迭代器遍历与直接中序遍历一颗红黑树不一样,中序遍历可以通过递归,自动按照左子树 - 根 - 右子树
的顺序遍历。但是迭代器只知道当前节点,不知道前一步与后一步是谁。比如下图:
当前迭代器处于这个蓝色框中的节点,请问它下一步是往左子树走,右子树走,还是父节点走?
值得注意的是,当迭代器指向哪一个节点,说明当前就遍历到了哪一个节点,此时迭代器处于这个蓝色框中的节点,说明这个节点的左子树已经遍历完了,刚好遍历到这个蓝色框节点。因此下一步就是中序遍历右子树,即让迭代器走到当前节点的右子树位置,并且找到右子树的最左节点,该节点就是下一个节点。
但是如果右子树为空呢?
比如我们遍历到以下节点:
此时说明以蓝色框为根的整颗子树都遍历完毕了,那么我们就要向上移动,走到当前节点的父节点处:
但是对于这个父节点而言,其左子树遍历完了,刚刚右子树遍历完毕后,走到了当前节点,说明当前节点也遍历完毕了(中序遍历,根节点一定在右子树前遍历完),此时还要向上移动,以此类推,直到走到第一个当前节点是父节点的左子树的情况。
至此,我们就大概清除迭代器移动的情况了:
如果迭代器当前节点的右子树不为空,遍历右子树(找到右子树的最左节点)
如果迭代器当前节点的右子树为空,向上找前一个节点是当前节点的左子树的节点
代码如下:
Self& operator++()
{
if (_node->_right)//右不为空,找右子树最左节点
{
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else//右为空
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;//parent前一个节点cur是其左子树
}
return *this;
}
operator--
同理,只是相反的:
如果迭代器当前节点的左子树不为空,遍历左子树(找到左子树的最右节点)
如果迭代器当前节点的左子树为空,向上找前一个节点是当前节点的右子树的节点
代码如下:
Self& operator--()
{
if (_node->_left)//左不为空
{
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else//左为空
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;//第一个为cur右子树的祖先
}
return *this;
}
接下来我们要把迭代器的类封装进RBTree
中,首先定义出iterator
和const_iterator
:
typedef RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeIterator<T, const T*, const T&> const_iterator;
接着写出begin
,end
的接口:
直接拿空指针构造end
接口:
iterator end()
{
return iterator(nullptr);
}
要注意的是,begin
接口不是直接拿_root
去构造iterator
,中序遍历的第一个节点是整棵树的最左侧节点,所以要先找到最左侧节点,再构造:
iterator begin()
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}
return iterator(subLeft);
}
const_iterator
同理:
const_iterator begin() const
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}
return const_iterator(subLeft);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
接着我们再封装出map
和set
的迭代器,直接复用RBTree
的迭代器接口即可:
mySet.h
:
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();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
myMap.h
:
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();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
这里有一个注意点,在typedef
的时候,由于我们的RBTree
是一个模板,我们到模板的域中访问了变量。编译器无法区分模板中const_iterator
的是变量还是类型,所以编译器会默认把它视为一个变量。如果它是一个类型,那么我们要明确告诉编译器,即通过typename
关键词。不然const_iterator
会被识别为一个变量,而不是一个类型。
由于STL中,find
接口返回的是迭代器,现在我们已经实现了迭代器,所以我们还要把find
的返回值改为迭代器,而不是布尔值,这里不做展示了,可以到文章末尾的代码块中查看。
insert接口
在map
和set
中,insert
的返回值比较特殊,其会返回pair<iterator, bool>
如果插入值
data
原先存在,此时iterator
指向原先的data
节点,bool
值返回false
表示插入失败
如果插入值data
原先不存在,此时iterator
指向新插入的data
节点,bool
值返回true
表示插入成功
因此我们还要改一下Insert
接口:
如果插入成功:
return make_pair(iterator(newNode), true);
如果插入失败:
return make_pair(iterator(cur), false);
由于插入逻辑比较复杂,若需要看整段代码,可以在文章末尾查看。
map的operator[]接口
map
还重载了[]
,这个重载比较复杂,但是非常有用,我们先看到声明:
V& operator[] (const K& key);
其接收一个K
类型的参数,也就是接受一个key
,然后返回一个V&
,也就是一个value
的引用。其功能为:接受一个key
值,然后返回这个key
对应的value
的引用。
其等效于下面的代码:
(*((this->insert(make_pair(k,V()))).first)).second
现在我们来解读以上代码,我们将其拆解为四个部分:make_pair(k, V( ))
+ this->insert( )
+ ( ).first
+ (*( )).second
,我们一层层解析。
第一层:
make_pair(k, V( ))
可以看出,这是在利用参数
k
,通过make_pair
构造一个pair
,而这个pair
的value
使用了V( )
(V
就是value
的类型)来调用默认构造。这样我们最后就得到了一个pair<key, value>
。
第二层:
this->insert( )
上一层我们构造了一个
pair<key, value>
,然后它被作为参数,传入到这个insert
中,相当于把刚刚构造的节点插入进map
中。map
的插入后,不论成功与否,都会返回一个pair<iterator, bool>
,iterator
用于指向key
的迭代器,bool
用于标识插入是否成功。所以这一层最后得到了一个pair
,分别存储了指向key
的迭代器和bool
。
第三层:
( ).first
上一层中我们得到了
pair<iterator, bool>
,这一层访问它的first
,也就是访问了iterator
,所以这一层得到了指向key
值的迭代器。
第四层:
(*( )).second
我们上一层拿到了指向
key
的迭代器,这一层先对迭代器解引用*( )
,此时就得到了一个map
的节点。而map
的节点是pair<key, value>
,所以我们解引用得到了一个pair
,随后通过( ).second
访问pair<key, value>
的second
,也就是value
。最后返回这个value
的引用。
所以我们最后得到了key
对应的value
的引用。那么这有什么用呢?
假设我们有一个map<string, string>
类型的字典dict
,通过这个来展示operator[ ]
的功能:
- 插入一个key值:
dict["left"];
以上语句在dict
中插入了一个key = "left"
但是没有value
的节点
- 插入一对
key - value
:
dict["left"] = "左边";
由于operator[ ]
返回的是对应的引用,因此我们可以直接给返回值赋值,此时我们就插入了一个节点key = "left" - value = "左边"
- 修改
key
对应的value
:
dict[“coffe”] = "咖啡";
如果我们的dict
原先就存在key = "coffe"
的节点,以上代码可以修改这个key
的value
值
- 得到
key
对应的value
:
cout << dict["coffe"] << endl;
由于我们拿到的是value
的引用,我们也可以把它作为一个值赋值给别人或者输出
可以看到,operator[]
的功能非常丰富,整体来说还是一个很好用的重载。
operator[]实现:
由于我们先前已经用insert
铺垫好了,我们直接调用insert
,然后返回value
的引用即可:
V& operator[](const K& key)
{
pair<K, V>& ret = insert(make_pair(key, V()));
return ret.first->second;
}
总代码展示
RBTree.h
:
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data;
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
template<class T, class Ptr, class Ref>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ptr, Ref> Self;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_right)//右不为空
{
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else//右为空
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;//第一个为cur左子树的祖先
}
return *this;
}
Self& operator--()
{
if (_node->_left)//左不为空
{
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else//左为空
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;//第一个为cur右子树的祖先
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template<class K, class T, class keyOfT>//keyOfT仿函数,取出T对象中的key
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeIterator<T, const T*, const T&> const_iterator;
iterator begin()
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}
return iterator(subLeft);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}
return const_iterator(subLeft);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//保持根为黑节点
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Node* parent = nullptr;
keyOfT kot;
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);
}
}
cur = new Node(data);
if (kot(parent->_data) > kot(data))
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
Node* newNode = cur;
while (parent && parent->_col == RED)//只有parent为红,才更新 (parent可能不存在)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//uncle存在且为红节点
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else//uncle不存在或为黑节点 (旋转)
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//旋转后一定平衡
}
}
else
{
Node* uncle = grandfather->_left;
//uncle存在且为红节点
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else//uncle不存在或为黑节点 (旋转)
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//旋转后一定平衡
}
}
}
_root->_col = BLACK;//在循环内部不判断root情况,统一处理
return make_pair(iterator(newNode), true);
}
//左单旋
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;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
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;
}
}
size_t Size()
{
return _Size(_root);
}
size_t _Size(Node* root)
{
if (root == nullptr)
return 0;;
return _Size(root->_left) + _Size(root->_right) + 1;
}
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();
}
//--------------------------------------------------------------------------------------------------------------
//中序
void InOrder()
{
_InOrder(_root);
cout << "end" << endl;
}
private:
//中序
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " - ";
_InOrder(root->_right);
}
Node* _root = nullptr;
};
mySet.h
:
#pragma once
#include "RBTree.h"
namespace mySet
{
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();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
}
myMap.h
:
#pragma once
#include "RBTree.h"
namespace myMap
{
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();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<K, V>& ret = insert(make_pair(key, V()));
return ret.first->second;
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}
标签:黑树,map,const,cur,parent,对红,key,return,iterator
From: https://blog.csdn.net/fsdfafsdsd/article/details/136767956