文章目录
- 红黑树的封装
- map和set的封装
- 红黑树迭代器的实现
- operator ++ 和 -- 的实现
- ++的实现过程
- 迭代器的其他模块
- 整体实现
本篇写于红黑树模拟实现后,对map和set进行封装,模拟实现map和set内部的原理
首先,map和set的底层逻辑是红黑树,那么就意味着不再需要像vector/list这样重新进行写入,而是直接在红黑树的基础上进行适当的封装即可
但是,前面实现的红黑树并不能完美的适配所需要的功能,因此要在一定程度上对红黑树进行改造后,才能很好的使用,那么下面首先要对红黑树进行一定程度的改造
本篇将分析STL库中对红黑树的封装原理,搭建出基础的框架,并进行分析
红黑树的封装
拿出一份关于STL中的源码,分析源码中是如何对这这棵树进行封装的
在红黑树的定义中就不太一样,在前面实现的过程中,是直接将pair键值对当做模板中的参数的,导致只有两种,一种是Key/Key模型,一种是Key/Value模型,而在源码的实现中,则是直接将类型放到模板中来实现,用泛型的思想编程
在map和set中,传参直接将需要传递的参数传到Value处:
因此在封装的时候,就可以这样进行封装,先对我们自己完成的红黑树进行一些改善
首先,对节点进行改善
template<class T>
struct RBTreeNode
{
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _col;
};
map和set的封装
下面可以对map和set进行初步封装了
namespace mymap
{
template<class K, class V>
class set
{
private:
RBTree<K, pair<K, V>> _t;
};
}
namespace myset
{
template<class K>
class set
{
private:
RBTree<K, K> _t;
};
}
下一个遇到的问题是,在插入数据的时候如何比较大小呢?例如下面的场景
上面是在模拟实现红黑树的过程中实现的逻辑,现在问题是,如何对于键值对进行比较?
在库函数中寻找对策:
比较的规则是比较键值对的第一个元素,因此现在需要做的就是想办法取出来键值对的第一个元素进行比较,因此就可以采取这样的思想,在map和set中都搞一个能把数据取出来的仿函数,在进行比较的时候返回的是Key即可,因此要修改红黑树的模板参数,接收一个仿函数的值,并用其来参与插入数据时的比较
namespace mymap
{
template<class K, class V>
class map
{
private:
struct MapKeyOfT
{
const K& operator()(const V& data)
{
// 对于map来讲,Key是传入的data键值对中的第一个元素
return data.first;
}
};
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}
namespace myset
{
template<class K>
class set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& data)
{
// 对于set来讲,K就是data本身
return data.first;
}
};
private:
RBTree<K, K, SetKeyOfT> _t;
};
}
此时基本逻辑就已经搭建起来了,在map/set中进行插入元素,实际上就是插入到树中,在外部再对这个插入的过程进行一次封装
pair<iterator,bool> insert(const V& val)
{
return _t.insert(val);
}
红黑树迭代器的实现
于是,要实现出红黑树的迭代器,红黑树的迭代器和链表的迭代器类似,都要借助一个类来构建
template<class T,class Ptr,class Ref>
struct _TreeIterator
{
typedef RBTreeNode<T> Node;
typedef _TreeIterator<T, T*, T&> Self;
// 构造函数:迭代器的本质就是封装了一层指针
_TreeIterator(Node* node)
:_node(node)
{}
// 迭代器中功能的实现
// 解引用取数据
Ref operator*()
{
return _node->_data;
}
// 取数据的地址
Ptr operator->()
{
return &(_node->_data);
}
// 实现++
// 迭代器的本质是节点的指针
Node* _node;
};
operator ++ 和 – 的实现
++的实现过程
以上图为例,此时指向的是17,从正常来说遍历次序是按照中序遍历,因此比17大的下一个数是22,总结出结论就是,++要寻找的是右孩子的最左子树,如果没有右子树如何处理?
如果没有右子树,就说明此时已经到了遍历结束了左子树,如上图所示,此时要找的是,孩子是父亲左的那个节点的祖先
根据上述逻辑,完善迭代器的代码
// 实现++
Self& operator++()
{
// 如果右子树存在,就到右子树中找最左节点
if (_node->_right)
{
// 下一个就是右子树的最左节点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
// 如果右子树不存在,就到孩子是父亲左的那个祖先
else
{
// 左子树 根 右子树
Node* cur = _node;
Node* parent = cur->_parent;
// 只要孩子是父亲的右,就继续向上循环找,直到找到孩子是父亲左的那个节点
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
// 实现--
Self& operator--()
{
// 如果左子树存在,就到左子树中找最右节点
if (_node->_left)
{
// 下一个就是右子树的最左节点
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
// 如果左子树不存在,就到孩子是父亲右的那个祖先
else
{
// 左子树 根 右子树
Node* cur = _node;
Node* parent = cur->_parent;
// 只要孩子是父亲的左,就继续向上循环找,直到找到孩子是父亲右的那个节点
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
迭代器的其他模块
// 判断相等和不相等,实际上就是看迭代器内部封装的节点是否是同一个节点即可
bool operator==(const Self& it)
{
return _node == it._node;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
整体实现
改造过后的红黑树
#pragma once
#include <iostream>
using namespace std;
enum Color
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _col;
};
template<class T, class Ptr, class Ref>
struct _TreeIterator
{
typedef RBTreeNode<T> Node;
typedef _TreeIterator<T, T*, T&> Self;
// 构造函数:迭代器的本质就是封装了一层指针
_TreeIterator(Node* node)
:_node(node)
{}
// 迭代器中功能的实现
// 解引用取数据
Ref operator*()
{
return _node->_data;
}
// 取数据的地址
Ptr operator->()
{
return &(_node->_data);
}
// 实现++
Self& operator++()
{
// 如果右子树存在,就到右子树中找最左节点
if (_node->_right)
{
// 下一个就是右子树的最左节点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
// 如果右子树不存在,就到孩子是父亲左的那个祖先
else
{
// 左子树 根 右子树
Node* cur = _node;
Node* parent = cur->_parent;
// 只要孩子是父亲的右,就继续向上循环找,直到找到孩子是父亲左的那个节点
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
// 实现--
Self& operator--()
{
// 如果左子树存在,就到左子树中找最右节点
if (_node->_left)
{
// 下一个就是右子树的最左节点
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
// 如果左子树不存在,就到孩子是父亲右的那个祖先
else
{
// 左子树 根 右子树
Node* cur = _node;
Node* parent = cur->_parent;
// 只要孩子是父亲的左,就继续向上循环找,直到找到孩子是父亲右的那个节点
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
// 判断相等和不相等,实际上就是看迭代器内部封装的节点是否是同一个节点即可
bool operator==(const Self& it)
{
return _node == it._node;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
// 迭代器的本质是节点的指针
Node* _node;
};
template<class K, class T, class KeyOfT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef _TreeIterator<T, T*, T&> iterator;
// 红黑树的构造函数
RBTree()
:_root(nullptr)
{}
// 红黑树的析构函数
~RBTree()
{
DelNode(_root);
}
// 红黑树迭代器部分
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
// 元素的插入
pair<iterator, bool> insert(const T& data)
{
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
// 根据搜索二叉树的基本逻辑完成
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
else
{
// 插入数据
while (cur)
{
if (kot(cur->_data) > kot(data))
{
// 插入元素小于当前节点元素,插入到左边
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_data) < kot(data))
{
// 插入元素大于当前节点元素,插入到右边
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur), false);
}
}
// 此时parent指向最后一个节点,cur为空
cur = new Node(data);
if (kot(parent->_data) > kot(cur->_data))
{
// 如果插入节点小于它的父亲,就插入到左边
parent->_left = cur;
cur->_parent = parent;
}
else
{
// 如果插入节点大于它的父亲,就插入到右边
parent->_right = cur;
cur->_parent = parent;
}
}
// 至此,普通二叉搜索树的插入已经完成,该进行红黑树的高度调整了
// 终止条件是parent为空,或者parent已经是黑色了,就意味着不需要调整了
// parent是红色,意味着grandparent一定存在
while (parent && parent->_col == RED)
{
// 更变的核心是舅舅,因此要先找到舅舅
// 整体来说还有两种情况,parent可能是grandparent的左或者右,舅舅就是另外一边
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
// 1. 舅舅存在,并且是红色
if (uncle && uncle->_col == RED)
{
// g
// p u
// c
// 变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
// 向上处理
cur = grandparent;
parent = cur->_parent;
}
// 2. 舅舅不存在
else
{
// 如果cur是左孩子
if (cur == parent->_left)
{
// g
// p
// c
// 对grandparent进行右旋
RotateR(grandparent);
// 变色
cur->_col = grandparent->_col = RED;
parent->_col = BLACK;
}
// 如果cur是右孩子
else
{
// g g
// p --> c --> c
// c p p g
// 对parent左旋,对grandparent右旋
RotateL(parent);
RotateR(grandparent);
// 变色
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
// 更新之后parent和grandparent顺序乱了,而且也不需要继续调整了,直接break
break;
}
}
// parent是grandparent的右孩子,相同的逻辑再进行一次
else
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
// 继续往上处理
cur = grandparent;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
// g
// p
// c
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
// g
// p
// c
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
}
// 不管上面怎么变都无所谓,只需要保证根节点是黑的就可以了
_root->_col = BLACK;
return make_pair(iterator(cur), true);
}
private:
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
void DelNode(Node* root)
{
if (root == nullptr)
{
return;
}
DelNode(root->_left);
DelNode(root->_right);
delete(root);
}
Node* _root = nullptr;
};
依据红黑树封装出的set
#pragma once
#include "RBTree.h"
namespace myset
{
template<class K>
class set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& data)
{
// 对于set来讲,K就是data本身
return data;
}
};
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
pair<iterator, bool> insert(const K& val)
{
return _t.insert(val);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}
依据红黑树构造出的map
#pragma once
#include "RBTree.h"
namespace mymap
{
template<class K, class V>
class map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& data)
{
// 对于map来讲,key是键值对的第一个元素
return data.first;
}
};
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
pair<iterator, bool> insert(const pair<K, V>& val)
{
return _t.insert(val);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}