网站开发费怎么入账,做网站运营需要具备哪些能力,如何做亚马逊跨境电商,学做电商的网站有哪些关于红黑树的模拟实现#xff0c;大家不清楚的先去看看博主的博客再来看这篇文章#xff0c;因为set和map的封装底层都是利用用的红黑树。所以这里不会过多介绍红黑树的相关内容#xff0c;而更多的是去为了契合STL中的红黑树去进行改造#xff0c;让封装的set和map能够去复… 关于红黑树的模拟实现大家不清楚的先去看看博主的博客再来看这篇文章因为set和map的封装底层都是利用用的红黑树。所以这里不会过多介绍红黑树的相关内容而更多的是去为了契合STL中的红黑树去进行改造让封装的set和map能够去复用我们的这份代码
DS进阶AVL树和红黑树-CSDN博客 在模拟实现之前我们肯定要尝试去看看源码是如何实现的我们会发现其实map和set的底层都是用的红黑树去封装的 但是你可能会有这样的疑惑map是kv模型set是k模型那难道stl底层封装了两颗红黑树么其实并不是的创建stl的大佬们为了增加代码的复用性想方设法地想让map和set同时复用一颗红黑树。而解决方法就是通过控制模版参数来区分map和set。 既然底层是套的红黑树的壳子我们就要来研究库里面的红黑树究竟通过了什么方法来让map和set都能够复用这份代码。
一、STL中的红黑树
1.1 利用模版参数控制和区分map和set
我们先来看看stl中的红黑树的模版参数然后进行分析 接下来我们来看看第三个模版参数的作用究竟是什么 总结
第1个模版参数是为了帮助我们拿到Key的类型因为find、erase的接口都是Key类型比较方便
第2个模版参数决定了红黑树节点中存的是key还是pair以此来区分map和set
第3个模版参数是通过仿函数决定了是拿什么去进行比较对set来说就是拿key对pair来说就是拿他的first。
第4个模版参数是具体的比较逻辑比如说我们传的是指针但是我们并不想通过指针比而是通过指针解引用的类型比就可以通过传这个仿函数去控制其比较的行为。
第5个是stl实现的一个堆内存管理器是为了提高从堆区申请内存的效率基本上所有的stl容器都会涉及到这个所以目前暂时不需要太在意
1.2 stl中的红黑树结构 在该图中设置了一个哨兵节点哨兵节点的左指向最小节点5最大节点的右指向哨兵节点header 为什么要这样设计呢 STL明确规定begin()与end()代表的是一段前闭后开的区间而对红黑树进行中序遍历后 可以得到一个有序的序列因此begin()可以放在红黑树中最小节点(即最左侧节点)的位 置end()放在最大节点(最右侧节点)的下一个位置关键是最大节点的下一个位置在哪块 能否给成nullptr呢答案是行不通的因为对end()位置的迭代器进行--操作必须要能找最 后一个元素此处就不行因此最好的方式是将end()放在头结点的位置 但是这样虽然方便我们找到第一个节点和最后一个节点但是每一次都要最最左端和最右端的节点进行和头节点之间的联系其实比较麻烦所以下面我们直接改造成不带哨兵节点的红黑树。去模拟实现迭代器。
1.3 改造并模拟实现红黑树的迭代器 但是最最关键的逻辑就是实现和--这样迭代器才能跑的起来下面我们来进行分析
迭代器的封装
templateclass T,class Ref,class Ptr
struct _RBTreeIterator
{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT, Ref, Ptr Self; //返回一个自身的迭代器Node* _node;_RBTreeIterator(Node* node) //利用节点去构造迭代器:_node(node){}// 1、typedef __RBTreeIteratorT, T, T* itertaor; 拷贝构造// 2、 typedef __RBTreeIteratorT, const T, const T* const_itertaor;// 支持普通迭代器构造const迭代器的构造函数_RBTreeIterator(const _RBTreeIteratorT, T, T* it) //隐私类型转化:_node(it._node){}Ref operator*(){return _node-_data; //解引用拿到对应的东西 map拿到pair set拿到key}Ptr operator-() //返回对应的指针类型{return operator*();}bool operator!(const Self s){return _node ! s._node;//判断两个迭代器是否相同}bool operator(const Self s){return _node s._node;//判断两个迭代器是否相同}Self operator() //实现迭代器的{if (_node-_right){//如有右不为空那么就去找到 右子树的最左路节点Node* subright _node-_right;while (subright-_left) subright subright-_left; //找到最左路节点_node subright;}else{//右为空沿着到根的路径找孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent parent-_right cur){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--() //实现迭代器的-- 右 根 左{if (_node-_left){//如有左不为空那么就去找到 左子树的最右路节点Node* subright _node-_left;while (subright-_right) subright subright-_right; //找到最左路节点_node subright;}else{//左为空沿着到根的路径找孩子是父亲右的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent parent-_left cur){cur parent;parent parent-_parent;}_node parent;}return *this;}
};
1.4 红黑树实现的全部代码
enum Colour
{RED,BLACK,
};templateclass T //T表示传的是K还是pair
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;RBTreeNode(const T data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};templateclass T,class Ref,class Ptr
struct _RBTreeIterator
{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT, Ref, Ptr Self; //返回一个自身的迭代器Node* _node;_RBTreeIterator(Node* node) //利用节点去构造迭代器:_node(node){}// 1、typedef __RBTreeIteratorT, T, T* itertaor; 拷贝构造// 2、 typedef __RBTreeIteratorT, const T, const T* const_itertaor;// 支持普通迭代器构造const迭代器的构造函数_RBTreeIterator(const _RBTreeIteratorT, T, T* it) //隐私类型转化:_node(it._node){}Ref operator*(){return _node-_data; //解引用拿到对应的东西 map拿到pair set拿到key}Ptr operator-() //返回对应的指针类型{return operator*();}bool operator!(const Self s){return _node ! s._node;//判断两个迭代器是否相同}bool operator(const Self s){return _node s._node;//判断两个迭代器是否相同}Self operator() //实现迭代器的{if (_node-_right){//如有右不为空那么就去找到 右子树的最左路节点Node* subright _node-_right;while (subright-_left) subright subright-_left; //找到最左路节点_node subright;}else{//右为空沿着到根的路径找孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent parent-_right cur){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--() //实现迭代器的-- 右 根 左{if (_node-_left){//如有左不为空那么就去找到 左子树的最右路节点Node* subright _node-_left;while (subright-_right) subright subright-_right; //找到最左路节点_node subright;}else{//左为空沿着到根的路径找孩子是父亲右的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent parent-_left cur){cur parent;parent parent-_parent;}_node parent;}return *this;}
};//K是为了单独拿到key的类型 因为find erase 的接口都是key 而第二个模版参数T决定是这边传的是pair还是key
templateclass K, class T,class KeyOfT //KeyofT 取出来比较的是k 还是pair中的k
class RBTree
{typedef RBTreeNodeT Node;
public:typedef _RBTreeIteratorT, T, T* iterator;typedef _RBTreeIteratorT, const T, const T* const_iterator;iterator begin(){Node* cur _root;while (cur cur-_left) cur cur-_left;//找到最左路的节点return iterator(cur);} iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* cur _root;while (cur cur-_left) cur cur-_left;//找到最左路的节点return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}~RBTree(){_Destroy(_root);_root nullptr;}Node* Find(const K key){Node* cur _root;KeyOfT kot;//控制 是在pair中拿key还是直接拿keywhile (cur){if (kot(cur-_data) key) cur cur-_right; //我比你小你往右找else if (kot(cur-_data) key) cur cur-_left; //我比你大你往左找else return cur;}return nullptr;//说明找不到}//先用搜索树的逻辑插入节点然后再去更新平衡因子。pairiterator,bool Insert(const T data){//如果为空树新节点就是根if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root),true);}KeyOfT kot;//控制 是在pair中拿key还是直接拿key//如果不为空树Node* parent nullptr;Node* cur _root;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 new Node(data);Node* newnode cur;//记住新加入的节点if (kot(parent-_data) kot(data)) parent-_left cur; //比父亲小连左边else parent-_right cur; //比父亲大连右边//别忘了父亲指针cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;//情况1如果u为存在且为红if (grandfather-_left parent)//如果p是g的左边u就在右边{Node* uncle grandfather-_right;//情况1如果u为存在且为红 p u变黑g变红 向上调整if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}else //情况2或者情况3 u为黑或者不存在 旋转变色{if (cur parent-_left) //情况2 右单旋p变黑 g变红{// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else //情况3 右左双旋 c变黑 g变红{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//情况2和情况3都要跳出循环}}else//if (grandfather-_right parent)//如果p是g的右边u就在左边 几乎一样就是旋转的逻辑不同{Node* uncle grandfather-_left;//情况1如果u为存在且为红 p u变黑g变红 向上调整if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}else//情况2或者情况3 u为黑或者不存在 旋转变色{if (cur parent-_right) //情况2 左单旋p变黑 g变红{// g// p u// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else //情况3 左右双旋 c变黑 g变红{// g// p u// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//情况2和情况3都要跳出循环}}}_root-_col BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑总没错return make_pair(iterator(newnode), true);}void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;//找到一条路径作为基准值 然后看看其他路径是否相等Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}// 连续红色节点return _Check(_root, 0, benchmark);}int Height(){return _Height(_root);}private:void _Destroy(Node* root){if (root nullptr) return;//后序遍历销毁_Destroy(root-_left);_Destroy(root-_right);delete root;}int _Height(Node* root){if (root nullptr)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool _Check(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}//旋转代码和AVL树是一样的只不过不需要搞平衡因子void RotateL(Node* parent){//旋转前先记录对应的节点Node* subR parent-_right;Node* subRL subR-_left;Node* ppnode parent-_parent;//子树的前驱节点//先让b变成30的边parent-_right subRL;if (subRL) subRL-_parent parent;//让30变成60的左边subR-_left parent;parent-_parent subR;//此时与前驱节点连接起来 如果前驱节点为空直接改变根if (ppnode nullptr){_root subR;_root-_parent nullptr;}//如果前驱节点不为空此时要根据之前paernt的情况决定插在哪边else{if (ppnode-_left parent) ppnode-_left subR;else ppnode-_right subR;//向上连接subR-_parent ppnode;}}void RotateR(Node* parent){//旋转前先记录对应的节点Node* subL parent-_left;Node* subLR subL-_right;Node* ppnode parent-_parent;//子树的前驱节点//先让b变成60的左边parent-_left subLR;if (subLR) subLR-_parent parent;//让60变成30的右边subL-_right parent;parent-_parent subL;//此时与前驱节点连接起来 如果前驱节点为空直接改变根if (ppnode nullptr){_root subL;_root-_parent nullptr;}//如果前驱节点不为空此时要根据之前paernt的情况决定插在哪边else{if (ppnode-_left parent) ppnode-_left subL;else ppnode-_right subL;//向上连接subL-_parent ppnode;}}Node* _root nullptr;
};二、set的模拟实现
前面我们已经将架子搭好了这个时候就可以直接开始用了
namespace cyx
{templateclass Kclass set{struct SetKeyofT{ const K operator()(const K key) //为了跟map保持一致{return key;}};public:typedef typename RBTree K,K,SetKeyofT::iterator iterator;//在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题iterator begin(){return _t.begin();}iterator end(){return _t.end();}pairiterator, bool insert(const Kkey){return _t.Insert(key);}private:RBTreeK, K, SetKeyofT _t;};
注意
1、在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题 2、对于insert返回值的改造本质上是为了map去服务的set只是配合而已。
三、map的模拟实现
3.1 insert的改装
在stl中 insert的返回值是pairiterator,bool 一开始我不太能理解为什么要这么设计。后来我明白了其实本质上为了后面重载[ ]的实现做铺垫。我们可以通过返回值去拿到iterator并对对应节点的value进行直接修改
//先用搜索树的逻辑插入节点然后再去更新平衡因子。
pairiterator,bool Insert(const T data)
{//如果为空树新节点就是根if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root),true);}KeyOfT kot;//控制 是在pair中拿key还是直接拿key//如果不为空树Node* parent nullptr;Node* cur _root;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 new Node(data);Node* newnode cur;//记住新加入的节点if (kot(parent-_data) kot(data)) parent-_left cur; //比父亲小连左边else parent-_right cur; //比父亲大连右边//别忘了父亲指针cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;//情况1如果u为存在且为红if (grandfather-_left parent)//如果p是g的左边u就在右边{Node* uncle grandfather-_right;//情况1如果u为存在且为红 p u变黑g变红 向上调整if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}else //情况2或者情况3 u为黑或者不存在 旋转变色{if (cur parent-_left) //情况2 右单旋p变黑 g变红{// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else //情况3 右左双旋 c变黑 g变红{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//情况2和情况3都要跳出循环}}else//if (grandfather-_right parent)//如果p是g的右边u就在左边 几乎一样就是旋转的逻辑不同{Node* uncle grandfather-_left;//情况1如果u为存在且为红 p u变黑g变红 向上调整if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}else//情况2或者情况3 u为黑或者不存在 旋转变色{if (cur parent-_right) //情况2 左单旋p变黑 g变红{// g// p u// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else //情况3 左右双旋 c变黑 g变红{// g// p u// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//情况2和情况3都要跳出循环}}}_root-_col BLACK; //预防情况1出现 parent就是根的情况 此时无论如何_root变成黑总没错return make_pair(iterator(newnode), true);
}
3.2 重载[ ]的实现
V operator[](const K key)
{pairiterator, bool ret _t.Insert(make_pair(key, V())); //默认构造return ret.first-second;
}
通过insert拿到对应位置的迭代器然后指向其second 这样就可以直接进行修改了。
3.3 模拟实现的代码
namespace cyx
{templateclass K, class Vclass map{struct MapKeyofT{const K operator()(const pairconst K, V kv) //为了跟map保持一致{return kv.first;}};public://模版类型的内嵌类型 加typenametypedef typename RBTreeK, pairconst K, V, MapKeyofT::iterator iterator;//在没有实例化的时候 编译器并不知道这是一个成员还是一个类型 typename可以帮助我们解决这个问题iterator begin(){return _t.begin();}iterator end(){return _t.end();}V operator[](const K key){pairiterator, bool ret _t.Insert(make_pair(key, V())); //默认构造return ret.first-second;}pairiterator, bool insert(const pairconst K, V kv){return _t.Insert(kv);}private:RBTreeK, pairconst K,V, MapKeyofT _t;};
