在之前的红黑树专题当中我们了解的红黑树的基本概念，在此之后我们试着实现了红代码。在之前的set和map专题当中我们已经了解了map和set的使用方法，了解了map和set如何使用，接下来就试着基于之前实现的红黑树来封装出出我们自己实现的mymap和myset。相信通过本篇的学习能让你对map和set有更深的理解，一起加油吧！！！
1.文件的创建
在实现myset和mymap的过程当中我们需要实现以下的文件：
BRTree.h：实现红黑树myset.h：实现myset
mymap：实现mymap
test.cpp：用于验证实现的myset和mymap是否满足我们的要求
1.基于实现的红黑树实现myset和mymap
1.1 根据实际情况修改红黑树
之前实现的红黑树实现的节点存储的是key，val的键值对，通过之前对map以及set的学习我们知道set是只有一个模板参数的，而map是有两个模板参数的。那么问题就来了，之前实现的红黑树是含有两个模板参数的，这是符合实现map的要求的，但是与set是相违背的，那么是否要给myset和mymap分别实现一份底层的红黑树代码呢？
这样的实现方法确实是可以实现我们的要求的，但是这种方法实现的代码是很冗余的，在两个红黑树当中有非常大部分的代码是完全相同的，因此接下来我们就要试着试着基于一棵红黑树的方式来同时实现myset和mymap
注：在此当前实现myset和mymap不考虑最后一个模板参数
在此之前实现的红黑树的两个模板参数分别是K和V，那么如何让实现的myset也能基于该红黑树呢？
其实解决方法很简单，只需要在实现myset时也使用两个模板参数来实现，这样就可以基于同一棵红黑树实现myset和mymap，那么接下来就在myset.h和mymap内分别实现基本的框架
myset：
#pragma once
#include"BRTree.h"
namespace zhz
{
class set
{
public:
//实现set插入等基本的功能……
private:
//创建一个红黑树的对象
RBTree<K,K> _rbtree;
};
}mymap：
#pragma once
#include"BRTree.h"
namespace zhz
{
template<class K,class V>
class map
{
public:
//实现map内插入等的基本功能……
private:
//创建红黑树的对象
RBTree<K, pair<K,V>> _rbtree;
};
}注：以上实现的set和map是放在zhz的命名空间内，这样就不会和标准模板库当中的map和set出现冲突。
在此以上我们看似解决了myset和mymap底层使用的红黑树无法共用的问题，但是我们真的解决了本质的问题了吗，如果是按照以上的方式实现那么在myset内部创建的红黑树对象的第一个模板参数和第二个模板参数都是K，mymap的第一个模板参数为K；第二个模板参数为V。其实此时问题就出现了，现在在红黑树实现插入功能insert时我们要实现的是在set内部插入时进行节点值的比较时需要比较的是K的值，但是在map当中是要比较kv键值对当中k的值；并且之后创建新的节点需要存储的是kv键值对。那么此时红黑树当中以K、V为模板参数就无法满足要求。
那么此时要如何修改红黑树呢？
其实只需要再改变红黑树对应的模板参数即可，即将模板参数从K、V修改为K、T，在此T在set当中传的就是K值，而在map当中就改为传键值对pair，这样就可以避免以上在红黑树的insert当种出现以上的问题。
按照以上的思路先要把表示红黑树节点的结构体BRTreeNode进行修改
enum colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _date;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
colour _col;
RBTreeNode(const T& date)
:_date(date)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{
}
};以上就将BRTreeNode的类模板参数修改为T，再将内部的成员变量从键值对pair修改为T类型的对象，这样就可以实现当T为K时红黑树节点内的值就为K，当T为pair时红黑树节点内的值为pair键值对。
接下来再对BRTree类进行修改
在此就只需要将RBTree类内的第二个模板参数修改为T，之后在RBTree内的insert内就可以根据T具体的类型来将对应的元素插入到红黑树当中。
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& date)
{
//当插入节点时的树为空时就将新插入的节点置为树的根节点，且颜色变为黑
if (_root == nullptr)
{
_root = new Node(date);
_root->_col = BLACK;
return true;
}
//寻找合适的插入位置
Node* cur = _root;
Node* Parent = nullptr;
while (cur)
{
if (cur->_date< date)
{
Parent = cur;
cur = cur->_right;
}
else if (cur->_date > date)
{
Parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//创建新节点
cur = new Node(date);
if (Parent->_date < date)
{
Parent->_right = cur;
}
else
{
Parent->_left = cur;
}
cur->_parent = Parent;
cur->_col = RED;
Node* ret = cur;
while (Parent && Parent->_col == RED)
{
Node* grandfather = Parent->_parent;
//父节点为祖父节点的左节点时
// g
// p u
//c
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
{
//当c为p的左节点时
// g
// p u
//c
if (Parent->_left == cur)
{
RotateR(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的右节点时
// g
// p u
// c
else
{
RotateL(Parent);
RotateR(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
//父节点为祖父节点的右节点时
// g
// u p
// c
else
{
Node* uncle = grandfather->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
//叔叔不存在或者为黑
else
{
//当c为p的右节点时
// g
// u p
// c
if (Parent->_right == cur)
{
RotateL(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的左节点时
// g
// u p
// c
else
{
RotateR(Parent);
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
//无论以上是否进行调整都将根结点的颜色置为黑
_root->_col = BLACK;
return true ;
}
Node* Find(const K& val)
{
if (_root == nullptr)
{
return nullptr;
}
Node* cur = _root;
while (cur)
{
if (cur->_val.first < val)
{
cur = cur->_left;
}
else if (cur->_val.first > val)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
private:
Node* _root = nullptr;
void RotateR(Node* Parent)
{
Node* subL = Parent->_left;
Node* subLR = subL->_right;
if (subLR != nullptr)
{
subLR->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_left = subLR;
Parent->_parent = subL;
subL->_right = Parent;
if (tmpNode != nullptr)
{
if (tmpNode->_left == Parent)
{
tmpNode->_left = subL;
}
else
{
tmpNode->_right = subL;
}
subL->_parent = tmpNode;
}
else
{
_root = subL;
subL->_parent = nullptr;
}
}
void RotateL(Node* Parent)
{
Node* subR = Parent->_right;
Node* subRL = subR->_left;
if (subRL != nullptr)
{
subRL->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_right = subRL;
Parent->_parent = subR;
subR->_left = Parent;
if (tmpNode != nullptr)
{
if (tmpNode->_left == Parent)
{
tmpNode->_left = subR;
}
else
{
tmpNode->_right = subR;
}
subR->_parent = tmpNode;
}
else
{
_root = subR;
subR->_parent = nullptr;
}
}
void Destory(Node* root)
{
if (root == nullptr)return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
};我们知道在set当中要进行比较就只需要比较K的值，但是map需要比较的是K、V当中的K，但是pair默认的比较是不是符合我们的要求呢？
接下来就通过官方文档看看
relational operators (pair) - C++ Reference
通过文档就可以看出pair的默认的比较方式其实是先比较pair当中的first，当不满足要求之后再比较second的值。这种比较方法是无法满足我们的要求的，这是因为map进行比较的方式其实是要直接比较对应的K，因此在红黑树类当中要创建第三个模板参数来实现仿函数。
template<class K, class T,class keyOfT>并且在set和map类当中实现对应的仿函数来实现自定义的比较
set内的仿函数：
struct SetkeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
map内的仿函数：
struct MapkeyOfT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};实现了对应的仿函数之后接下来还需要将红黑树的对象以及红黑树的类模板参数进行修改。
//set内BRTree对象
RBTree<K, K,SetkeyOfT> _rbtree;
//map内BRTree对象
RBTree<K, pair<K,V>,MapkeyOfT> _rbtree;BRTre类模板参数如下所示：
template<class K, class T,class keyOfT>有了仿函数keyOfT之后接下来在BRTree类内部就可以创建对应的keyOfT对象来实现红黑树节点值的比较
实际上map和set的源码当中就是使用以上大致的思路实现的，如下图所示：
但是从以上就可以看出这里源码命名风格比较乱，set模板参数用的Key命名，map用的是Key和T命名，而rb_tree用的又是Key和Value。
1.2 iterator实现
通过之前set和map的学习我们知道这两个容器是支持迭代器的。因此现在要实现我们实现的myset和mymap支持迭代器就需要先实现红黑树的迭代器，之后再set和map内实现调用红黑树内的迭代器来实现容器内的迭代器，但是现在我们实现的红黑树当中目前是没有实现迭代器的，因此接下来先要来实现红黑树内的迭代器。
和实现链表的迭代器类似，在此实现红黑树的迭代器也是创建一个红黑树迭代器的类，将其命名为BRTreeIterator，类的参数为T。再该类内成员变量就是指向当前节点的指针。
template<class T>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T> Self;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{
}
//运算符重载函数……
};与之前实现lis类似在实现迭代器时需要实现->、*等运算符的重载函数，在此我们先将*等简单的函数实现，实现代码如所示：
T& operator*()
{
return _node->_date;
}
T* operator->()
{
return &_node->_date;
}
接下来在就需要实现++，--的运算符重载函数，不过和之前实现list不同的时在红黑树当中要在迭代器当中实现这两个运算符的重载函数不再像之前的链表一样直接访问当前节点的下一个节点即可，我们需要再分析红黑树的结构再来试着实现这两个函数的代码。
首先来分析++运算符重载函数该如何实现
在此我们知道在红黑树当中使用迭代器访问红黑树输出的结果就是中序遍历的结果，而在二叉树当进行中序遍历就是进行根->左->右的操作。因此接下来我们就试着在一棵红黑树当中分析得到当前节点中序遍历的下一个节点该如何操作。
例如以下的红黑树：
当我们要找到值为15的节点的下一个节点就需要找出路径上节点为其父节点的左孩子节点，此时该节点就是接下来要遍历的节点；以上的红黑树当中对应的节点就是值为18的节点。另外一种就是像以上的红黑树当中值为30的节点，要得到该节点中序遍历的下一个节点就需要在其的右子树当中找到最左端的节点；以上的红黑树当中对应的节点就是值为35的节点。
那么通过以上的示例就可以总结在红黑树当中要得到当前节点的下一个中序遍历的节点有以下的两种情况。
1.当前节点的右孩子节点不为空时，下一个节点就为当前节点的右子树最左侧的节点。
2.当前节点的右孩子为空，下一个节点就为当前节点所在红黑树当中的路径上的节点；该节点的特征是该节点为其父节点的左孩子节点。
注：若一直找不到满足要求的节点下一个节点就说明当前节点是遍历当中最后一个节点。
按照以上的要求在BRBTreeIterator实现的++运算符函数如下所示：
RBTreeIterator<T>& operator++()
{
//情况1当前节点的右孩子节点不为空
if (_node->_right)
{
Node* minleft = _node->_right;
//找到当前节点右子树当中的最左侧的节点
while (minleft->_left)
{
minleft = minleft->_left;
}
_node = minleft;
}
//情况2当前节点的右孩子节点为空
else
{
Node* cur = _node;
Node* Parent = cur->_parent;
//找到节点所在的路径上为父节点左孩子节点的节点或者为根节点的节点
while (Parent && cur==Parent->_right)
{
cur = Parent;
Parent = Parent->_parent;
}
_node = Parent;
}
//返回找到的节点对应的对象
return *this;
}接下来再来实现--运算符重载函数
在红黑树当中进行对应节点的--操作其实就是要找到当前节点的在中序遍历当中的前一个节点，例如以下的示例：
如上图所示，由于在红黑树当中正向遍历为左->根->右，那么反向的遍历就为右->根->左，那么这时值为50的节点的上一个节点为其的父亲节点即值为40的节点，那么该节点的上一个节点又是值为35的节点，接下来进行要找遍历的上一个节点就从40为根的子树当中跳出了，接下来上一个节点就是值为30的节点，接下来寻找的逻辑一直保持不变。
这时和在实现++当中类似实际上也会存在两种情况，分别是1.当前节点的左孩子节点不为空，那么这时前一个节点就为当前节点的左子树当中的最右节点，2.若当前节点的
那么通过以上的示例就可以总结在红黑树当中要得到当前节点的上一个中序遍历的节点有以下的两种情况。
1.当前节点的左孩子节点不为空时，下一个节点就为当前节点的右子树最右侧的节点。
2.当前节点的左孩子为空，下一个节点就为当前节点所在红黑树当中的路径上的节点；该节点的特征是该节点为其父节点的右孩子节点。
注：若一直找不到满足要求的节点下一个节点就说明当前节点是遍历当中最开始的节点。
在此和实现++有一点是不同的那就是如果当前迭代器为end，那么该如何找出遍历当中的最后一个节点呢？
实际上解决的方法很简单，那就是在迭代器当中直接将end设置为nullptr，那么这时在调用opreator--的时候判断一下当前节点的值是否为nllptr，是的话就直接遍历当前的红黑树，得到红黑树当中右子树中的最左节点。这样就能得到中序遍历中的最后一个节点。
但是以上的解决方法要求在迭代器当中保存有红黑树的根节点指针，那么这时我们就需要再对实现的RBTreeIterator成员变量再增加一个根节点的指针。
template<class T>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node,Node* root)
:_node(node),_root(root)
{
}
//运算符重载函数……
};按照以上的要求在BRBTreeIterator实现的--运算符函数如下所示：
RBTreeIterator<T>& operator--()
{
//当前为迭代器的end
if (_node == nullptr)
{
Node* rightmost = _root;
while (rightmost && rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
//当前节点左孩子节点不为空
else if (_node->_left)
{
Node* rightmost = _node->_left;
while (rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
//当前节点左孩子节点为空
else
{
Node* cur = _node;
Node* Parent = _node->_parent;
while (Parent && cur == Parent->_left)
{
cur = Parent;
Parent = Parent->_parent;
}
_node = Parent;
}
return *this;
}在源码当中实现的方式和以上我们的方法不怎么相同，在源码当中在原本的红黑树之上再创建了一个header的节点，该节点的左孩子节点为红黑树中左子树的最左节点；右孩子节点为右子树当中的最右节点，同时让header节点的父节点为红黑树的根节点，红黑树根节点的父节点为header节点。这时迭代器当中的end指针指向的就是header节点，这时要得到end--的节点指针就只需要拿到header节点的孩子节点即可。
部分实现的源码如下所示：
struct __rb_tree_base_iterator
{
typedef __rb_tree_node_base::base_ptr base_ptr;
base_ptr node;
void increment()
{
if (node->right != 0) {
node = node->right;
while (node->left != 0)
node = node->left;
}
else{
base_ptr y = node->parent;
while (node == y->right) {
node = y;
y = y->parent;
}
if(node->right != y)
node = y;
}
}
void decrement()
{
if (node->color == __rb_tree_red &&
node->parent->parent == node)
node = node->right;
else if (node->left != 0) {
base_ptr y = node->left;
while (y->right != 0)
y = y->right;
node = y;
}
else{
base_ptr y = node->parent;
while (node == y->left) {
node = y;
y = y->parent;
} n
ode = y;
}
}
};
template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
typedef Value value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
__rb_tree_iterator() {}
__rb_tree_iterator(link_type x) { node = x; }
__rb_tree_iterator(const iterator& it) { node = it.node; }
reference operator*() const { return link_type(node)->value_field; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() { increment(); return *this; }
self& operator--() { decrement(); return *this; }
inline bool operator==(const __rb_tree_base_iterator& x,
const __rb_tree_base_iterator& y) {
return x.node == y.node;
}
inline bool operator!=(const __rb_tree_base_iterator& x,
const __rb_tree_base_iterator& y) {
return x.node != y.node;
}在此我们未使用源码当中的方式来实现其实除了在红黑树当中在插入节点的时候维持header节点的指针实现较为繁琐外，要得到header节点合适的左右孩子节点也是需要在红黑树进行旋转之后遍历红黑树得到的，那么这样就会使得红黑树的效率受到影响。
以上实现完++和--的运算符重载函数之后接下来再将==和!=的重载函数实现
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}但是以上我们只是实现的普通迭代器，那么借鉴之前实现list迭代器的经验就可以再给BRTreeIterator类模板当中增加两个参数，分别为迭代器的引用和迭代器的指针。
完整代码如下所示：
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node, Node* root)
:_node(node)
, _root(root)
{
}
Ref operator*()
{
return _node->_date;
}
Ptr operator->()
{
return &_node->_date;
}
Self& operator++()
{
//情况1当前节点的右孩子节点不为空
if (_node->_right)
{
Node* minleft = _node->_right;
//找到当前节点右子树当中的最左侧的节点
while (minleft->_left)
{
minleft = minleft->_left;
}
_node = minleft;
}
//情况2当前节点的右孩子节点为空
else
{
Node* cur = _node;
Node* Parent = cur->_parent;
//找到节点所在的路径上为父节点左孩子节点的节点或者为根节点的节点
while (Parent && cur == Parent->_right)
{
cur = Parent;
Parent = Parent->_parent;
}
_node = Parent;
}
//返回找到的节点对应的对象
return *this;
}
Self& operator--()
{
//当前为迭代器的end
if (_node == nullptr)
{
Node* rightmost = _root;
while (rightmost && rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
//当前节点左孩子节点不为空
else if (_node->_left)
{
Node* rightmost = _node->_left;
while (rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
//当前节点左孩子节点为空
else
{
Node* cur = _node;
Node* Parent = _node->_parent;
while (Parent && cur == Parent->_left)
{
cur = Parent;
Parent = Parent->_parent;
}
_node = Parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};1.3 补全BRTree代码
以上我们将红黑树对应的迭代器实现之后，那么接下来就根据以上实现的红黑树代码将begin和end等函数的使用添加到BRTree类内。
实现代如下所示：
#pragma once
#pragma once
#include<iostream>
using namespace std;
int x;
enum colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _date;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
colour _col;
RBTreeNode(const T& date)
:_date(date)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{
}
};
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node, Node* root)
:_node(node)
, _root(root)
{
}
Ref operator*()
{
return _node->_date;
}
Ptr operator->()
{
return &_node->_date;
}
Self& operator++()
{
//情况1当前节点的右孩子节点不为空
if (_node->_right)
{
Node* minleft = _node->_right;
//找到当前节点右子树当中的最左侧的节点
while (minleft->_left)
{
minleft = minleft->_left;
}
_node = minleft;
}
//情况2当前节点的右孩子节点为空
else
{
Node* cur = _node;
Node* Parent = cur->_parent;
//找到节点所在的路径上为父节点左孩子节点的节点或者为根节点的节点
while (Parent && cur == Parent->_right)
{
cur = Parent;
Parent = Parent->_parent;
}
_node = Parent;
}
//返回找到的节点对应的对象
return *this;
}
Self& operator--()
{
//当前为迭代器的end
if (_node == nullptr)
{
Node* rightmost = _root;
while (rightmost && rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
//当前节点左孩子节点不为空
else if (_node->_left)
{
Node* rightmost = _node->_left;
while (rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
//当前节点左孩子节点为空
else
{
Node* cur = _node;
Node* Parent = _node->_parent;
while (Parent && cur == Parent->_left)
{
cur = Parent;
Parent = Parent->_parent;
}
_node = Parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template<class K, class T, class keyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> constIterator;
RBTree() = default;
~RBTree()
{
Destory(_root);
}
Iterator Begin()
{
//得到红黑树当中的最左节点
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur, _root);
}
constIterator End()const
{
return constIterator(nullptr, _root);
}
constIterator Begin()const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return constIterator(cur, _root);
}
Iterator End()
{
return Iterator(nullptr, _root);
}
pair<Iterator, bool> Insert(const T& date)
{
//当插入节点时的树为空时就将新插入的节点置为树的根节点，且颜色变为黑
if (_root == nullptr)
{
_root = new Node(date);
_root->_col = BLACK;
return { Iterator(_root,_root),true };
}
keyOfT kot;
//寻找合适的插入位置
Node* cur = _root;
Node* Parent = nullptr;
while (cur)
{
if (kot(cur->_date) < kot(date))
{
Parent = cur;
cur = cur->_right;
}
else if (kot(cur->_date) > kot(date))
{
Parent = cur;
cur = cur->_left;
}
else
{
return { Iterator(cur,_root),false };
}
}
//创建新节点
cur = new Node(date);
if (kot(Parent->_date) < kot(date))
{
Parent->_right = cur;
}
else
{
Parent->_left = cur;
}
cur->_parent = Parent;
cur->_col = RED;
Node* ret = cur;
while (Parent && Parent->_col == RED)
{
Node* grandfather = Parent->_parent;
//父节点为祖父节点的左节点时
// g
// p u
//c
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
{
//当c为p的左节点时
// g
// p u
//c
if (Parent->_left == cur)
{
RotateR(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的右节点时
// g
// p u
// c
else
{
RotateL(Parent);
RotateR(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
//父节点为祖父节点的右节点时
// g
// u p
// c
else
{
Node* uncle = grandfather->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
//叔叔不存在或者为黑
else
{
//当c为p的右节点时
// g
// u p
// c
if (Parent->_right == cur)
{
RotateL(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的左节点时
// g
// u p
// c
else
{
RotateR(Parent);
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
//无论以上是否进行调整都将根结点的颜色置为黑
_root->_col = BLACK;
return { Iterator(ret,_root),true };
}
Iterator Find(const K& val)
{
if (_root == nullptr)
{
return Iterator(nullptr,_root);
}
Node* cur = _root;
keyOfT kot;
while (cur)
{
if (kot(cur->_date) > val)
{
cur = cur->_left;
}
else if (kot(cur->_date) < val)
{
cur = cur->_right;
}
else
{
return Iterator(cur, _root);
}
}
return End();
}
private:
Node* _root = nullptr;
void RotateR(Node* Parent)
{
Node* subL = Parent->_left;
Node* subLR = subL->_right;
if (subLR != nullptr)
{
subLR->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_left = subLR;
Parent->_parent = subL;
subL->_right = Parent;
if (tmpNode != nullptr)
{
if (tmpNode->_left == Parent)
{
tmpNode->_left = subL;
}
else
{
tmpNode->_right = subL;
}
subL->_parent = tmpNode;
}
else
{
_root = subL;
subL->_parent = nullptr;
}
}
void RotateL(Node* Parent)
{
Node* subR = Parent->_right;
Node* subRL = subR->_left;
if (subRL != nullptr)
{
subRL->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_right = subRL;
Parent->_parent = subR;
subR->_left = Parent;
if (tmpNode != nullptr)
{
if (tmpNode->_left == Parent)
{
tmpNode->_left = subR;
}
else
{
tmpNode->_right = subR;
}
subR->_parent = tmpNode;
}
else
{
_root = subR;
subR->_parent = nullptr;
}
}
//销毁红黑树
void Destory(Node* root)
{
if (root == nullptr)return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
};
1.4 myset类实现
以上我们已经将红黑树实现了对应的迭代器并且将红黑树类的代码也进行修改，那么接下来就来实现set类的代码
实际上实现的过程很简单，在BRTree当中已经将底层实现完毕，那么接下来就只需要在set层内调用底层的代码实现封装即可。
实现的代码如下所示：
namespace zhz
{
template<class K>
class set
{
struct SetkeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//使用typename避免编译器将Iterator识别为静态成员变量
typedef typename RBTree<K, const K, SetkeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetkeyOfT>::constIterator const_iterator;
pair<iterator, bool> insert(const K& key)
{
return _rbtree.Insert(key);
}
iterator begin()
{
return _rbtree.Begin();
}
iterator end()
{
return _rbtree.End();
}
const_iterator begin()const
{
return _rbtree.Begin();
}
const_iterator end()const
{
return _rbtree.End();
}
iterator find(const K& key)
{
_rbtree.Insert(key);
}
private:
RBTree<K, const K, SetkeyOfT> _rbtree;
};
}注：以上的代码当中将RBTree类模板第二个模板参数使用const修饰是因为set当中对应的k值是不允许修改的，修改之后会使得无法保持二叉搜索树的特性，那么这时给第二个模板参数加上const就可以让用户无法修改二叉树当中节点内的值。
接下来使用以下的代码进行测试：
void Print(const set<int>& s)
{
set<int>::const_iterator it = s.end();
while (it != s.begin())
{
--it;
//*it += 2;
cout << *it << " ";
}
cout << endl;
}
void test_set()
{
set<int> s;
/*s.insert(1);
s.insert(4);
s.insert(2);
s.insert(3);*/
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto x : a)
s.insert(x);
Print(s);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}在test.cpp内调用test_set
#include<iostream>
#include"myset.h"
using namespace std;
int main()
{
zhz::test_set();
return 0;
}运行代码，输出结果如下所示：
通过以上的输出结果就可以看出我们实现的红黑树的迭代器以及set整体代码是没有问题的。
包括用户无法修改set内元素的值也是符合要求的。
1.5 mymap类实现
在实现了set对应的代码之后接下来继续来实现map类的代码，大体实现的流程和set类似，但是要多出来实现在map当中要实现[]运算符的重载函数。
通过之前map的学习我们知道实际上[]运算符的重载实现只需要封装对应的insert即可，最后再返回对应节点迭代器的引用。
实现代码如下所示：
#pragma once
#include"BRTree.h"
namespace zhz
{
template<class K, class V>
class map
{
struct MapkeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapkeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapkeyOfT>::constIterator const_iterator;
iterator begin()
{
return _rbtree.Begin();
}
iterator end()
{
return _rbtree.End();
}
const_iterator begin()const
{
return _rbtree.Begin();
}
const_iterator end()const
{
return _rbtree.End();
}
pair<iterator, bool>insert(const pair<K, V>& kv)
{
return _rbtree.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key,V() });
return ret.first->second;
}
iterator find(const K& key)
{
_rbtree.Insert(key);
}
private:
RBTree<K, pair<const K, V>, MapkeyOfT> _rbtree;
};
}通过以下的代码测试实现的map是否符合要求：
void test_map()
{
map<int, int> m;
m.insert({ 1,1 });
m.insert({ 2,3 });
m.insert({ 3,1 });
m.insert({ 5,1 });
map<int, int>::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
dict["left"] = "左边，插入";
dict["insert"] = "插入";
dict["string"];
for (auto& kv : dict)
{
cout << kv.first << " " << kv.second << endl;
}
cout << endl;
}在test.cpp内调用test_map
#include<iostream>
#include"mymap.h"
using namespace std;
int main()
{
zhz::test_map();
return 0;
}运行代码，输出结果如下所示：
通过以上的输出结果可以验证实现的map是符合要求的。
2. 完整代码
BRTree.h
#pragma once
#pragma once
#include<iostream>
using namespace std;
int x;
enum colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
T _date;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
colour _col;
RBTreeNode(const T& date)
:_date(date)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{
}
};
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node, Node* root)
:_node(node)
, _root(root)
{
}
Ref operator*()
{
return _node->_date;
}
Ptr operator->()
{
return &_node->_date;
}
Self& operator++()
{
//情况1当前节点的右孩子节点不为空
if (_node->_right)
{
Node* minleft = _node->_right;
//找到当前节点右子树当中的最左侧的节点
while (minleft->_left)
{
minleft = minleft->_left;
}
_node = minleft;
}
//情况2当前节点的右孩子节点为空
else
{
Node* cur = _node;
Node* Parent = cur->_parent;
//找到节点所在的路径上为父节点左孩子节点的节点或者为根节点的节点
while (Parent && cur == Parent->_right)
{
cur = Parent;
Parent = Parent->_parent;
}
_node = Parent;
}
//返回找到的节点对应的对象
return *this;
}
Self& operator--()
{
//当前为迭代器的end
if (_node == nullptr)
{
Node* rightmost = _root;
while (rightmost && rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
//当前节点左孩子节点不为空
else if (_node->_left)
{
Node* rightmost = _node->_left;
while (rightmost->_right)
{
rightmost = rightmost->_right;
}
_node = rightmost;
}
//当前节点左孩子节点为空
else
{
Node* cur = _node;
Node* Parent = _node->_parent;
while (Parent && cur == Parent->_left)
{
cur = Parent;
Parent = Parent->_parent;
}
_node = Parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template<class K, class T, class keyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> constIterator;
RBTree() = default;
~RBTree()
{
Destory(_root);
}
Iterator Begin()
{
//得到红黑树当中的最左节点
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return Iterator(cur, _root);
}
constIterator End()const
{
return constIterator(nullptr, _root);
}
constIterator Begin()const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return constIterator(cur, _root);
}
Iterator End()
{
return Iterator(nullptr, _root);
}
pair<Iterator, bool> Insert(const T& date)
{
//当插入节点时的树为空时就将新插入的节点置为树的根节点，且颜色变为黑
if (_root == nullptr)
{
_root = new Node(date);
_root->_col = BLACK;
return { Iterator(_root,_root),true };
}
keyOfT kot;
//寻找合适的插入位置
Node* cur = _root;
Node* Parent = nullptr;
while (cur)
{
if (kot(cur->_date) < kot(date))
{
Parent = cur;
cur = cur->_right;
}
else if (kot(cur->_date) > kot(date))
{
Parent = cur;
cur = cur->_left;
}
else
{
return { Iterator(cur,_root),false };
}
}
//创建新节点
cur = new Node(date);
if (kot(Parent->_date) < kot(date))
{
Parent->_right = cur;
}
else
{
Parent->_left = cur;
}
cur->_parent = Parent;
cur->_col = RED;
Node* ret = cur;
while (Parent && Parent->_col == RED)
{
Node* grandfather = Parent->_parent;
//父节点为祖父节点的左节点时
// g
// p u
//c
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
{
//当c为p的左节点时
// g
// p u
//c
if (Parent->_left == cur)
{
RotateR(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的右节点时
// g
// p u
// c
else
{
RotateL(Parent);
RotateR(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
//父节点为祖父节点的右节点时
// g
// u p
// c
else
{
Node* uncle = grandfather->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
Parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
Parent = cur->_parent;
}
//叔叔不存在或者为黑
else
{
//当c为p的右节点时
// g
// u p
// c
if (Parent->_right == cur)
{
RotateL(grandfather);
grandfather->_col = RED;
Parent->_col = BLACK;
}
//当c为p的左节点时
// g
// u p
// c
else
{
RotateR(Parent);
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}
//无论以上是否进行调整都将根结点的颜色置为黑
_root->_col = BLACK;
return { Iterator(ret,_root),true };
}
Iterator Find(const K& val)
{
if (_root == nullptr)
{
return Iterator(nullptr,_root);
}
Node* cur = _root;
keyOfT kot;
while (cur)
{
if (kot(cur->_date) > val)
{
cur = cur->_left;
}
else if (kot(cur->_date) < val)
{
cur = cur->_right;
}
else
{
return Iterator(cur, _root);
}
}
return End();
}
private:
Node* _root = nullptr;
void RotateR(Node* Parent)
{
Node* subL = Parent->_left;
Node* subLR = subL->_right;
if (subLR != nullptr)
{
subLR->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_left = subLR;
Parent->_parent = subL;
subL->_right = Parent;
if (tmpNode != nullptr)
{
if (tmpNode->_left == Parent)
{
tmpNode->_left = subL;
}
else
{
tmpNode->_right = subL;
}
subL->_parent = tmpNode;
}
else
{
_root = subL;
subL->_parent = nullptr;
}
}
void RotateL(Node* Parent)
{
Node* subR = Parent->_right;
Node* subRL = subR->_left;
if (subRL != nullptr)
{
subRL->_parent = Parent;
}
Node* tmpNode = Parent->_parent;
Parent->_right = subRL;
Parent->_parent = subR;
subR->_left = Parent;
if (tmpNode != nullptr)
{
if (tmpNode->_left == Parent)
{
tmpNode->_left = subR;
}
else
{
tmpNode->_right = subR;
}
subR->_parent = tmpNode;
}
else
{
_root = subR;
subR->_parent = nullptr;
}
}
//销毁红黑树
void Destory(Node* root)
{
if (root == nullptr)return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
};
myset.h
#pragma once
#include"BRTree.h"
namespace zhz
{
template<class K>
class set
{
struct SetkeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//使用typename避免编译器将Iterator识别为静态成员变量
typedef typename RBTree<K, const K, SetkeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetkeyOfT>::constIterator const_iterator;
pair<iterator, bool> insert(const K& key)
{
return _rbtree.Insert(key);
}
iterator begin()
{
return _rbtree.Begin();
}
iterator end()
{
return _rbtree.End();
}
const_iterator begin()const
{
return _rbtree.Begin();
}
const_iterator end()const
{
return _rbtree.End();
}
iterator find(const K& key)
{
return _rbtree.Find(key);
}
private:
RBTree<K, const K, SetkeyOfT> _rbtree;
};
void Print(const set<int>& s)
{
set<int>::const_iterator it = s.end();
while (it != s.begin())
{
--it;
// ֧
//*it += 2;
cout << *it << " ";
}
cout << endl;
}
void test_set()
{
set<int> s;
/*s.insert(1);
s.insert(4);
s.insert(2);
s.insert(3);*/
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto x : a)
s.insert(x);
Print(s);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}mymap.h
#pragma once
#pragma once
#include"BRTree.h"
namespace zhz
{
template<class K, class V>
class map
{
struct MapkeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapkeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapkeyOfT>::constIterator const_iterator;
iterator begin()
{
return _rbtree.Begin();
}
iterator end()
{
return _rbtree.End();
}
const_iterator begin()const
{
return _rbtree.Begin();
}
const_iterator end()const
{
return _rbtree.End();
}
pair<iterator, bool>insert(const pair<K, V>& kv)
{
return _rbtree.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key,V() });
return ret.first->second;
}
iterator find(const K& key)
{
return _rbtree.Find(key);
}
private:
RBTree<K, pair<const K, V>, MapkeyOfT> _rbtree;
};
void test_map()
{
map<int, int> m;
m.insert({ 1,1 });
m.insert({ 2,3 });
m.insert({ 3,1 });
m.insert({ 5,1 });
map<int, int>::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
dict["left"] = "左边，插入";
dict["insert"] = "插入";
dict["string"];
for (auto& kv : dict)
{
cout << kv.first << " " << kv.second << endl;
}
cout << endl;
string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
// 统计水果出现的次
map<string, int> countTree;
for (auto str : strs)
{
auto ret = countTree.find(str);
if (ret == countTree.end())
{
countTree.insert({ str, 1 });
}
else
{
countTree[str]++;
}
}
for (auto& kv : countTree)
{
cout << kv.first << " " << kv.second << endl;
}
cout << endl;
}
}以上就是本篇的全部内容了，希望本文对您有所帮助。