【C++】用手搓的红黑树手搓set和map
目录
一、set/map的底层结构
1、set/map的源码
2、利用模板区分set/map
3、利用仿函数控制比较大小
二、set/map的迭代器（红黑树的迭代器）
1、红黑树的begin、end迭代器
2、红黑树迭代器的operator++
3、红黑树迭代器的operator--
三、set的const迭代器
四、map的const迭代器
五、迭代器类的拷贝构造
六、整体代码
1、RBTree.h
2、Set.h
3、map.h
本文相关往期内容，可按需查阅：
1、【C++】set/multiset、map/multimap的使用
2、【数据结构】二叉搜索树的实现
3、【数据结构】平衡二叉树
4、【数据结构】手撕红黑树
本文难点：使用红黑树封装set和map，必须保证两种数据结构复用同一棵红黑树；且满足set和map的性质，set的value不可被改变，而map的value可以被改变。
一、set/map的底层结构
1、set/map的源码
扒一扒STL库中set和map的底层结构，不难发现，set和map的底层用的都是红黑树且均为key/value模型。
只不过set的key/value均为key值填充，而map的key/value使用key和pair<const Key,T>进行填充。因此，set和map中底层虽然都是红黑树，但这两种数据结构中的红黑树实例化类型并不相同。
那么使用同一颗红黑树的模板，如何实例化出适配set和/map的对象？
2、利用模板区分set/map
template <class T>//T类型代表value
struct RBTreeNode
{
RBTreeNode(const T& data)
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _data(data)
, _col(RED)
{}
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
T _data;
Color _col;
};map和set的区别在于value的不同，红黑树模板参数T，代表value用以区分set和map。
3、利用仿函数控制比较大小
我们会发现红黑树的插入等接口会对key值进行比较大小，像set直接对key进行比较，这没问题，但是map中的节点装的是pair<K,V>,pair的比较规则是first比完之后可能会再去比较second（而我们仅仅想要比较first，该比较规则不适用）。
通过源码启发，我们可以对红黑树新增一个模板参数：仿函数KeyOfT，在set和map类中完善该仿函数的比较对象，用于区分set和map的比较：
template <class K>
class set
{
//仿函数用于比较大小
struct SetKeyOfT
{
const K& operator()(const K& key)//传入节点的值
{
return key;//返回key
}
};
private:
RBTree<K, K, SetKeyOfT> _t;
};
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)//传入节点的值
{
return kv.first;//返回kv.first
}
};
private:
RBTree<const K, pair<K,V>, MapKeyOfT> _t;
};
//利用模板确定传入对象是set还是map
template <class K, class T,class KeyOfT>
class RBTree//红黑树
{};利用仿函数，传入节点的值，set将会返回key值，map将会的返回pair的first。这样就解决了比较大小的规则问题。
二、set/map的迭代器（红黑树的迭代器）
因为红黑树的中序遍历是有序的，可以根据中序遍历作为迭代器++--的依据。
STL源码采用下图结构，多搞了一个头结点。迭代器begin()可以指向header的左，迭代器end()指向header。
不过本文采用无头结点的常规红黑树仿写红黑树的迭代器。
1、红黑树的begin、end迭代器
2、红黑树迭代器的operator++
1、如果当前节点的右不为空，迭代器++返回右子树的最左节点
2、如果当前节点的右为空，迭代器++返回祖先（当前节点是父亲的左）(end()-1迭代器++返回nullptr即end())
template <class T>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
//1、右不为空，下一个节点是右树的最小节点
//2、右为空，去找右是父亲左的最近祖先
Self& operator++()//找中序的下一个节点,即根的右树的最左节点,返回值是一个迭代器的对象
{
if (_node->_right != nullptr)
{
Node* min = _node->_right;
while (min->_left != nullptr)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent != nullptr && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};3、红黑树迭代器的operator--
1、如果当前节点的左不为空，迭代器--返回左子树的最右节点
2、如果当前节点的左为空，迭代器--返回祖先（当前节点是父亲的右）
template <class T>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
Self& operator--()
{
if (_node->_left!=nullptr)
{
Node* max = _node;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent != nullptr && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};三、set的const迭代器
对于set和map，它们的key都是不能改的。set的value不能修改，map的value可以修改。
因为set的value是不能改的，所以它的底层将普通迭代器和const迭代器全部封装成const迭代器来“解决”：
//自己实现的，不代表STL
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;封装之后又会出现新问题，set使用迭代器其实都是在使用const迭代器，但是自己实现的红黑树的迭代器接口返回普通类型的迭代器，在Set.h中对this加上const“解决”：
iterator begin()const
{
return _t.begin();
}
iterator end()const
{
return _t.end();
}这时使用迭代器调用上方函数会发现红黑树返回了普通迭代器类型的迭代器，类型不匹配。在红黑树中补齐const版本的迭代器函数解决：
const_iterator begin()const//找红黑树最左节点
{
Node* left = _root;
while (left != nullptr && left->_left != nullptr)
{
left = left->_left;
}
return const_iterator(left);
}
const_iterator end()const
{
return const_iterator(nullptr);
}四、map的const迭代器
map的value是可以改的，所以要分别设计普通迭代器和const迭代器。
typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<const 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();
}五、迭代器类的拷贝构造
STL库中的普通迭代器都可以转换为const迭代器，这是迭代器类的拷贝构造所支持的。
这个拷贝构造有点特殊：
//红黑树的迭代器
template <class T,class Ref,class Ptr>//key/value、T&、T*
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
typedef __RBTreeIterator<T, T&, T*> iterator;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
__RBTreeIterator(const iterator& it)//const iterator本质还是普通迭代器
:_node(it._node)
{}
};1、当这个模板的的Ref和PTR被实例化为T&和T*时，__RBTreeIterator(const iterator& it)就是一个拷贝构造(没啥意义)
2、当这个模板的的Ref和PTR被实例化为const T&和const T*时，__RBTreeIterator(const iterator& it)就是一个构造函数，支持用普通迭代器去构造const迭代器。此时const迭代器的拷贝构造函数则由编译器自动生成，刚好满足迭代器值拷贝的特点。
六、整体代码
1、RBTree.h
#pragma once
#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
enum Color
{
RED,
BLACK,
};
template <class T>//T类型代表value
struct RBTreeNode
{
RBTreeNode(const T& data)
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _data(data)
, _col(RED)
{}
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
T _data;
Color _col;
};
//红黑树的迭代器
// key/value T& T*
template <class T,class Ref,class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
typedef __RBTreeIterator<T, T&, T*> iterator;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
__RBTreeIterator(const iterator& it)
:_node(it._node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()//返回类型的地址
{
return &_node->_data;
}
//1、右不为空，下一个节点是右树的最小节点
//2、右为空，去找右是父亲左的最近祖先
Self& operator++()//找中序的下一个节点,即根的右树的最左节点,返回值是一个迭代器的对象
{
if (_node->_right != nullptr)
{
Node* min = _node->_right;
while (min->_left != nullptr)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent != nullptr && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left!=nullptr)
{
Node* max = _node;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent != nullptr && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
//pair的比较是如果first小还要比second，我们只要比first，所以加了仿函数KeyOfT，用以取出first进行比较
//set->RBTree<K, K, SetKeyOfT>
//map->RBTree<const K, pair<K,V>, MapKeyOfT>
template <class K, class T,class KeyOfT>
class RBTree
{
public:
typedef __RBTreeIterator<T,T&,T*> iterator;
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()//找红黑树最左节点
{
Node* left = _root;
while (left!=nullptr&&left->_left!=nullptr)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin()const//找红黑树最左节点
{
Node* left = _root;
while (left != nullptr && left->_left != nullptr)
{
left = left->_left;
}
return const_iterator(left);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
typedef RBTreeNode<T> Node;
pair<iterator,bool> Insert(const T& data)//对于map来说data是pair
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//根节点给黑色
return make_pair(iterator(_root), true);//返回插入的节点
}
KeyOfT kot;//搞一个仿函数对象
//_root不为空
Node* parent = nullptr;
Node* cur = _root;
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);
Node* newNode = cur;//记录cur的地址，make_pair返回插入节点的地址
cur->_col = RED;//新插入节点给红色，可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同，必定违反规则。
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
cur->_parent = parent;//维护cur的父指针
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;//找到祖父
if (grandfather->_left == parent)//如果父亲是祖父的左孩子
{
Node* uncle = grandfather->_right;//找到叔叔
//情况一：叔叔存在且为红
if (uncle != nullptr && uncle->_col == RED)
{
//变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else//情况二或情况三
{
if (cur == parent->_left)//情况二，直线
{
RotateRight(grandfather);//右单旋
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三，折线
{
RotateLeft(parent);//左单旋
RotateRight(grandfather);//右单旋
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//如果父亲是祖父的右孩子
{
Node* uncle = grandfather->_left;
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//情况二，直线
{
//g
// p
// c
RotateLeft(grandfather);//左单旋
parent->_col = BLACK;
grandfather->_col = RED;
}
else//情况三，折线
{
//g
// p
//c
RotateRight(parent);//右单旋
RotateLeft(grandfather);//左单旋
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newNode), true);//返回插入的节点
}
void Inorder()
{
_Inorder(_root);
}
bool IsBalance()
{
return _IsBalance();
}
private:
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << kot(root->_data) << ":" << root->_data.second << endl;
_Inorder(root->_right);
}
bool Check(Node* root, int blackNum, const int ref)//检查有没有连续红节点
{
if (root == nullptr)
{
if (blackNum != ref)
{
cout << "路径上黑节点数量不一致" << endl;
return false;
}
return true;
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "违反规则，父子均为红" << endl;
return false;
}
return Check(root->_left, blackNum, ref) && Check(root->_right, blackNum, ref);
}
bool _IsBalance()
{
if (_root == nullptr)
return true;
if (_root->_col != BLACK)
{
return false;
}
//数一下一条路径黑色节点数量
int ref = 0;//统计一条路上黑色节点的数量
Node* left = _root;
while (left != nullptr)
{
if (left->_col == BLACK)
{
++ref;
}
left = left->_left;
}
return Check(_root, 0, ref);
}
void RotateLeft(Node* parent)//左单旋
{
Node* grandfather = parent->_parent;
Node* cur = parent->_right;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (grandfather->_left == parent)//需要判定parent原来属于grandfather的哪一边
grandfather->_left = cur;
else
grandfather->_right = cur;
cur->_parent = grandfather;
}
parent->_right = cur->_left;
if (cur->_left != nullptr)
cur->_left->_parent = parent;
cur->_left = parent;
parent->_parent = cur;
}
void RotateRight(Node* parent)//右单旋
{
Node* grandfather = parent->_parent;
Node* cur = parent->_left;
if (parent == _root)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (grandfather->_left == parent)
{
grandfather->_left = cur;
cur->_parent = grandfather;
}
else
{
grandfather->_right = cur;
cur->_parent = grandfather;
}
}
parent->_parent = cur;
parent->_left = cur->_right;
if (cur->_right != nullptr)
cur->_right->_parent = parent;
cur->_right = parent;
}
private:
Node* _root = nullptr;
};迭代器的begin(),end()接口放在红黑树这个类中，而operator++--放在迭代器这个类中，自己写一下循环遍历红黑树的代码就知道为什么这样设计了。
2、Set.h
#pragma once
#include "RBTree.h"
namespace jly
{
template <class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)//传入value
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
pair<iterator, bool> insert(const K& key)
{
pair<typename RBTree<K, K, SetKeyOfT>::iterator,bool> ret= _t.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}
iterator begin()const
{
return _t.begin();
}
iterator end()const
{
return _t.end();
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
void test2()
{
//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//int a[] = { 9,8,7,6,5,4,3,2,1};
set<int> s;
for (auto e : a)
{
s.insert(e);
}
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
}
}3、map.h
#pragma once
#include "RBTree.h"
namespace jly
{
template <class K,class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)//传入value
{
return kv.first;
}
};
public:
//typename是C++中用于指定一个类的类型的关键字。
//通常用于表示某个类型是一个类类型，而不是其他类型，如int等。
//这里不加typedef编译器无法区分iterator是一个类型还是一个静态变量。因为他俩都可以这么写。。
//所以从类模板取出内嵌类型就需要加typedef
typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
pair<iterator,bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin()const
{
return _t.begin();
}
const_iterator end()const
{
return _t.end();
}
V& operator[](const K& key)//传入key值
{
pair<iterator,bool> ret= _t.Insert(key,V());
return ret.first->second;//找到ret（make_pair<iterator,bool>）的first，解引用找到节点value
}
private:
RBTree<const K, pair<const K,V>, MapKeyOfT> _t;
};
void test1()
{
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//int a[] = { 9,8,7,6,5,4,3,2,1};
map<int,int> m;
for (auto e : a)
{
m.insert(make_pair(e,e));
}
map<int, int>::iterator it = m.begin();
while (it != m.end())
{
cout << (* it).first << " ";
++it;
}
cout << endl;
for (auto& e : m)
{
cout << e.first<<" ";
}
}
}