C++ set和map的模拟实现
我们之前在红黑树里讲过，STL容器中的set与map底层就是一棵红黑树，要模拟实现set与map底层需要实现红黑树，并将其做一些改造
1. set类与map类的框架
1.1 set
namespace pc
{
template<class K>
class set
{
public:
//成员函数
private:
RBTree<K, K, SetCompare> _rbt;
};
}将其存放在pc这个命名空间里。上面的SetCompare是仿函数，具体实现下面讲解
1.2 map
namespace pc
{
template<class K, class V>
class map
{
public:
//成员函数
private:
RBTree<K, pair<K, V>,MapCompare> _rbt;
};
}
也存放在了pc命名空间，同样MapCompare也是仿函数
2. 改造红黑树
2.1 节点的改造
我们，先将红黑树节点存储的值改变为一个可变的可操控的T（因为可能是set也可能是map调用）
template<class T>
struct RBTNode
{
Color co;//颜色
T _data;
RBTNode<T>* _parent;
RBTNode<T>* left;
RBTNode<T>* right;
RBTNode(const T& data)
: _data(data)
,_parent(nullptr)
, left(nullptr)
, right(nullptr)
{
}
};
2.2 改造红黑树实现
template<class K, class T,class Compare>三个模板参数，K是键值的数据类型，T是节点所存储数据的数据类型，Compare是仿函数
对于set是不需要第一个参数的，但是对于map查找与删除也是以K为查找基准的，虽然可以通过.first来取得对应元素，但map与set封装在一棵树set中没有这样的操作，所以加一个模板参数来获取这个K
（1）红黑树的节点的比较
因为存储的值可能是pair这种类型也可能是int这种类型，所以为了方便应对不同类型的情况，我们在set与map里分别定义一个仿函数，而不同类型需要的仿函数可能是不同的我们将其加入到模板参数里自动识别即可
map与set仿函数实现分别如下
template<class K, class V>
class map
{
public:
struct MapCompare
{
const K& operator() (const pair<K, V>& kv)
{
return kv.first;
}
};
private:
RBTree<K, pair<K, V>,MapCompare> _rbt;
}; template<class K>
class set
{
public:
struct SetCompare
{
const K& operator() (const K& k)
{
return k;
}
};
private:
RBTree<K, K, SetCompare> _rbt;
};
（2）插入改造
我们对返回值要进行改造成一个pair：第一个参数是一个迭代器第二个参数改造成一个bool值，比较大小用我们上面的仿函数来替换
pair<Iterator,bool> Insert(const T& data)
{
if (_root == nullptr)//插入
{
_root = new Node(data);
_root->co = BLACK;
return make_pair(Iterator(_root, _root), true);
}
Compare com;
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (com(cur->_data) > com(data))
{
parent = cur;
cur = cur->left;
}
else if (com(cur->_data) < com(data))
{
parent = cur;
cur = cur->right;
}
else//不接收重复键值的
{
return make_pair(Iterator(cur, _root), false);
}
}
cur = new Node(data);
Node* newnode = cur;//记录好最后返回
if (com(parent->_data) > com(data))
{
parent->left = cur;
}
else
parent->right = cur;
cur->_parent = parent;//将新建的节点父亲赋值
cur->co = RED;
while (parent && parent->co == RED)//新增节点为红色，其父亲就不能为红色,也不能为空
{
Node* u;//叔叔
Node* grandfather = parent->_parent;//parent为RED就肯定有爷爷因为根节点一定是黑的
if (grandfather->left == parent)
{
u = grandfather->right;
if (u && u->co == RED)//叔叔存在且为红色,仅变色
{
u->co = BLACK;
parent->co = BLACK;
grandfather->co = RED;
}
else if (u == nullptr || u->co == BLACK)//变色加旋转
{
if (cur == parent->left)
{
RRotate(grandfather);//右单旋
parent->co = BLACK;
grandfather->co = RED;
}
else
{
LRotate(parent);
RRotate(grandfather);
cur->co = BLACK;
parent->co = RED;
grandfather->co = RED;
}
break;//旋转后就不需要向上寻找了
}
}
else
{
u = grandfather->left;
if (u && u->co == RED)//叔叔存在且为红色,仅变色
{
u->co = BLACK;
parent->co = BLACK;
grandfather->co = RED;
}
else if (u == nullptr || u->co == BLACK)//叔叔不存在或者为黑，旋转加变色
{
if (cur == parent->right)
{
LRotate(grandfather);//左单旋
parent->co = BLACK;
grandfather->co = RED;
}
else
{
RRotate(parent);
LRotate(grandfather);
cur->co = BLACK;
parent->co = RED;
grandfather->co = RED;
}
break;//旋转后就不需要向上寻找了
}
}
cur = grandfather;//继续向上检测
parent = cur->_parent;
}
_root->co = BLACK;
return make_pair(Iterator(newnode, _root), true);
}（3）查找改造
查找改造十分简单，只需要利用仿函数比较即可，返回值变为迭代器
Iterator Find(const K& key)
{
Node* cur = _root;
Compare com;
while (cur)
{
if (com(cur->_data) < key)
{
cur = cur->right;
}
else if (com(cur->_data) > key)
{
cur = cur->left;
}
else
return Iterator(cur, _root);
}
return End();
}（4）删除改造
我们在删除中是利用了查找函数的，查找返回变为了一个迭代器，我们接受迭代器中存储的对应节点指针即可
Compare com;
Node* cur = Find(kv)._node;
if (cur == nullptr)
return;但是我们map的存储的pair数据，K是不能被修改的也就是被const修饰了，所以我们对于节点有左右子树的情况不能简单的将其存储值data与左子树最大或右子树最小交换，可以动态开辟一个新节点来代替
if (cur->left && cur->right)//将其转化为没有孩子或者只有左子树或右子树
{
Node* LeftBig = cur->left;//找到左边最大
while (LeftBig->right)
{
LeftBig = LeftBig->right;
}
Node* newnode = new Node(LeftBig->_data);
newnode->co = cur->co;
//改变cur孩子的指向
cur->left->_parent = newnode;
cur->right->_parent = newnode;
//改变cur父亲的指向
if (cur == _root)
{
_root = newnode;
newnode->co = BLACK;
}
else
{
if (cur->_parent->left == cur)
{
cur->_parent->left = newnode;
}
else if (cur->_parent->right == cur)
{
cur->_parent->right = newnode;
}
}
//改变newnode的指向
newnode->left = cur->left;
newnode->right = cur->right;
newnode->_parent = cur->_parent;
delete cur;
cur = LeftBig; //更新实际删除的结点
}总删除函数为
void Erase(const K& kv)
{
Compare com;
Node* cur = Find(kv)._node;
if (cur == nullptr)
return;
if (cur->left && cur->right)//将其转化为没有孩子或者只有左子树或右子树
{
Node* LeftBig = cur->left;//找到左边最大
while (LeftBig->right)
{
LeftBig = LeftBig->right;
}
Node* newnode = new Node(LeftBig->_data);
newnode->co = cur->co;
//改变cur孩子的指向
cur->left->_parent = newnode;
cur->right->_parent = newnode;
//改变cur父亲的指向
if (cur == _root)
{
_root = newnode;
newnode->co = BLACK;
}
else
{
if (cur->_parent->left == cur)
{
cur->_parent->left = newnode;
}
else if (cur->_parent->right == cur)
{
cur->_parent->right = newnode;
}
}
//改变newnode的指向
newnode->left = cur->left;
newnode->right = cur->right;
newnode->_parent = cur->_parent;
delete cur;
cur = LeftBig; //更新实际删除的结点
}
Node* parent = cur->_parent;
if (cur->left||cur->right)//如果有左孩子或有孩子，替换并将颜色换为黑色(原来是黑色也不影响)
{
if (cur == _root)//如果要删除的节点是根节点
{
if (cur->left)
{
_root = cur->left;
cur->left->_parent = nullptr;
_root->co = BLACK;
}
else if (cur->right)
{
_root = cur->right;
cur->right->_parent = nullptr;
_root->co = BLACK;
}
else
assert(false);
}
else//不是根节点
{
if (parent->left == cur)//如果cur是左子树
{
if (cur->left)//如果其是左子树还有
{
parent->left = cur->left;
cur->left->_parent = parent;
}
else if (cur->right)//如果是右子树还有
{
parent->left = cur->right;
cur->right->_parent = parent;
}
parent->left->co = BLACK;//调整为黑色
}
else if (parent->right == cur)
{
if (cur->left)
{
parent->right = cur->left;
cur->left->_parent = parent;
}
else if (cur->right)
{
parent->right = cur->right;
cur->right->_parent = parent;
}
parent->right->co = BLACK;//调整为黑色
}
else
assert(false);
}
delete cur;
cur = nullptr;
}
else//没有孩子
{
if (cur->co == RED)//要删除节点为红色，不需要进行调整，不可能是根节点，根节点一定是黑的
{
if (parent->left == cur)
{
parent->left = nullptr;
}
else if (parent->right == cur)
{
parent->right = nullptr;
}
delete cur;
cur = nullptr;
}
else if (cur->co == BLACK)
{
//删除的是根节点
if (cur == _root)
{
_root = nullptr;
delete cur;
cur = nullptr;
}
else
{
Node* bro;//兄弟,不可能为空，不然就不是所有路径都有一样的黑色节点了
Node* tmp = cur;//删除tmp节点了
cur->co = TWOBLACK;
while(cur->co==TWOBLACK)
{
if (parent->left == cur)//cur是父亲的左节点
{
bro = parent->right;
if (bro->co == BLACK)//如果兄弟是黑色，有两种情况
{
//1.至少有一个是红孩子
if (bro->right && bro->right->co == RED)//右孩子存在且为红,如果左孩子也同时存在且为红也可进行这一操作
{
//变色， 1. bro孩子的颜色变成bro的颜色 2. bor的颜色变为parent的颜色，parent的颜色变为黑色
bro->right->co = bro->co;
bro->co = parent->co;
parent->co = BLACK;
//旋转
LRotate(parent);
cur->co = BLACK;
}
else if (bro->left && bro->left->co == RED)//左孩子存在且为红
{
//变色，1.bro孩子颜色变为bro父亲的颜色(不用经过bro) 2.bro父亲变黑
bro->left->co = parent->co;
parent->co = BLACK;
//旋转
RRotate(bro);
LRotate(parent);
cur->co = BLACK;
}
else//2.孩子都是黑色，nullptr也算是黑色
{
//兄弟变红,
bro->co = RED;
//双黑上移 有三种情况
//1.parent是红色的或者是根节点,直接设置成黑色
cur->co = BLACK;
if (parent->co == RED || parent == _root)
{
parent->co = BLACK;
}
else //2.是普通节点
{
parent->co = TWOBLACK;
cur = parent;//将其设置为新的
parent = cur->_parent;//
}
}
}
else if (bro->co == RED)//兄弟为红，父兄变色,朝双黑节点旋转
{
bro->co = BLACK;
parent->co = RED;
LRotate(parent);
}
}
else if (parent->right == cur)
{
bro = parent->left;
if (bro->co == BLACK)//如果兄弟是黑色，有两种情况
{
//1.至少有一个是红孩子
if (bro->left && bro->left->co == RED)//左孩子存在且为红,如果右孩子也同时存在且为红也可进行这一操作
{
//变色， 1. bro孩子的颜色变成bro的颜色 2. bor的颜色变为parent的颜色，parent的颜色变为黑色
bro->left->co = bro->co;
bro->co = parent->co;
parent->co = BLACK;
//旋转
RRotate(parent);
cur->co = BLACK;
}
else if (bro->right && bro->right->co == RED)//右孩子存在且为红
{
//变色，1.bro孩子颜色变为bro父亲的颜色(不用经过bro) 2.bro父亲变黑
bro->right->co = parent->co;
parent->co = BLACK;
//旋转
LRotate(bro);
RRotate(parent);
cur->co = BLACK;
}
else//2.孩子都是黑色，nullptr也算是黑色
{
//兄弟变红,
bro->co = RED;
//双黑上移 有三种情况
//1.parent是红色的或者是根节点,直接设置成黑色
cur->co = BLACK;
if (parent->co == RED || parent == _root)
{
parent->co = BLACK;
}
else //2.是普通节点
{
parent->co = TWOBLACK;
cur = parent;//将其设置为新的
parent = cur->_parent;//
}
}
}
else if (bro->co == RED)//兄弟为红，父兄变色，朝双黑节点旋转
{
bro->co = BLACK;
parent->co = RED;
RRotate(parent);
}
}
else
assert(false);
}
//释放节点(删除)
parent = tmp->_parent;
cur = tmp;
if (parent->left == cur)
{
parent->left = nullptr;
}
else if (parent->right == cur)
{
parent->right = nullptr;
}
else
assert(false);
delete cur;
cur = nullptr;
}
}
else
assert(false);
}
}3. 迭代器实现
我们的迭代器模板参数要三个分别来存储：节点数据类型，数据类型的引用，数据类型的指针
template <class T,class Ref ,class Ptr>
struct RBTreeIterator
{
typedef RBTNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
RBTreeIterator(Node* node, Node* root)
:_node(node)
, _root(root)
{
}
Self& operator++()
{
//右不为空，右子树最左边就是下一个
if (_node->right)
{
Node* Leftnode = _node->right;
while (Leftnode->left)
{
Leftnode = Leftnode->left;
}
_node = Leftnode;
}
else
{
//往上找到，孩子是父亲左的那个节点
Node* cur = _node;
Node* parent = cur->_parent;
while (parent&&cur==parent->right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node == nullptr)//end()
{
//就要走到整棵树的最右边的节点
Node* Rightnode = _root;
while (Rightnode && Rightnode->right)
{
Rightnode = Rightnode->right;
}
_node = Rightnode;
}
else if(_node->left)
{
//左子树不为空，中序左子树最后一个
Node* Rightnode = _node->left;
while (Rightnode->right)
{
Rightnode = Rightnode->right;
}
_node = Rightnode;
}
else//孩子是父亲左的那个祖先
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator !=(const Self& s) const
{
return _node != s._node;
}
bool operator ==(const Self& s) const
{
return _node == s._node;
}
Node* _node;
Node* _root;
};++实现的思路：不看全局，只看局部，只考虑当前中序局部要访问的下一个节点。
- 当前的节点的右子树不为空，应该找到其右子树当中的最左节点。
- 如果当前的节点左子树为空，应该往上找到孩子不在父亲右的祖先(即往上找一个节点，是其父亲的左孩子，下一个要找的节点就是这个父亲节点)，如果往上找第一个值大于当前节点的值的节点的话再允许插入重复元素的情况下会出错。
--实现的思路与其相反
- 如果当前的节点左子树不为空，寻找其左子树当中的最右节点。
- 如果当前节点的左子树为空，往上找孩子不再父亲左的祖先
- 当当前节点为空时，说明是end，--将其变为树的最左边即可
在红黑树中写迭代器函数，begin() end()等
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
Iterator Begin()
{
Node* leftnode = _root;
while (leftnode && leftnode->left)
{
leftnode = leftnode->left;
}
return Iterator(leftnode, _root);//匿名对象初始化
}
Iterator End()
{
return Iterator(nullptr, _root);//因为还可能执行--操作
}
ConstIterator Begin() const
{
Node* leftnode = _root;
while (leftnode && leftnode->left)
{
leftnode = leftnode->left;
}
return ConstIterator(leftnode, _root);//匿名对象初始化
}
ConstIterator End() const
{
return ConstIterator(nullptr, _root);//因为还可能执行--操作
}我们set/map直接复用红黑树的接口即可
namespace pc
{
template<class K>
class set
{
public:
struct SetCompare
{
const K& operator() (const K& k)
{
return k;
}
};
//当 typedef 声明的是一个类中的 类型成员 而不是数据成员时，需要 typename 修饰声明的类型成员：
typedef typename RBTree<K,const K, SetCompare>::Iterator iterator;
typedef typename RBTree<K,const K, SetCompare>::ConstIterator const_iterator;
iterator begin()
{
return _rbt.Begin();
}
iterator end()
{
return _rbt.End();
}
const_iterator begin() const
{
return _rbt.Begin();
}
const_iterator end() const
{
return _rbt.End();
}
pair<iterator, bool> insert(const K& key)
{
return _rbt.Insert(key);
}
iterator find(const K & key)
{
return _rbt.Find(key);
}
void erase(const K& k)
{
_rbt.Erase(k);
}
void inorder()
{
_rbt.InOrder();
}
private:
//typedef set_rbt;
RBTree<K, const K, SetCompare> _rbt;
};
void Print( set<int>& s)
{
set<int>::iterator it = s.end();
while (it != s.begin())
{
--it;
// 不⽀持修改
//*it += 2;
cout << *it << " ";
}
cout << endl;
}
}namespace pc
{
template<class K, class V>
class map
{
public:
struct MapCompare
{
const K& operator() (const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename RBTree< K, pair< const K, V>, MapCompare>::Iterator iterator;
typedef typename RBTree< K, pair< const K, V>, MapCompare>::ConstIterator const_iterator;
iterator begin()
{
return _rbt.Begin();
}
iterator end()
{
return _rbt.End();
}
const_iterator begin() const
{
return _rbt.Begin();
}
const_iterator end() const
{
return _rbt.End();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _rbt.Insert(kv);
}
iterator find(const K& key)
{
return _rbt.Find(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));//map[] ，没有会创建
return ret.first->second;
}
void erase(const K& k)
{
_rbt.Erase(k);
}
void InOrder()
{
_rbt.InOrder();
}
private:
//typedef map_rbt;
RBTree<K, pair<const K, V>,MapCompare> _rbt;
};
}
在STL库中，end进行--操作与我们不同
让根节点增加了一个头结点，让这个头结点的左指针指向最左节点，右指针指向最右节点。然后让用头结点的左节点构造begin(),头结点本身end()，这样就能实现--后指向最右边的节点了
4. 源码
（1）RBT.h
#pragma once
#include<iostream>
#include<algorithm>
#include<assert.h>
using namespace std;
enum Color
{
RED,
BLACK,
TWOBLACK
};
template<class T>
struct RBTNode
{
Color co;//颜色
T _data;
RBTNode<T>* _parent;
RBTNode<T>* left;
RBTNode<T>* right;
RBTNode(const T& data)
: _data(data)
,_parent(nullptr)
, left(nullptr)
, right(nullptr)
{
}
};
template <class T,class Ref ,class Ptr>
struct RBTreeIterator
{
typedef RBTNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
RBTreeIterator(Node* node, Node* root)
:_node(node)
, _root(root)
{
}
Self& operator++()
{
//右不为空，右子树最左边就是下一个
if (_node->right)
{
Node* Leftnode = _node->right;
while (Leftnode->left)
{
Leftnode = Leftnode->left;
}
_node = Leftnode;
}
else
{
//往上找到，孩子是父亲左的那个节点
Node* cur = _node;
Node* parent = cur->_parent;
while (parent&&cur==parent->right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node == nullptr)//end()
{
//就要走到整棵树的最右边的节点
Node* Rightnode = _root;
while (Rightnode && Rightnode->right)
{
Rightnode = Rightnode->right;
}
_node = Rightnode;
}
else if(_node->left)
{
//左子树不为空，中序左子树最后一个
Node* Rightnode = _node->left;
while (Rightnode->right)
{
Rightnode = Rightnode->right;
}
_node = Rightnode;
}
else//孩子是父亲左的那个祖先
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator !=(const Self& s) const
{
return _node != s._node;
}
bool operator ==(const Self& s) const
{
return _node == s._node;
}
Node* _node;
Node* _root;
};
template<class K, class T,class Compare>
class RBTree
{
public:
typedef RBTNode<T> Node;
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
Iterator Begin()
{
Node* leftnode = _root;
while (leftnode && leftnode->left)
{
leftnode = leftnode->left;
}
return Iterator(leftnode, _root);//匿名对象初始化
}
Iterator End()
{
return Iterator(nullptr, _root);//因为还可能执行--操作
}
ConstIterator Begin() const
{
Node* leftnode = _root;
while (leftnode && leftnode->left)
{
leftnode = leftnode->left;
}
return ConstIterator(leftnode, _root);//匿名对象初始化
}
ConstIterator End() const
{
return ConstIterator(nullptr, _root);//因为还可能执行--操作
}
RBTree()
{ }
RBTree(const RBTree<K,T,Compare>& t)
{
_root = Copy(t._root);
}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* tmp = new Node(root->_data);
tmp->left = Copy(root->left);
tmp->right = Copy(root->right);
return tmp;
}
~RBTree()
{
Destroy(_root);
}
RBTree<K,T,Compare>& operator=(RBTree t)
{
swap(_root, t.root);
return *this;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->left);
Destroy(root->right);
delete root;
root = nullptr;
}
pair<Iterator,bool> Insert(const T& data)
{
if (_root == nullptr)//插入
{
_root = new Node(data);
_root->co = BLACK;
return make_pair(Iterator(_root, _root), true);
}
Compare com;
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (com(cur->_data) > com(data))
{
parent = cur;
cur = cur->left;
}
else if (com(cur->_data) < com(data))
{
parent = cur;
cur = cur->right;
}
else//不接收重复键值的
{
return make_pair(Iterator(cur, _root), false);
}
}
cur = new Node(data);
Node* newnode = cur;//记录好最后返回
if (com(parent->_data) > com(data))
{
parent->left = cur;
}
else
parent->right = cur;
cur->_parent = parent;//将新建的节点父亲赋值
cur->co = RED;
while (parent && parent->co == RED)//新增节点为红色，其父亲就不能为红色,也不能为空
{
Node* u;//叔叔
Node* grandfather = parent->_parent;//parent为RED就肯定有爷爷因为根节点一定是黑的
if (grandfather->left == parent)
{
u = grandfather->right;
if (u && u->co == RED)//叔叔存在且为红色,仅变色
{
u->co = BLACK;
parent->co = BLACK;
grandfather->co = RED;
}
else if (u == nullptr || u->co == BLACK)//变色加旋转
{
if (cur == parent->left)
{
RRotate(grandfather);//右单旋
parent->co = BLACK;
grandfather->co = RED;
}
else
{
LRotate(parent);
RRotate(grandfather);
cur->co = BLACK;
parent->co = RED;
grandfather->co = RED;
}
break;//旋转后就不需要向上寻找了
}
}
else
{
u = grandfather->left;
if (u && u->co == RED)//叔叔存在且为红色,仅变色
{
u->co = BLACK;
parent->co = BLACK;
grandfather->co = RED;
}
else if (u == nullptr || u->co == BLACK)//叔叔不存在或者为黑，旋转加变色
{
if (cur == parent->right)
{
LRotate(grandfather);//左单旋
parent->co = BLACK;
grandfather->co = RED;
}
else
{
RRotate(parent);
LRotate(grandfather);
cur->co = BLACK;
parent->co = RED;
grandfather->co = RED;
}
break;//旋转后就不需要向上寻找了
}
}
cur = grandfather;//继续向上检测
parent = cur->_parent;
}
_root->co = BLACK;
return make_pair(Iterator(newnode, _root), true);
}
Iterator Find(const K& key)
{
Node* cur = _root;
Compare com;
while (cur)
{
if (com(cur->_data) < key)
{
cur = cur->right;
}
else if (com(cur->_data) > key)
{
cur = cur->left;
}
else
return Iterator(cur, _root);
}
return End();
}
void Erase(const K& kv)
{
Compare com;
Node* cur = Find(kv)._node;
if (cur == nullptr)
return;
if (cur->left && cur->right)//将其转化为没有孩子或者只有左子树或右子树
{
Node* LeftBig = cur->left;//找到左边最大
while (LeftBig->right)
{
LeftBig = LeftBig->right;
}
Node* newnode = new Node(LeftBig->_data);
newnode->co = cur->co;
//改变cur孩子的指向
cur->left->_parent = newnode;
cur->right->_parent = newnode;
//改变cur父亲的指向
if (cur == _root)
{
_root = newnode;
newnode->co = BLACK;
}
else
{
if (cur->_parent->left == cur)
{
cur->_parent->left = newnode;
}
else if (cur->_parent->right == cur)
{
cur->_parent->right = newnode;
}
}
//改变newnode的指向
newnode->left = cur->left;
newnode->right = cur->right;
newnode->_parent = cur->_parent;
delete cur;
cur = LeftBig; //更新实际删除的结点
}
Node* parent = cur->_parent;
if (cur->left||cur->right)//如果有左孩子或有孩子，替换并将颜色换为黑色(原来是黑色也不影响)
{
if (cur == _root)//如果要删除的节点是根节点
{
if (cur->left)
{
_root = cur->left;
cur->left->_parent = nullptr;
_root->co = BLACK;
}
else if (cur->right)
{
_root = cur->right;
cur->right->_parent = nullptr;
_root->co = BLACK;
}
else
assert(false);
}
else//不是根节点
{
if (parent->left == cur)//如果cur是左子树
{
if (cur->left)//如果其是左子树还有
{
parent->left = cur->left;
cur->left->_parent = parent;
}
else if (cur->right)//如果是右子树还有
{
parent->left = cur->right;
cur->right->_parent = parent;
}
parent->left->co = BLACK;//调整为黑色
}
else if (parent->right == cur)
{
if (cur->left)
{
parent->right = cur->left;
cur->left->_parent = parent;
}
else if (cur->right)
{
parent->right = cur->right;
cur->right->_parent = parent;
}
parent->right->co = BLACK;//调整为黑色
}
else
assert(false);
}
delete cur;
cur = nullptr;
}
else//没有孩子
{
if (cur->co == RED)//要删除节点为红色，不需要进行调整，不可能是根节点，根节点一定是黑的
{
if (parent->left == cur)
{
parent->left = nullptr;
}
else if (parent->right == cur)
{
parent->right = nullptr;
}
delete cur;
cur = nullptr;
}
else if (cur->co == BLACK)
{
//删除的是根节点
if (cur == _root)
{
_root = nullptr;
delete cur;
cur = nullptr;
}
else
{
Node* bro;//兄弟,不可能为空，不然就不是所有路径都有一样的黑色节点了
Node* tmp = cur;//删除tmp节点了
cur->co = TWOBLACK;
while(cur->co==TWOBLACK)
{
if (parent->left == cur)//cur是父亲的左节点
{
bro = parent->right;
if (bro->co == BLACK)//如果兄弟是黑色，有两种情况
{
//1.至少有一个是红孩子
if (bro->right && bro->right->co == RED)//右孩子存在且为红,如果左孩子也同时存在且为红也可进行这一操作
{
//变色， 1. bro孩子的颜色变成bro的颜色 2. bor的颜色变为parent的颜色，parent的颜色变为黑色
bro->right->co = bro->co;
bro->co = parent->co;
parent->co = BLACK;
//旋转
LRotate(parent);
cur->co = BLACK;
}
else if (bro->left && bro->left->co == RED)//左孩子存在且为红
{
//变色，1.bro孩子颜色变为bro父亲的颜色(不用经过bro) 2.bro父亲变黑
bro->left->co = parent->co;
parent->co = BLACK;
//旋转
RRotate(bro);
LRotate(parent);
cur->co = BLACK;
}
else//2.孩子都是黑色，nullptr也算是黑色
{
//兄弟变红,
bro->co = RED;
//双黑上移 有三种情况
//1.parent是红色的或者是根节点,直接设置成黑色
cur->co = BLACK;
if (parent->co == RED || parent == _root)
{
parent->co = BLACK;
}
else //2.是普通节点
{
parent->co = TWOBLACK;
cur = parent;//将其设置为新的
parent = cur->_parent;//
}
}
}
else if (bro->co == RED)//兄弟为红，父兄变色,朝双黑节点旋转
{
bro->co = BLACK;
parent->co = RED;
LRotate(parent);
}
}
else if (parent->right == cur)
{
bro = parent->left;
if (bro->co == BLACK)//如果兄弟是黑色，有两种情况
{
//1.至少有一个是红孩子
if (bro->left && bro->left->co == RED)//左孩子存在且为红,如果右孩子也同时存在且为红也可进行这一操作
{
//变色， 1. bro孩子的颜色变成bro的颜色 2. bor的颜色变为parent的颜色，parent的颜色变为黑色
bro->left->co = bro->co;
bro->co = parent->co;
parent->co = BLACK;
//旋转
RRotate(parent);
cur->co = BLACK;
}
else if (bro->right && bro->right->co == RED)//右孩子存在且为红
{
//变色，1.bro孩子颜色变为bro父亲的颜色(不用经过bro) 2.bro父亲变黑
bro->right->co = parent->co;
parent->co = BLACK;
//旋转
LRotate(bro);
RRotate(parent);
cur->co = BLACK;
}
else//2.孩子都是黑色，nullptr也算是黑色
{
//兄弟变红,
bro->co = RED;
//双黑上移 有三种情况
//1.parent是红色的或者是根节点,直接设置成黑色
cur->co = BLACK;
if (parent->co == RED || parent == _root)
{
parent->co = BLACK;
}
else //2.是普通节点
{
parent->co = TWOBLACK;
cur = parent;//将其设置为新的
parent = cur->_parent;//
}
}
}
else if (bro->co == RED)//兄弟为红，父兄变色，朝双黑节点旋转
{
bro->co = BLACK;
parent->co = RED;
RRotate(parent);
}
}
else
assert(false);
}
//释放节点(删除)
parent = tmp->_parent;
cur = tmp;
if (parent->left == cur)
{
parent->left = nullptr;
}
else if (parent->right == cur)
{
parent->right = nullptr;
}
else
assert(false);
delete cur;
cur = nullptr;
}
}
else
assert(false);
}
}
void RRotate(Node* parent)//右单旋
{
Node* cur = parent->left;
Node* curR = cur->right;
parent->left = curR;
cur->right = parent;
if (curR)//若其不为空就将其父亲设为parent
{
curR->_parent = parent;
}
if (_root == parent)//若parent是根节点
{
_root = cur;
cur->_parent = nullptr;
}
else
{
cur->_parent = parent->_parent;
if (parent->_parent->left == parent)
parent->_parent->left = cur;
else if (parent->_parent->right == parent)
parent->_parent->right = cur;
else
assert(false);
}
parent->_parent = cur;
}
void LRotate(Node* parent)//左单旋
{
Node* cur = parent->right;
Node* curL = cur->left;
parent->right = cur->left;
cur->left = parent;
if (curL)
{
curL->_parent = parent;
}
if (_root == parent)//若parent是根节点
{
_root = cur;
cur->_parent = nullptr;
}
else
{
cur->_parent = parent->_parent;
if (parent->_parent->left == parent)
parent->_parent->left = cur;
else if (parent->_parent->right == parent)
parent->_parent->right = cur;
else
assert(false);
}
parent->_parent = cur;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)//可以在外面再弄一个通过this指针访问
{
if (root == nullptr)
return;
Compare com;
_InOrder(root->left);
cout << com(root->_data) << " ";
_InOrder(root->right);
}
private:
Node* _root = nullptr;
};（2）set.h
#pragma once
#include"RBT.h"
namespace pc
{
template<class K>
class set
{
public:
struct SetCompare
{
const K& operator() (const K& k)
{
return k;
}
};
//当 typedef 声明的是一个类中的 类型成员 而不是数据成员时，需要 typename 修饰声明的类型成员：
typedef typename RBTree<K,const K, SetCompare>::Iterator iterator;
typedef typename RBTree<K,const K, SetCompare>::ConstIterator const_iterator;
iterator begin()
{
return _rbt.Begin();
}
iterator end()
{
return _rbt.End();
}
const_iterator begin() const
{
return _rbt.Begin();
}
const_iterator end() const
{
return _rbt.End();
}
pair<iterator, bool> insert(const K& key)
{
return _rbt.Insert(key);
}
iterator find(const K & key)
{
return _rbt.Find(key);
}
void erase(const K& k)
{
_rbt.Erase(k);
}
void inorder()
{
_rbt.InOrder();
}
private:
//typedef set_rbt;
RBTree<K, const K, SetCompare> _rbt;
};
void Print( set<int>& s)
{
set<int>::iterator it = s.end();
while (it != s.begin())
{
--it;
// 不⽀持修改
//*it += 2;
cout << *it << " ";
}
cout << endl;
}
}（3）map.h
#include"RBT.h"
namespace pc
{
template<class K, class V>
class map
{
public:
struct MapCompare
{
const K& operator() (const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename RBTree< K, pair< const K, V>, MapCompare>::Iterator iterator;
typedef typename RBTree< K, pair< const K, V>, MapCompare>::ConstIterator const_iterator;
iterator begin()
{
return _rbt.Begin();
}
iterator end()
{
return _rbt.End();
}
const_iterator begin() const
{
return _rbt.Begin();
}
const_iterator end() const
{
return _rbt.End();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _rbt.Insert(kv);
}
iterator find(const K& key)
{
return _rbt.Find(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));//map[] ，没有会创建
return ret.first->second;
}
void erase(const K& k)
{
_rbt.Erase(k);
}
void InOrder()
{
_rbt.InOrder();
}
private:
//typedef map_rbt;
RBTree<K, pair<const K, V>,MapCompare> _rbt;
};
}
本篇到这里啦~ (๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤
ヾ(￣▽￣)Bye~Bye~