我们用上期写的红黑树来模拟一下C++中set和map的封装
目录
我们先来看看STL中set和map的实现源码：
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing set
//·····
}template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
typedef Key key_type;
typedef T data_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
typedef Compare key_compare;
//·····
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
//·····
}咦？这实现的怎么和想象中的有些不一样，其底层都用到了一个rb_tree，我们来看看这个rb_tree的源码：
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 simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
typedef __rb_tree_color_type color_type;
//·····
}
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};
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;
//·····
}哦~原来STL中的set和map使用的底层红黑树都是同一个结构（只存一个元素类型），set中红黑树存储的元素类型为T，map中存储类型为pair<const Key，T>
我们想要使用自己手搓的红黑树来封装set和map，就要对原来的实现结构做一些修改：
#include<iostream>
using namespace std;
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;//多一个指针指向其父节点,方便我们的后续操作
T _data;
Colour _col;//颜色标识
RBTreeNode(const T& data)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_data(data),
_col(RED)//默认构造时,优先将节点的颜色置为红色
{}
};
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* cur = _root, * parent = nullptr;
while (cur)//找到合适的位置
{
if (data < cur->_data)
{
parent = cur;
cur = cur->_left;
}
else if (data > cur->_data)
{
parent = cur;
cur = cur->_right;
}
else
{
cout << "插入的值重复" << endl;
return false;
}
}
cur = new Node(data);
//将插入的节点连接上二叉树
if (data < parent->_data)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//开始调整
while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
elsecur为红，p为红，g为黑，u不存在/u存在且为黑
{
if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线
{
//右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur在p的右边,p在g的左边，构成一条折线
{
//左右双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//调整完跳出
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
elsecur为红，p为红，g为黑，u不存在/u存在且为黑
{
if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线
{
//左单旋
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur在p的左边,p在g的右边，构成一条折线
{
//右左双旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//调整完跳出
}
}
}
_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑
return true;
}
bool IsBalance()
{
if (_root && _root->_col == RED)
{
cout << "根节点颜色是红色" << endl;
return false;
}
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchmark;
cur = cur->_left;
}
// 连续红色节点
return _Check(_root, 0, benchmark);
}
private:
void RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pparent = parent->_parent;
parent->_right = subRL;//更新parent的右节点
if (subRL)//防止该节点为空
{
subRL->_parent = parent;//更新subRL的父节点
}
parent->_parent = subR;//更新parent的父节点
subR->_left = parent;//subR的左子树置为parent
subR->_parent = pparent;//更新subR的父节点
if (pparent == nullptr)//旋转的是整棵树
{
_root = subR;//更新根节点
}
else//将旋转后的子树链接上整个二叉树
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
}
}
void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pparent = parent->_parent;
parent->_left = subLR;//更新parent的左节点
if (subLR)//防止该节点为空
{
subLR->_parent = parent;//更新subLR的父节点
}
parent->_parent = subL;//更新parent的父节点
subL->_right = parent;//subL的右子树置为parent
subL->_parent = pparent;//更新subL的父节点
if (pparent == nullptr)//旋转的是整棵树
{
_root = subL;//更新根节点
}
else//将旋转后的子树链接上整个二叉树
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
}
}
bool _Check(Node* root, int blackNum, int benchmark)
{
if (root == nullptr)
{
if (benchmark != blackNum)
{
cout << "某条路径黑色节点的数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED
&& root->_parent
&& root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
return false;
}
return _Check(root->_left, blackNum, benchmark)
&& _Check(root->_right, blackNum, benchmark);
}
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
private:
Node* _root = nullptr;
};#include"RBTree.h"
namespace lhs
{
template<class K, class V>
class map
{
public:
bool insert(const pair<const K, V>&data)
{
return _t.Insert(data);
}
private:
RBTree<K, pair<const K, V>> _t;
};
}#include"RBTree.h"
namespace lhs
{
template<class K>
class set
{
public:
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K> _t;
};
}insert函数的实现很简单，直接调用即可
但是我们基于底层实现的红黑树，map的数据比较是按pair类型来进行的，这显然并不符合我们的需求，所以我们需要再向RBTree传入一个仿函数来提取pair中的first成员来进行比较：
namespace lhs
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K,V>& kv)
{
return kv.first;
}
};
public:
bool insert(const pair<const K, V>&data)
{
return _t.Insert(data);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}namespace lhs
{
template<class K>
class set
{
struct SetKeyOfT//set中仿函数没有什么实际作用,只是为了和map配套
{
const K& operator()(const K& key)
{
return key;
}
};
public:
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}#include<iostream>
using namespace std;
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;//多一个指针指向其父节点,方便我们的后续操作
T _data;
Colour _col;//颜色标识
RBTreeNode(const T& data)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_data(data),
_col(RED)//默认构造时,优先将节点的颜色置为红色
{}
};
template<class K, class T, class KeyOft>//根据KeyOfT传入的仿函数来确定比较类型
class RBTree
{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* cur = _root, * parent = nullptr;
KeyOft kot;//创建仿函数对象
while (cur)//找到合适的位置
{
if (kot(data) < kot(cur->_data))//通过仿函数调出我们想要比较的成员
{
parent = cur;
cur = cur->_left;
}
else if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else
{
cout << "插入的值重复" << endl;
return false;
}
}
cur = new Node(data);
//将插入的节点连接上二叉树
if (kot(data) < kot(parent->_data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//开始调整
//.......
}
//......
private:
Node* _root = nullptr;
};
当然确定了map中的比较类型也不行，万一比较方式不符合用户的预期，我们需要通过模版传入仿函数来替换比较的方式：
namespace lhs
{
template<class K, class Compare = less<K>>
class set
{
struct SetKeyOfT//set中仿函数没有什么实际作用,只是为了和map配套
{
const K& operator()(const K& key)
{
return key;
}
};
public:
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT, Compare> _t;
};
}namespace lhs
{
template<class K, class V, class Compare = less<K>>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K,V>& kv)
{
return kv.first;
}
};
public:
bool insert(const pair<const K, V>&data)
{
return _t.Insert(data);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT, Compare> _t;
};
}#include<iostream>
using namespace std;
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;//多一个指针指向其父节点,方便我们的后续操作
T _data;
Colour _col;//颜色标识
RBTreeNode(const T& data)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_data(data),
_col(RED)//默认构造时,优先将节点的颜色置为红色
{}
};
template<class K, class T, class KeyOft, class Compare>//根据KeyOfT传入的仿函数来确定比较类型，根据Compare传入的方式来确定比较方式
class RBTree
{
typedef RBTreeNode<T> Node;
public:
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* cur = _root, * parent = nullptr;
KeyOft kot;//创建仿函数对象
Compare cmp;
while (cur)//找到合适的位置
{
if (cmp(kot(data), kot(cur->_data)))//通过仿函数调出我们想要比较的成员,再按我们预期的方式进行比较
{
parent = cur;
cur = cur->_left;
}
else if (kot(data) == kot(cur->_data))
{
cout << "插入的值重复" << endl;
return false;
}
else
{
parent = cur;
cur = cur->_right;
}
}
cur = new Node(data);
//将插入的节点连接上二叉树
if (cmp(kot(data), kot(parent->_data)))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//开始调整
//.......
}
private:
Node* _root = nullptr;
};
红黑树迭代器的实现和我们讲解list迭代器的实现基本一致，这里不再一步步赘述，不熟悉的同学可以看到这里：【C++】深入剖析list
在红黑树对于迭代器的++操作会有不同的方式来进行处理：
#include<iostream>
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;//多一个指针指向其父节点,方便我们的后续操作
T _data;
Colour _col;//颜色标识
RBTreeNode(const T& data)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_data(data),
_col(RED)//默认构造时,优先将节点的颜色置为红色
{}
};
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& n)
{
return _node != n._node;
}
Self& operator++()//++就是走中序遍历的顺序
{
if (_node->_right)//如果右子树不为空，就找到右子树的最左节点
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else//右子树为空,向上找到孩子节点是父亲左孩子的那个节点
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()//--就是反向的中序遍历(右根左)
{
if (_node->_left)//如果左子树不为空，就找到左子树的最右节点
{
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else//左子树为空,向上找到孩子节点是父亲右孩子的那个节点
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOft, class Compare>//根据KeyOfT传入的仿函数来确定比较类型,根据Compare传入的方式来确定比较方式
class RBTree
{
typedef RBTreeNode<T> Node;
public:
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
public:
typedef __RBTreeIterator<T, T&, T*> iterator;
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
Node* cur=_root;
while (cur&&cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator cbegin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator cend()
{
return const_iterator(nullptr);
}
private:
Node* _root = nullptr;
};
namespace lhs
{
template<class K, class V, class Compare = std::less<K>>
class map
{
struct MapKeyOfT
{
const K& operator()(const std::pair<const K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT,Compare>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, std::pair<const K, V>, MapKeyOfT, Compare> _t;
};
}namespace lhs
{
template<class K, class Compare = std::less<K>>
class set
{
struct SetKeyOfT//set中仿函数没有什么实际作用,只是为了和map配套
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT, Compare>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, K, SetKeyOfT, Compare> _t;
};
}map的operate[]的实现底层调用的是insert函数，所以我们需要在之前实现的insert函数上做一些修改：
#include<iostream>
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;//多一个指针指向其父节点,方便我们的后续操作
T _data;
Colour _col;//颜色标识
RBTreeNode(const T& data)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_data(data),
_col(RED)//默认构造时,优先将节点的颜色置为红色
{}
};
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& n)
{
return _node != n._node;
}
Self& operator++()//++就是走中序遍历的顺序
{
if (_node->_right)//如果右子树不为空，就找到右子树的最左节点
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else//右子树为空,向上找到孩子节点是父亲左孩子的那个节点
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()//--就是反向的中序遍历(右根左)
{
if (_node->_left)//如果左子树不为空，就找到左子树的最右节点
{
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else//左子树为空,向上找到孩子节点是父亲右孩子的那个节点
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOft, class Compare>//根据KeyOfT传入的仿函数来确定比较类型,根据Compare传入的方式来确定比较方式
class RBTree
{
typedef RBTreeNode<T> Node;
public:
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
public:
typedef __RBTreeIterator<T, T&, T*> iterator;
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
std::pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return std::make_pair(iterator(_root), true);
}
Node* cur = _root, * parent = nullptr;
KeyOft kot;//创建仿函数对象
Compare cmp;
while (cur)//找到合适的位置
{
if (cmp(kot(data), kot(cur->_data)))//通过仿函数调出我们想要比较的成员,再按我们预期的方式进行比较
{
parent = cur;
cur = cur->_left;
}
else if (kot(data) == kot(cur->_data))
{
std::cout << "插入的值重复" << std::endl;
return std::make_pair(iterator(cur), false);
}
else
{
parent = cur;
cur = cur->_right;
}
}
cur = new Node(data);
//将插入的节点连接上二叉树
if (cmp(kot(data), kot(parent->_data)))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
Node* newnode = cur;//记录新增节点位置，方便构造返回迭代器，防止调整后cur位置发生改变
//开始调整
while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
elsecur为红，p为红，g为黑，u不存在/u存在且为黑
{
if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线
{
//右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur在p的右边,p在g的左边，构成一条折线
{
//左右双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//调整完跳出
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
elsecur为红，p为红，g为黑，u不存在/u存在且为黑
{
if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线
{
//左单旋
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur在p的左边,p在g的右边，构成一条折线
{
//右左双旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//调整完跳出
}
}
}
_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑
return std::make_pair(iterator(newnode), true);;
}
private:
Node* _root = nullptr;
};
namespace lhs
{
template<class K, class V, class Compare = std::less<K>>
class map
{
struct MapKeyOfT
{
const K& operator()(const std::pair<const K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT,Compare>::iterator iterator;
V& operator[](const K& key)//调用Insert来实现
{
std::pair<iterator, bool> ret = _t.Insert(std::make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, std::pair<const K, V>, MapKeyOfT, Compare> _t;
};
}RBTree.h:
#pragma once
#include<iostream>
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;//多一个指针指向其父节点,方便我们的后续操作
T _data;
Colour _col;//颜色标识
RBTreeNode(const T& data)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_data(data),
_col(RED)//默认构造时,优先将节点的颜色置为红色
{}
};
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& n)
{
return _node != n._node;
}
Self& operator++()//++就是走中序遍历的顺序
{
if (_node->_right)//如果右子树不为空，就找到右子树的最左节点
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else//右子树为空,向上找到孩子节点是父亲左孩子的那个节点
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()//--就是反向的中序遍历(右根左)
{
if (_node->_left)//如果左子树不为空，就找到左子树的最右节点
{
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else//左子树为空,向上找到孩子节点是父亲右孩子的那个节点
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOft, class Compare>//根据KeyOfT传入的仿函数来确定比较类型,根据Compare传入的方式来确定比较方式
class RBTree
{
typedef RBTreeNode<T> Node;
public:
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
public:
typedef __RBTreeIterator<T, T&, T*> iterator;
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
Node* cur=_root;
while (cur&&cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator cbegin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator cend()
{
return const_iterator(nullptr);
}
std::pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return std::make_pair(iterator(_root), true);
}
Node* cur = _root, * parent = nullptr;
KeyOft kot;//创建仿函数对象
Compare cmp;
while (cur)//找到合适的位置
{
if (cmp(kot(data), kot(cur->_data)))//通过仿函数调出我们想要比较的成员,再按我们预期的方式进行比较
{
parent = cur;
cur = cur->_left;
}
else if (kot(data) == kot(cur->_data))
{
std::cout << "插入的值重复" << std::endl;
return std::make_pair(iterator(cur), false);
}
else
{
parent = cur;
cur = cur->_right;
}
}
cur = new Node(data);
//将插入的节点连接上二叉树
if (cmp(kot(data), kot(parent->_data)))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
Node* newnode = cur;//记录新增节点位置，方便构造返回迭代器，防止调整后cur位置发生改变
//开始调整
while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
elsecur为红，p为红，g为黑，u不存在/u存在且为黑
{
if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线
{
//右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur在p的右边,p在g的左边，构成一条折线
{
//左右双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//调整完跳出
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
elsecur为红，p为红，g为黑，u不存在/u存在且为黑
{
if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线
{
//左单旋
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//cur在p的左边,p在g的右边，构成一条折线
{
//右左双旋
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//调整完跳出
}
}
}
_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑
return std::make_pair(iterator(newnode), true);;
}
bool IsBalance()
{
if (_root && _root->_col == RED)
{
std::cout << "根节点颜色是红色" << std::endl;
return false;
}
int benchmark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchmark;
cur = cur->_left;
}
// 连续红色节点
return _Check(_root, 0, benchmark);
}
private:
void RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pparent = parent->_parent;
parent->_right = subRL;//更新parent的右节点
if (subRL)//防止该节点为空
{
subRL->_parent = parent;//更新subRL的父节点
}
parent->_parent = subR;//更新parent的父节点
subR->_left = parent;//subR的左子树置为parent
subR->_parent = pparent;//更新subR的父节点
if (pparent == nullptr)//旋转的是整棵树
{
_root = subR;//更新根节点
}
else//将旋转后的子树链接上整个二叉树
{
if (pparent->_left == parent)
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
}
}
void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pparent = parent->_parent;
parent->_left = subLR;//更新parent的左节点
if (subLR)//防止该节点为空
{
subLR->_parent = parent;//更新subLR的父节点
}
parent->_parent = subL;//更新parent的父节点
subL->_right = parent;//subL的右子树置为parent
subL->_parent = pparent;//更新subL的父节点
if (pparent == nullptr)//旋转的是整棵树
{
_root = subL;//更新根节点
}
else//将旋转后的子树链接上整个二叉树
{
if (pparent->_left == parent)
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
}
}
bool _Check(Node* root, int blackNum, int benchmark)
{
if (root == nullptr)
{
if (benchmark != blackNum)
{
std::cout << "某条路径黑色节点的数量不相等" << std::endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED
&& root->_parent
&& root->_parent->_col == RED)
{
std::cout << "存在连续的红色节点" << std::endl;
return false;
}
return _Check(root->_left, blackNum, benchmark)
&& _Check(root->_right, blackNum, benchmark);
}
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
private:
Node* _root = nullptr;
};
Map.h:
#pragma once
#include"RBTree.h"
namespace lhs
{
template<class K, class V, class Compare = std::less<K>>
class map
{
struct MapKeyOfT
{
const K& operator()(const std::pair<const K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT,Compare>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
std::pair<iterator, bool> insert(const std::pair<const K, V>& data)
{
return _t.Insert(data);
}
V& operator[](const K& key)//调用Insert来实现
{
std::pair<iterator, bool> ret = _t.Insert(std::make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, std::pair<const K, V>, MapKeyOfT, Compare> _t;
};
}Set.h：
#pragma once
#include"RBTree.h"
namespace lhs
{
template<class K, class Compare = std::less<K>>
class set
{
struct SetKeyOfT//set中仿函数没有什么实际作用,只是为了和map配套
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT, Compare>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
std::pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT, Compare> _t;
};
}