🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【C++的学习】
📝📝本篇内容：对于map和set的基本理解；KeyOfValue；typename；红黑树的迭代器；红黑树内部的更新；set的实现；map的实现；完整代码
⬆⬆⬆⬆上一篇：红黑树（map和set的底层）
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-
1.对于map和set的基本理解
在我们使用map和set的时候，会认为map的底层红黑树也是简单的模板K和V的键对值作为数据，其实不然，我们可以看一下源码
简单来说就如下图
上图展示了红黑树的结点中对于传来的第二个模板参数是作为存储的类型的
所有说其实第一个拿到的单独K类型，这是因为find，erase这些接口函数的参数是K
第二个模板参数决定了红黑树里面的结点里面存什么？是K还是KV
并且我们发现一个点，map的所存储的的K是const类型的，而我们的set就是正常的K，这是为什么呢？
首先不管是map还是set，对于K都是不能修改的，那么在设计迭代器时就要避免这种问题，map的V是可以进行修改的，所以说对于普通的迭代器就需要保证K不能被改掉，因此在存储时就得是const类型，这样不会被修改，同时不会影响V的修改。那么set是什么情况？其实在设计的时候动一下小脑筋，在声明时直接将红黑树的const迭代器声明为普通迭代器和const迭代器，这样在调用者看来其实没什么区别。
看到这个可能又会跳出新的疑问，KeyOfValue是什么？typename是什么？
2.KeyOfValue
我们先解答第一个问题
我们要思考一下，我们的set和map的底层都是红黑树，但是它们两者在实现上还是会有少许不同，比如在进行寻找插入位置和查找时只需要Key就行，但是map底层存储的是KV，set存储的是K，这就是导致了再进行比较时会出现歧义。因此需要一个单独的仿函数来进行解决，如果是map那么就返回KV中的K，如果是set，那么就直接返回K
3.typename
这个关键字的意义是为了能够指示模板声明或定义中的某个名称是类型名而非变量名，因为在使用
typedef RBTree::const_iterator iterator;
编译器也可能认为这是一个static成员变量，因此使用typename能够明确它是一个类型，否则就会报一堆的错误
4.红黑树的迭代器
我们需要实现map和set的迭代器，那么就必须将红黑树的迭代器给实现了
首先我们思考一下，map和set的迭代器的功能是顺序遍历一遍，那么红黑树也是一样的，也就是以中序的方式进行遍历，遍历的就只能是结点，那么第一个要遍历的就肯定是1，那结束呢，可以不可以是30？不行，因为30也是需要被迭代到的，那么只能是nullptr。
接下来我们来看遍历完1后是谁呢？应该是6，也就是说当右子树还有结点的情况下，就应该去右子树遍历。当6被遍历到后，它的左右都没有结点了，就该是8了，那也就是说我们得沿着根结点找，找到孩子结点是作为父结点左边的那个祖先
总结一下：
我们的begin是从1开始，end是nullptr
当右边不为空时，下一个就是右子树的最左结点
当右边为空时，沿着根路径，找孩子结点是父亲左孩子的那个祖先
上面是operator++的，那么operator- -就是相反的
当左边不为空时，下一个就是左子树的最右结点
当左边为空时，沿着根路径，找孩子结点是父亲右孩子的那个祖先
//迭代器
template<class T,class Ref,class Ptr>
struct __RBTreeIterator__
{
typedef __RBTreeIterator__<T, Ref, Ptr> self;//迭代器本身重命名
typedef RBTreeNode<T> Node;
__RBTreeIterator__(Node* node)//使用结点作为迭代器所使用的对象
:_node(node)
{}
//针对于set的insert函数返回的实际类型是const __RBTreeIterator__进行的特定处理
__RBTreeIterator__(const __RBTreeIterator__<T, T&, T*>& s)//如果是const实例化，这个函数是构造函数
{ //如果是普通实例化，这个函数是拷贝构造
_node = s._node;
}
//前置++
self operator++()
{
//右不为空，下一个就是右子树的最左结点
if (_node->_right != nullptr)
{
Node* cur = _node->_right;
while (cur->_left)//找出最左结点
{
cur = cur->_left;
}
_node = cur;
}
//右为空，沿着根路径，找孩子结点是父亲左边的那个祖先
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//parent可能会为空，即最后的结束end
while (parent && parent->_right== cur)//找结点是父亲左孩子的-注意别写反
{
//继续往上找
cur = parent;
parent = parent->_parent;
}
_node= parent;//找到了
}
return *this;
}
//前置--
self operator--()
{
//左不为空，下一个就是左子树的最右结点
if (_node->_left != nullptr)
{
Node* cur = _node->_left;//左子树结点
//找最右结点
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
//左为空，沿着根结点，找孩子结点是父结点右孩子的那个祖先
else
{
Node* parent = _node->_parent;//父结点
Node* cur = _node;
//parent可能是空
while (parent && parent->_left== cur)//找孩子结点是父结点右孩子的那个祖先-注意别写反
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//*的运算符重载
Ref operator*()
{
return _node->_data;
}
//结构体使用，->的运算符重载
Ptr operator->()
{
return &(_node->_data);
}
//!=运算符重载
bool operator!=(const self& s)
{
return s._node != _node;
}
Node* _node;
};
其中__RBTreeIterator__(const RBTreeIterator<T, T&, T*>& s)这个函数的问题要结合着set的插入函数来讲
//红黑树内部对于迭代器的实现
typedef __RBTreeIterator__<T, T&, T*> iterator;//迭代器
typedef __RBTreeIterator__<T, const T&, const T*> const_iterator;//const迭代器
//迭代器的起始
iterator begin()
{
//起始位置是最左结点
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
//迭代器的结束
iterator end()
{
return iterator(nullptr);
}
//const迭代器的起始
const_iterator begin()const
{
//起始位置是最左结点
Node* cur = _root;
while (cur->left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
//迭代器的结束
const_iterator end()const
{
return const_iterator(nullptr);
}
5.红黑树内部的更新
既然是要模拟实现map和set，那么红黑树内部也需要进行更改，将迭代器应用其中，如下很多返回值需要更改成键对值的形式
//RBTree.hpp
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
//结点颜色
enum Color
{
RED,
BLACK
};
//红黑树的结点
template<class T>
struct RBTreeNode
{
RBTreeNode(const T& data)
:_data(data)
{}
T _data;//修改
Color _col = RED;//结点的颜色
struct RBTreeNode* _parent = nullptr;//父结点
struct RBTreeNode* _left = nullptr;//左孩子
struct RBTreeNode* _right = nullptr;//右孩子
};
//迭代器
template<class T,class Ref,class Ptr>
struct __RBTreeIterator__
{
typedef __RBTreeIterator__<T, Ref, Ptr> self;//迭代器本身重命名
typedef RBTreeNode<T> Node;
__RBTreeIterator__(Node* node)//使用结点作为迭代器所使用的对象
:_node(node)
{}
//针对于set的insert函数返回的实际类型是const __RBTreeIterator__进行的特定处理
__RBTreeIterator__(const __RBTreeIterator__<T, T&, T*>& s)//如果是const实例化，这个函数是构造函数
{ //如果是普通实例化，这个函数是拷贝构造
_node = s._node;
}
//前置++
self operator++()
{
//右不为空，下一个就是右子树的最左结点
if (_node->_right != nullptr)
{
Node* cur = _node->_right;
while (cur->_left)//找出最左结点
{
cur = cur->_left;
}
_node = cur;
}
//右为空，沿着根路径，找孩子结点是父亲左边的那个祖先
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//parent可能会为空，即最后的结束end
while (parent && parent->_right== cur)//找结点是父亲左孩子的-注意别写反
{
//继续往上找
cur = parent;
parent = parent->_parent;
}
_node= parent;//找到了
}
return *this;
}
//前置--
self operator--()
{
//左不为空，下一个就是左子树的最右结点
if (_node->_left != nullptr)
{
Node* cur = _node->_left;//左子树结点
//找最右结点
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
//左为空，沿着根结点，找孩子结点是父结点右孩子的那个祖先
else
{
Node* parent = _node->_parent;//父结点
Node* cur = _node;
//parent可能是空
while (parent && parent->_left== cur)//找孩子结点是父结点右孩子的那个祖先-注意别写反
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//*的运算符重载
Ref operator*()
{
return _node->_data;
}
//结构体使用，->的运算符重载
Ptr operator->()
{
return &(_node->_data);
}
//!=运算符重载
bool operator!=(const self& s)
{
return s._node != _node;
}
Node* _node;
};
//红黑树的模板
template<class K, class T,class KeyOfValue>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator__<T, T&, T*> iterator;//迭代器
typedef __RBTreeIterator__<T, const T&, const T*> const_iterator;//const迭代器
//迭代器的起始
iterator begin()
{
//起始位置是最左结点
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
//迭代器的结束
iterator end()
{
return iterator(nullptr);
}
//const迭代器的起始
const_iterator begin()const
{
//起始位置是最左结点
Node* cur = _root;
while (cur->left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
//迭代器的结束
const_iterator end()const
{
return const_iterator(nullptr);
}
//析构函数
~RBTree()
{
_Destory(_root);
_root = nullptr;
}
//查找函数
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
//当前结点小于查找的结点，往右边找
if (KeyOfValue()(cur->_data)< key)//修改比较方式
{
cur = cur->_right;
}
//当前结点大于查找的结点，往左边找
else if (KeyOfValue()(cur->_data) > key)
{
cur = cur->_left;
}
else//找到了
{
return cur;
}
}
return nullptr;//没有找到
}
pair<iterator,bool> Insert(const T& data)
{
Node* newnode = new Node(data);
//判断是否是空树
if (_root == nullptr)
{
_root = newnode;
_root->_col = BLACK;
return make_pair(iterator(_root), true);//修改返回值
}
else
{
Node* cur = _root;
Node* parent = nullptr;//记录父结点
//寻找合适的插入位置
while (cur)
{
//当前结点比插入结点小，往右走
if (KeyOfValue()(cur->_data) < KeyOfValue()(data))//修改取值方式
{
parent = cur;
cur = cur->_right;
}
//当前结点比插入结点大，往左走
else if (KeyOfValue()(cur->_data) > KeyOfValue()(data))//修改取值方式
{
parent = cur;
cur = cur->_left;
}
else//相等
{
return make_pair(iterator(cur),false);//修改返回值
}
}
//在父结点的右边插入
if (KeyOfValue()(parent->_data) < KeyOfValue()(data))//修改取值方式
{
parent->_right = newnode;
}
//在父结点的左边插入
else
{
parent->_left = newnode;
}
cur = newnode;
cur->_parent = parent;//插入结点的父结点
//进行调整，保持平衡
Node* grandfather = parent->_parent;//爷爷结点
while (parent && parent->_col == RED)//父结点只要存在并且为红就需要调整
{
//父结点在爷爷结点的左边
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;//叔叔结点
//叔叔结点存在并且为红色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;//父结点和叔叔结点的颜色变为黑色
grandfather->_col = RED;//爷爷结点的颜色变成红色，这样此路径上的黑结点个数不变
//继续向上调整
cur = grandfather;
parent = grandfather->_parent;
}
//叔叔结点不存在或者存在且为黑
else
{
// g
// p u
// c
//cur是parent的左孩子
if (cur == parent->_left)
{
//进行右单旋
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
// g
// p u
// c
else//cur是parent的右孩子
{
//先进行左单旋
RotateL(parent);
//然后进行右单旋
RotateR(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//不需要再向上调整了
}
}
//父结点在爷爷结点的右边
else
{
Node* uncle = grandfather->_left;//叔叔结点
//叔叔结点存在且为红
if (uncle && uncle->_col == RED)
{
//叔叔结点和父结点的颜色变成黑色
uncle->_col = parent->_col = BLACK;
//爷爷结点变成红色
grandfather->_col = RED;
//继续更新
cur = grandfather;
parent = grandfather->_parent;
}
else//叔叔结点不存在或者叔叔结点为黑色
{
// g
// u p
// c
//当前结点是父结点的右孩子
if (cur == parent->_right)
{
//进行左单旋
RotateL(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
// g
// u p
// c
else//当前结点是父结点的左孩子
{
//先进行右单旋
RotateR(parent);
//再进行左单旋
RotateL(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//情况一需要设置，其余情况是为了以防万一保证根结点一定是黑色的
_root->_col = BLACK;
return make_pair(iterator(cur), true);//修改返回值
}
}
// //中序遍历
// void Inorder()
// {
// _Inorder(_root);
// }
//
// //红黑树的高度
// int Height()
// {
// return _Height(_root);
// }
//
//
// bool IsBlance()
// {
// //先检查根结点
// if (_root && _root->_col == RED)
// {
// cout << "root is Red" << endl;
// return false;
// }
//
// //计算出一条路径上黑色结点的个数
// int refer_val = 0;
// Node* cur = _root;
// while (cur)
// {
// if (cur->_col == BLACK)
// {
// refer_val++;
// }
// cur = cur->_left;
// }
//
// //检查是否每条路径上的黑色结点数量都相同
// return _CheckBlack(_root, 0, refer_val);
// }
//
//
private:
//销毁函数
void _Destory(Node* root)
{
if (root == nullptr)
{
return;
}
//类似于后序遍历的思想，必须最后销毁根结点，否则会出现指针悬空
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
//private:
// //测试函数
//
// //检查每条路径上黑色结点数量是否相同
// bool _CheckBlack(Node* root, int count, int refer_val)
// {
// //走到路径头了
// if (root == nullptr)
// {
// //不相等说明数量不对
// if (count != refer_val)
// {
// cout << "the error path has " << count << "Black node" << endl;
// return false;
// }
// else
// {
// return true;
// }
// }
//
// //遇到黑色结点就++
// if (root->_col == BLACK)
// {
// count++;
// }
//
// //红色结点也要注意一下，不能连续两个结点是红色
// if (root->_col == RED && root->_parent->_col == RED)
// {
// cout << "Both " << root->_kv.first << " and its parent "\
// << root->_parent->_kv.first << " is Red node" << endl;
// return false;
// }
//
// //分别去左右两条路径去计算判断
// return _CheckBlack(root->_left, count, refer_val) && _CheckBlack(root->_right, count, refer_val);
// }
//
//
// //中序遍历
// void _Inorder(Node* root)
// {
// if (root == nullptr)
// {
// return;
// }
// _Inorder(root->_left);
// cout << root->_kv.first << " ";
// _Inorder(root->_right);
// }
//
// //红黑树的高度
// int _Height(Node* root)
// {
// if (root == nullptr)
// {
// return 0;
// }
// int left = _Height(root->_left);
// int right = _Height(root->_right);
// return left > right ? left + 1 : right + 1;
// }
//
private:
//旋转函数
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;//父结点的右结点，未来的新根结点
Node* subRL = subR->_left;//需要重新连接的，父结点的右结点的左结点
Node* pparent = parent->_parent;//现在父结点的父结点
//1.先处理parent的父结点
//①本身就是根结点
if (pparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
//②parent是父结点的左孩子
if (pparent->_left == parent)
{
//修改parent父结点的左孩子指向
pparent->_left = subR;
}
//③parent是父结点的右孩子
else
{
//修改parent父结点的右孩子指向
pparent->_right = subR;
}
//修改subR的父结点
subR->_parent = pparent;
}
//2.处理subR左孩子的情况
subR->_left = parent;
parent->_parent = subR;
//3.处理subRL的指向
if (subRL)
subRL->_parent = parent;
parent->_right = subRL;
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;//父结点的左结点，未来的新根结点
Node* subLR = subL->_right;//父结点的左孩子的右结点，需要重新连接的
Node* pparent = parent->_parent;//现在父结点的父结点
//1.先处理父结点
//①本身就是根结点，没有父结点
if (pparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
//②parent是父结点的左孩子
if (pparent->_left == parent)
{
//修改pparent的左孩子指向
pparent->_left = subL;
}
//③parent是父结点的右孩子
else
{
//修改pparent的右孩子指向
pparent->_right = subL;
}
subL->_parent = pparent;//新根结点的父结点指向修改
}
//2.处理subL的情况
subL->_right = parent;//变成新的根结点，原根结点变成其右孩子
parent->_parent = subL;
//3.处理subLR的情况
if (subLR)
{
subLR->_parent = parent;//subLR父结点指向修改
}
//parent的左孩子指向修改
parent->_left = subLR;
}
private:
Node* _root = nullptr;
};
6.set实现
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include "RBTree.hpp"
using namespace std;
namespace lnb
{
template<class K>
class set
{
private:
//红黑树进行比较时需要用来区分map和set取不同的值
struct KeyOfValue
{
const K& operator()(const K& data)
{
return data;
}
};
//第一个K用于find，erase这些函数，第二个K是真正存储的结点内容
typedef RBTree<K, K, KeyOfValue> RBTree;
public:
//迭代器
typedef typename RBTree::const_iterator iterator;//特殊设计，保证key不会被修改
typedef typename RBTree::const_iterator const_iterator;
//普通迭代器
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
//const迭代器
const_iterator begin()const
{
return _tree.begin();
}
const iterator end()const
{
return _tree.end();
}
//插入函数
pair<iterator, bool> insert(const K& key)
{
return _tree.Insert(key);
}
private:
RBTree _tree;
};
void TestSet()
{
set<int> s;
s.insert(12);
s.insert(10);
s.insert(7);
s.insert(14);
s.insert(9);
for (auto& e : s)
{
cout << e << " ";
}
}
}
我们这边来特别看一下set的插入函数，它的返回值的情况我们在之前的文章中讲过，我们这次主要分析一下它有什么问题。首先我们前面将自己的普通迭代器和const迭代器都设置成了红黑树的const迭代器，那么也就是对于insert而言，它的返回值中的K类型本质上是是红黑树中的const迭代器，然后我们insert内部调用的是红黑树内部的Insert函数，但是在红黑树内部的Insert的返回值是普通的迭代器，这就会导致一个问题，就是普通的迭代器要赋值给const迭代器。因此我们在迭代器内部实现了一个函数，前面已经展示了，将普通的迭代器类型作为参数，形成一个成员函数，对于const类型的迭代器进行实例化而言，这就是一个构造函数，完美解决set的insert函数问题，对于普通类型的迭代器进行实例化而言，这是一个拷贝构造函数，无伤大雅，和默认的拷贝构造函数功能一样。
//针对于set的insert函数返回的实际类型是const __RBTreeIterator__进行的特定处理
__RBTreeIterator__(const __RBTreeIterator__<T, T&, T*>& s)//如果是const实例化，这个函数是构造函数
{ //如果是普通实例化，这个函数是拷贝构造
_node = s._node;
}
7.map的实现
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <utility>
#include "RBTree.hpp"
using namespace std;
namespace lnb
{
template<class K,class V>
class map
{
private:
//红黑树进行比较时需要用来区分map和set取不同的值
struct KeyOfValue
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
private:
//底层是红黑树
typedef RBTree<K, pair<const K, V>, KeyOfValue> RBTree;
public:
typedef typename RBTree::iterator iterator;//typename的作用是告诉编译器::找的是类型
typedef typename RBTree::const_iterator const_iterator;
//map的迭代器底层是调用红黑树的begin和end
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
const_iterator begin()const
{
return _tree.begin();
}
const_iterator end()const
{
return _tree.end();
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _tree.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator,bool> it=insert(make_pair(key, V()));
return (it.first)->second;
}
private:
//底层是红黑树
RBTree _tree;
};
//测试
void TestMap()
{
map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(5, 0));
m.insert(make_pair(3, 1));
map<int, int>::iterator it=m.begin();
while (it != m.end())
{
cout << it->first << " ";
++it;
}
cout << m[5] << endl;
}
}
map的相关情况其实都已经讲过了，像operator[ ]的实现原理在介绍map和set使用的时候就讲过，本质上就是将insert函数的返回值中的迭代器中的V返回回去，还有就是KeyOfValue前面也讲了。
8.完整代码
//Map.hpp
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <utility>
#include "RBTree.hpp"
using namespace std;
namespace lnb
{
template<class K,class V>
class map
{
private:
//红黑树进行比较时需要用来区分map和set取不同的值
struct KeyOfValue
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
private:
//底层是红黑树
typedef RBTree<K, pair<const K, V>, KeyOfValue> RBTree;
public:
typedef typename RBTree::iterator iterator;//typename的作用是告诉编译器::找的是类型
typedef typename RBTree::const_iterator const_iterator;
//map的迭代器底层是调用红黑树的begin和end
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
const_iterator begin()const
{
return _tree.begin();
}
const_iterator end()const
{
return _tree.end();
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _tree.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator,bool> it=insert(make_pair(key, V()));
return (it.first)->second;
}
private:
//底层是红黑树
RBTree _tree;
};
//测试
void TestMap()
{
map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(5, 0));
m.insert(make_pair(3, 1));
map<int, int>::iterator it=m.begin();
while (it != m.end())
{
cout << it->first << " ";
++it;
}
cout << m[5] << endl;
}
}
//RBTree.hpp
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
//结点颜色
enum Color
{
RED,
BLACK
};
//红黑树的结点
template<class T>
struct RBTreeNode
{
RBTreeNode(const T& data)
:_data(data)
{}
T _data;//修改
Color _col = RED;//结点的颜色
struct RBTreeNode* _parent = nullptr;//父结点
struct RBTreeNode* _left = nullptr;//左孩子
struct RBTreeNode* _right = nullptr;//右孩子
};
//迭代器
template<class T,class Ref,class Ptr>
struct __RBTreeIterator__
{
typedef __RBTreeIterator__<T, Ref, Ptr> self;//迭代器本身重命名
typedef RBTreeNode<T> Node;
__RBTreeIterator__(Node* node)//使用结点作为迭代器所使用的对象
:_node(node)
{}
//针对于set的insert函数返回的实际类型是const __RBTreeIterator__进行的特定处理
__RBTreeIterator__(const __RBTreeIterator__<T, T&, T*>& s)//如果是const实例化，这个函数是构造函数
{ //如果是普通实例化，这个函数是拷贝构造
_node = s._node;
}
//前置++
self operator++()
{
//右不为空，下一个就是右子树的最左结点
if (_node->_right != nullptr)
{
Node* cur = _node->_right;
while (cur->_left)//找出最左结点
{
cur = cur->_left;
}
_node = cur;
}
//右为空，沿着根路径，找孩子结点是父亲左边的那个祖先
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//parent可能会为空，即最后的结束end
while (parent && parent->_right== cur)//找结点是父亲左孩子的-注意别写反
{
//继续往上找
cur = parent;
parent = parent->_parent;
}
_node= parent;//找到了
}
return *this;
}
//前置--
self operator--()
{
//左不为空，下一个就是左子树的最右结点
if (_node->_left != nullptr)
{
Node* cur = _node->_left;//左子树结点
//找最右结点
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
//左为空，沿着根结点，找孩子结点是父结点右孩子的那个祖先
else
{
Node* parent = _node->_parent;//父结点
Node* cur = _node;
//parent可能是空
while (parent && parent->_left== cur)//找孩子结点是父结点右孩子的那个祖先-注意别写反
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//*的运算符重载
Ref operator*()
{
return _node->_data;
}
//结构体使用，->的运算符重载
Ptr operator->()
{
return &(_node->_data);
}
//!=运算符重载
bool operator!=(const self& s)
{
return s._node != _node;
}
Node* _node;
};
//红黑树的模板
template<class K, class T,class KeyOfValue>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator__<T, T&, T*> iterator;//迭代器
typedef __RBTreeIterator__<T, const T&, const T*> const_iterator;//const迭代器
//迭代器的起始
iterator begin()
{
//起始位置是最左结点
Node* cur = _root;
while (cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
//迭代器的结束
iterator end()
{
return iterator(nullptr);
}
//const迭代器的起始
const_iterator begin()const
{
//起始位置是最左结点
Node* cur = _root;
while (cur->left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
//迭代器的结束
const_iterator end()const
{
return const_iterator(nullptr);
}
//析构函数
~RBTree()
{
_Destory(_root);
_root = nullptr;
}
//查找函数
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
//当前结点小于查找的结点，往右边找
if (KeyOfValue()(cur->_data)< key)//修改比较方式
{
cur = cur->_right;
}
//当前结点大于查找的结点，往左边找
else if (KeyOfValue()(cur->_data) > key)
{
cur = cur->_left;
}
else//找到了
{
return cur;
}
}
return nullptr;//没有找到
}
pair<iterator,bool> Insert(const T& data)
{
Node* newnode = new Node(data);
//判断是否是空树
if (_root == nullptr)
{
_root = newnode;
_root->_col = BLACK;
return make_pair(iterator(_root), true);//修改返回值
}
else
{
Node* cur = _root;
Node* parent = nullptr;//记录父结点
//寻找合适的插入位置
while (cur)
{
//当前结点比插入结点小，往右走
if (KeyOfValue()(cur->_data) < KeyOfValue()(data))//修改取值方式
{
parent = cur;
cur = cur->_right;
}
//当前结点比插入结点大，往左走
else if (KeyOfValue()(cur->_data) > KeyOfValue()(data))//修改取值方式
{
parent = cur;
cur = cur->_left;
}
else//相等
{
return make_pair(iterator(cur),false);//修改返回值
}
}
//在父结点的右边插入
if (KeyOfValue()(parent->_data) < KeyOfValue()(data))//修改取值方式
{
parent->_right = newnode;
}
//在父结点的左边插入
else
{
parent->_left = newnode;
}
cur = newnode;
cur->_parent = parent;//插入结点的父结点
//进行调整，保持平衡
Node* grandfather = parent->_parent;//爷爷结点
while (parent && parent->_col == RED)//父结点只要存在并且为红就需要调整
{
//父结点在爷爷结点的左边
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;//叔叔结点
//叔叔结点存在并且为红色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;//父结点和叔叔结点的颜色变为黑色
grandfather->_col = RED;//爷爷结点的颜色变成红色，这样此路径上的黑结点个数不变
//继续向上调整
cur = grandfather;
parent = grandfather->_parent;
}
//叔叔结点不存在或者存在且为黑
else
{
// g
// p u
// c
//cur是parent的左孩子
if (cur == parent->_left)
{
//进行右单旋
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
// g
// p u
// c
else//cur是parent的右孩子
{
//先进行左单旋
RotateL(parent);
//然后进行右单旋
RotateR(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;//不需要再向上调整了
}
}
//父结点在爷爷结点的右边
else
{
Node* uncle = grandfather->_left;//叔叔结点
//叔叔结点存在且为红
if (uncle && uncle->_col == RED)
{
//叔叔结点和父结点的颜色变成黑色
uncle->_col = parent->_col = BLACK;
//爷爷结点变成红色
grandfather->_col = RED;
//继续更新
cur = grandfather;
parent = grandfather->_parent;
}
else//叔叔结点不存在或者叔叔结点为黑色
{
// g
// u p
// c
//当前结点是父结点的右孩子
if (cur == parent->_right)
{
//进行左单旋
RotateL(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
// g
// u p
// c
else//当前结点是父结点的左孩子
{
//先进行右单旋
RotateR(parent);
//再进行左单旋
RotateL(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//情况一需要设置，其余情况是为了以防万一保证根结点一定是黑色的
_root->_col = BLACK;
return make_pair(iterator(cur), true);//修改返回值
}
}
// //中序遍历
// void Inorder()
// {
// _Inorder(_root);
// }
//
// //红黑树的高度
// int Height()
// {
// return _Height(_root);
// }
//
//
// bool IsBlance()
// {
// //先检查根结点
// if (_root && _root->_col == RED)
// {
// cout << "root is Red" << endl;
// return false;
// }
//
// //计算出一条路径上黑色结点的个数
// int refer_val = 0;
// Node* cur = _root;
// while (cur)
// {
// if (cur->_col == BLACK)
// {
// refer_val++;
// }
// cur = cur->_left;
// }
//
// //检查是否每条路径上的黑色结点数量都相同
// return _CheckBlack(_root, 0, refer_val);
// }
//
//
private:
//销毁函数
void _Destory(Node* root)
{
if (root == nullptr)
{
return;
}
//类似于后序遍历的思想，必须最后销毁根结点，否则会出现指针悬空
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
//private:
// //测试函数
//
// //检查每条路径上黑色结点数量是否相同
// bool _CheckBlack(Node* root, int count, int refer_val)
// {
// //走到路径头了
// if (root == nullptr)
// {
// //不相等说明数量不对
// if (count != refer_val)
// {
// cout << "the error path has " << count << "Black node" << endl;
// return false;
// }
// else
// {
// return true;
// }
// }
//
// //遇到黑色结点就++
// if (root->_col == BLACK)
// {
// count++;
// }
//
// //红色结点也要注意一下，不能连续两个结点是红色
// if (root->_col == RED && root->_parent->_col == RED)
// {
// cout << "Both " << root->_kv.first << " and its parent "\
// << root->_parent->_kv.first << " is Red node" << endl;
// return false;
// }
//
// //分别去左右两条路径去计算判断
// return _CheckBlack(root->_left, count, refer_val) && _CheckBlack(root->_right, count, refer_val);
// }
//
//
// //中序遍历
// void _Inorder(Node* root)
// {
// if (root == nullptr)
// {
// return;
// }
// _Inorder(root->_left);
// cout << root->_kv.first << " ";
// _Inorder(root->_right);
// }
//
// //红黑树的高度
// int _Height(Node* root)
// {
// if (root == nullptr)
// {
// return 0;
// }
// int left = _Height(root->_left);
// int right = _Height(root->_right);
// return left > right ? left + 1 : right + 1;
// }
//
private:
//旋转函数
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;//父结点的右结点，未来的新根结点
Node* subRL = subR->_left;//需要重新连接的，父结点的右结点的左结点
Node* pparent = parent->_parent;//现在父结点的父结点
//1.先处理parent的父结点
//①本身就是根结点
if (pparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
//②parent是父结点的左孩子
if (pparent->_left == parent)
{
//修改parent父结点的左孩子指向
pparent->_left = subR;
}
//③parent是父结点的右孩子
else
{
//修改parent父结点的右孩子指向
pparent->_right = subR;
}
//修改subR的父结点
subR->_parent = pparent;
}
//2.处理subR左孩子的情况
subR->_left = parent;
parent->_parent = subR;
//3.处理subRL的指向
if (subRL)
subRL->_parent = parent;
parent->_right = subRL;
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;//父结点的左结点，未来的新根结点
Node* subLR = subL->_right;//父结点的左孩子的右结点，需要重新连接的
Node* pparent = parent->_parent;//现在父结点的父结点
//1.先处理父结点
//①本身就是根结点，没有父结点
if (pparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
//②parent是父结点的左孩子
if (pparent->_left == parent)
{
//修改pparent的左孩子指向
pparent->_left = subL;
}
//③parent是父结点的右孩子
else
{
//修改pparent的右孩子指向
pparent->_right = subL;
}
subL->_parent = pparent;//新根结点的父结点指向修改
}
//2.处理subL的情况
subL->_right = parent;//变成新的根结点，原根结点变成其右孩子
parent->_parent = subL;
//3.处理subLR的情况
if (subLR)
{
subLR->_parent = parent;//subLR父结点指向修改
}
//parent的左孩子指向修改
parent->_left = subLR;
}
private:
Node* _root = nullptr;
};
//Set.hpp
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include "RBTree.hpp"
using namespace std;
namespace lnb
{
template<class K>
class set
{
private:
//红黑树进行比较时需要用来区分map和set取不同的值
struct KeyOfValue
{
const K& operator()(const K& data)
{
return data;
}
};
//第一个K用于find，erase这些函数，第二个K是真正存储的结点内容
typedef RBTree<K, K, KeyOfValue> RBTree;
public:
//迭代器
typedef typename RBTree::const_iterator iterator;//特殊设计，保证key不会被修改
typedef typename RBTree::const_iterator const_iterator;
//普通迭代器
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
//const迭代器
const_iterator begin()const
{
return _tree.begin();
}
const iterator end()const
{
return _tree.end();
}
//插入函数
pair<iterator, bool> insert(const K& key)
{
return _tree.Insert(key);
}
private:
RBTree _tree;
};
void TestSet()
{
set<int> s;
s.insert(12);
s.insert(10);
s.insert(7);
s.insert(14);
s.insert(9);
for (auto& e : s)
{
cout << e << " ";
}
}
}
//main.cc
#include "Set.hpp"
#include "Map.hpp"
int main()
{
lnb::TestMap();
lnb::TestSet();
return 0;
}
🌸🌸红黑树的知识大概就讲到这里啦，博主后续会继续更新更多数据结构的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪