一.红黑树
1.红黑树的迭代器
迭代器是一个相对来说比较复杂得东西.首先我们知道模拟得迭代器,实际上就是一个节点得指针.包含++,-- 以及对节点得基本操作.
template<class T , class ref, class ptr>
struct _rb_iterator
{
typedef RBTreeNode<T> Node;
typedef _rb_iterator<T, ref, ptr> self;
Node* _node;
Node* _root;
_rb_iterator(Node* node, Node* root = nullptr)
:_node(node),_root(root)
{ }
typedef _rb_iterator<T, T&, T* > iterator;
//无论模板构造的是_rb_iterator<T, T&, T* > 还是_rb_iterator<T, const T&, const T* >
///iterator都是_rb_iterator<T, T&, T* >
//这就是实现了 ,将普通迭代器,转换为从上图迭代器.
_rb_iterator(const iterator& it)
:_node(it._node),_root(it._root){
}
//原本的迭代器是,const迭代器和 普通迭代器不是相同的类型,不是同一个类型的东西.
//这里使用了将一个普通迭代器 构造出来一个const迭代器
ref operator*()
{
return _node->_data;
}
ptr operator->()
{
return &(_node->_data);
}
self& operator++()
{
//迭代器在当前节点的时候说明左子树已经全部 遍历完成,
//下一步是 右子树或者 祖先节点(nullptr)
if (_node == nullptr)
{
cout << "end() 不能 ++" << endl;
return *this;
}
if (_node->_right != nullptr)
{
//下一步是遍历右子树的最小节点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else {
//下一步是遍历祖先.
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left != cur)
{
cur = cur->_parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
self& operator--()
{
//这里假设 end() 和 iterator(nullptr)相同
if (_node == nullptr)
{
//就是本来是 : end() ,现在需要 --
Node* root = _root;
while (root->_right)
{
root = root->_right;
}
_node = root;
return *this;
}
//node 不是空
if (_node->_left)
{
//node的左节点不是空
//找到左树的最大节点
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && parent->_left == cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};前面是迭代器基本得具体实现,其中得++和--得逻辑很新,建议反复观看,怎么通过父指针找到下一个节点.
2.红黑树的修改
前面的文章中我们讲解了红黑树的结构和实现.这一节课我们直接使用上一个文章中实现的红黑树,因为set和map都是底层都是使用红黑树实现的,而且使用的都是同一个红黑树模板实现的,这里就要稍微修改一下我们上节课实现的红黑树模板了,使他能够实现set和map共用一个红黑树.
template <class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
//这个需要共有化,因为在外部需要从定义.
typedef _rb_iterator<T, T&, T*> iterator;
typedef _rb_iterator<T, const T&, const T*> const_iterator;
RBTree()
:_root(nullptr)
{}
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
cout << "iterator begin" << endl;
return iterator(cur, _root);
}
iterator end()
{
cout << "iterator end" << endl;
return iterator(nullptr, _root);
}
const_iterator begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
cout << "const_iterator begin" << endl;
return const_iterator(cur, _root);
}
const_iterator end() const
{
cout << "const_iterator end" << endl;
return const_iterator(nullptr, _root);
}
pair<iterator,bool> insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return pair<iterator, bool>(iterator(_root,_root),true);
}
Node* parent = nullptr;
Node* cur = _root;
//找到要插入的位置
while (cur)
{
if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data)) {
parent = cur;
cur = cur->_left;
}
else
{
return pair<iterator, bool>(iterator(cur, _root), false);;
}
}
//插入
cur = new Node(data);
cur->_col = RED;
Node* ret = cur;
//默认给红色
//因为插入黑了一定违背规则
//插入红色亦可能违背规则,有可能不违背规则
//减少调整
if (kot(parent->_data)> kot(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//此处cur是当前插入节点
//parent是cur的父节点
//开始调节
//开始检测是否符合规则,并且进行处理
//如果父节点的颜色是黑色的话不需要调节,直接退出
//如果父节点的颜色是红色的话 需要一直向上调节
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{//左边的三种情况
//情况一:叔叔存在且为红
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else //情况二或者情况三:叔叔不存在 / 叔叔存在且为黑
{
if (parent->_left == cur)
{//情况二
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else if (parent->_right == cur)
{//情况三
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
parent->_col = grandfather->_col = RED;
}
else
{
assert(false);
}
}
}
else if (grandfather->_right == parent)
{//右边的三种情况
//情况一:叔叔存在且为红
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else //情况二或者情况三: 叔叔不存在 / 叔叔存在且为黑
{
if (parent->_left == cur)
{//情况三
RotateR(parent);
RotateL(grandfather);
parent->_col = RED;
cur->_col = BLACK;
grandfather->_col = RED;
}
else if (parent->_right == cur)
{//情况二
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
assert(false);
}
}
}
else
{
assert(false);
}
}
_root->_col = BLACK;
return pair<iterator, bool>(iterator(ret, _root), true);;
}
void print()
{
int count = 0;
_print(_root, count);
cout << endl;
}
先给出修改完成后的容貌. 观察上面的修改之后的红黑树模板.(没有实现删除部分).我们在使用set和map的时候发现set是只有一个key,而相反map是key和val组成的一个键值对.
//再map中红黑树模板这样使用
RBTree<K, pair<const K,V>, KeyOfT > _rb_tree;
//再set中红黑树模板这样使用
RBTree<K, K, KeyOfT > _rb_tree;
这就实现了怎么共用一个模板实现两个不同的容器.
还有就是end和begin得具体指向那个节点得问题,再stl库中得实现不是这样写的,这个仁者见仁智者见智,我的方法肯定有缺陷,库里面在红黑树得前面根节点添加了一个哨兵位得头节点,end()指向得是哨兵位得头节点,我为了防便直接使用得是nullptr代替得.建议大家在修改红黑树得时候加上哨兵位得头节点.
二.set的具体实现
template<class K>
class set
{
struct KeyOfT
{
const K& operator()(const K& val)
{
return val;
}
};
public:
//typedef typename RBTree<K, K, KeyOfT >::iterator iterator;
//是否是const迭代器底层都应该使用const迭代器,因为,set是不允许修改的, 无论是T&和 T*都没有修改权限.
typedef typename RBTree<K, K, KeyOfT >::const_iterator iterator;
//iterator应该使用const_iterator
typedef typename RBTree<K, K, KeyOfT >::const_iterator const_iterator;
iterator begin() const
{
return _rb_tree.begin();
}
iterator end() const
{
return _rb_tree.end();
}
//在后面加上const,使end和begin在普通调用得const调用都是一样得.
//都返回const_iterator迭代器.
pair<iterator,bool> insert(const K& val)
{
//pair< typaname RBTree<K, K, KeyOfT>::iterator, bool> p = _rb_tree.insert(val);
//return pair<iterator, bool>(p.first, p.second);
return _rb_tree.insert(val);
//这里要在迭代器那层实现将 普通迭代器 构造成为 const迭代器.
//虽然普通迭代器 和 const迭代器 都是 同一个类模板,但是模板参数不相同,所以类型不相同,不能通过强制类型转换就行转换的
//有些内置类型是可以相互转换的,
//但是自定义类型大多是不能1相互转换的, 只有父子类之间可以相互转换.
}
void print()
{
_rb_tree.print();
}
private:
//第一个K是 key比较元素的类型
//第二个K是 每个节点的元素 ,set就只含有一个 key
//第三个通过仿函数取消 set 和 map 公用一个 insert的时候一个差异化的问题.
//insert插入的都是 T(Node的data) set的data是 k 可以直接比较
//但是 map的 insert插入的是 pair<K,T> 他的比较函数不符合需求,所以需要我们通过仿函数的返回值来去掉差异化.
RBTree<K, K, KeyOfT > _rb_tree;
};这里有几个问题需要想明白得,set是通过底层都是const迭代器来是是实现不允许修改key,这样就会引发各种各样的问题,比如insert在返回的时候 pari第一个参数的iterator就会变成const_iterator,然而红黑树的insert底层返回的是普通的iteratort所以就会出现问题.所以在迭代器中要写一个特殊的构造函数.实现普通迭代器构造const迭代器,的功能.(看上面的迭代器实现).
三.map的具体实现
template< class K, class V>
class map
{
struct KeyOfT
{
const K& operator()(const pair<K,V>& val)
{
return val.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, KeyOfT >::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, KeyOfT >::const_iterator const_iterator;
iterator begin()
{
return _rb_tree.begin();
}
iterator end()
{
return _rb_tree.end();
}
const_iterator begin() const
{
return _rb_tree.begin();
}
const_iterator end() const
{
return _rb_tree.end();
}
//const类型调用红黑树的const类型begin和end函数
//普通的迭代器调用普通的类型的begin和end
pair<iterator,bool> insert(const pair<K,V>& val)
{
return _rb_tree.insert(val);
}
void print()
{
_rb_tree.print();
}
V& operator[](const K& key)
{
return _rb_tree.insert(make_pair(key, V())).first->second;
}
private:
//第一个K是 key比较元素的类型
//第二个pair是 每个节点的元素 ,map节点中data存的是 pair
//第三个通过仿函数取消 set 和 map 公用一个 insert的时候一个差异化的问题.
//insert插入的都是 T(Node的data) set的data是 k 可以直接比较
//但是 map的 insert插入的是 pair<K,T> 他的比较函数不符合需求,所以需要我们通过仿函数的返回值来去掉差异化.
RBTree<K, pair<const K,V>, KeyOfT > _rb_tree;
};map的实现没有那么难 ,就是需要我们重载[]的一些东西.就需要insert的返回值的支持.然后使用迭代器即可.没有set那么绕