搞个竞拍网站怎么做,做的网站,wordpress後台小程序,做网站网络公司无收入目录 前言及准备#xff1a;一、红黑树接口1.1 begin1.2 end1.3 查找1.4 插入1.5 左单旋和右单旋 二、树形迭代器#xff08;正向#xff09;2.1 前置 三、模拟实现set四、模拟实现map 前言及准备#xff1a;
set、map的底层结构是红黑树#xff0c;它们的函数通过调用红… 目录 前言及准备一、红黑树接口1.1 begin1.2 end1.3 查找1.4 插入1.5 左单旋和右单旋 二、树形迭代器正向2.1 前置 三、模拟实现set四、模拟实现map 前言及准备
set、map的底层结构是红黑树它们的函数通过调用红黑树的接口来实现红黑树一些接口需要通过树形迭代器来实现。set是k模型map是kv模型红黑树要不要写两份呢答案是不需要只用一份即可通过仿函数来控制。
定义树的节点
templateclass T
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){}
};红黑树有3个指针域数据域用T来表示如果是set那么传过来的是k模型如果是map是kv模型。新增的节点的颜色默认是红色根节点除外。
一、红黑树接口
1.1 begin
返回的是红黑树的第一个节点注意这里的第一个的顺序是按中序遍历来的所以第一个节点的位置是树的最左节点。
//返回的迭代器指向的数据可修改
iterator begin()
{Node* subLeft _root;while (subLeft-_left){subLeft subLeft-_left;}return iterator(subLeft);
}
//返回的迭代器指向的数据不可修改
const_iterator begin() const
{Node* subLeft _root;while (subLeft-_left){subLeft subLeft-_left;}return const_iterator(subLeft);
}1.2 end
返回的是最后一个节点最右侧节点的下一个位置。由于这里实现的红黑树没有头节点所以只能给nullptr来勉强实现这个迭代器。但是这样其实是不行的因为对end()位置的迭代器进行 - - 操作必须要能找最后一个元素给nullptr就找不到了。如果有头节点那么end()的位置应该是在头节点的位置。
iterator end()
{return iterator(nullptr);
}
const_iterator end() const
{return const_iterator(nullptr);
}1.3 查找
查找的过程与之前写的二叉搜索树没有多大区别要注意的是返回类型找到了返回的是该节点的迭代器找不到就返回end()。
iterator Find(const K key)
{KeyOfT kot;Node* cur _root;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return iterator(cur);}}return end();
}咋知道是set还是map的数据进行比较看传过来的类模板参数中的仿函数是set的还是map的。当然这里只需写好就行不用关心传过来的是什么set和map的仿函数内部已经确定好了。
说明一下 templateclass K, class T, class KeyOfT 这是该红黑树的类模板K是Find()函数中要对比的数据类型T是节点的数据域可能是k模型也有可能是kv模型。怎么确定呢通过第三个类模板参数——仿函数来确定。仿函数传的是set的就是k模型仿函数传的是map的就是kv模型。仿函数内部具体实现下面再说。
1.4 插入
为了接近STL库中的insert函数返回类型是pair即插入成功返回该节点的迭代器和true插入失败说明该节点已经存在返回该节点的迭代器和false。
pairiterator, bool Insert(const T data)
{//为空if (_root nullptr){_root new Node(data);_root-_col BLACK;//根节点都是黑色的特殊处理return make_pair(iterator(_root), true);}//非空KeyOfT kot;Node* cur _root;Node* parent nullptr;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);//红色的if (kot(parent-_data) kot(data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;Node* newnode cur;//调整颜色while (parent parent-_col RED){Node* grandfather parent-_parent;//爷爷节点//父节点在爷爷节点的左边那么叔叔节点在右边if (parent grandfather-_left){Node* uncle grandfather-_right;//情况一叔叔存在且为红if (uncle uncle-_col RED){grandfather-_col RED;uncle-_col parent-_col BLACK;cur grandfather;//爷爷不是根向上更新parent cur-_parent;}//情况二叔叔不存在/存在且为黑else{//单旋if (cur parent-_left){RotateR(grandfather);//右单旋parent-_col BLACK;//变色grandfather-_col RED;}//左右双旋 // cur parent-_rightelse{RotateL(parent);//先左单旋RotateR(grandfather);//再右单旋grandfather-_col RED;//变色cur-_col BLACK;}}}else//父节点在右边叔叔在左边{Node* uncle grandfather-_left;//情况一叔叔存在且为红if (uncle uncle-_col RED){grandfather-_col RED;uncle-_col parent-_col BLACK;cur grandfather;//爷爷不是根向上更新parent cur-_parent;}//情况二叔叔不存在/存在且为黑else{//单旋if (cur parent-_right){RotateL(grandfather);//左单旋parent-_col BLACK;//变色grandfather-_col RED;}//右左双旋 // cur parent-_leftelse{RotateR(parent);//先右单旋RotateL(grandfather);//再左单旋grandfather-_col RED;//变色cur-_col BLACK;}break;//经过情况二后跳出}}}_root-_col BLACK;//统一处理根必须是黑的return make_pair(iterator(newnode), true);
}1.5 左单旋和右单旋
这两个就是之前的这里不作重复叙述了
//左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;//不为空if (subRL){subRL-_parent parent;}subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;//处理parent如果为根if (parent _root){_root subR;subR-_parent nullptr;}//不为根处理与ppnode的连接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;parent-_left subLR;//不为空if (subLR){subLR-_parent parent;}subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}
}二、树形迭代器正向
2.1 前置
首先要清楚的是到下一个节点位置是按中序遍历走的主要有两种情况
该节点有右子树该节点没有右子树
1️⃣有右子树 总结有右子树后的下一个节点是右子树的最左节点
2️⃣没有右子树 总结没有右子树后下一个节点是祖先节点中左孩子是当前节点原来节点的位置或者左孩子是当前节点的父亲的那个祖先
有点弯再来图捋一捋
前置- -的逻辑与前置刚好相反
templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT, Ref, Ptr Self;Node* _node;RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}//前置Self operator(){//右子树存在if (_node-_right){//下一个节点在右子树的最左边Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}//右子树不存在else{Node* cur _node;Node* parent cur-_parent;//cur是parent的左子树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;//cur是parent的右子树时parent就是下一个while (parent parent-_left cur){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;}
};三、模拟实现set
set是k模型仿函数返回的只有key值。其他接口调用红黑树的
templateclass K
class set
{//仿函数struct SetKeyOfT{const K operator()(const K key){return key;}};
public:typedef typename RBTreeK, const K, SetKeyOfT::iterator iterator;typedef typename RBTreeK, const K, SetKeyOfT::const_iterator const_iterator;//迭代器iterator begin(){return _t.begin();}const_iterator begin() const{return _t.begin();}iterator end(){return _t.end();}const_iterator end() const{return _t.end();}//插入pairiterator, bool Insert(const K key){return _t.Insert(key);}//查找iterator Find(const K key){_t.Find(key);}
private:RBTreeK, const K, SetKeyOfT _t;
};四、模拟实现map
map是kv模型仿函数返回的取kv中的key值。其他接口调用红黑树的除此之外多了一个operator[]
templateclass K, class V
class map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::const_iterator const_iterator;//迭代器iterator begin(){return _t.begin();}const_iterator begin() const{return _t.begin();}iterator end(){return _t.end();}const_iterator end() const{return _t.end();}//插入pairiterator, bool Insert(const pairK, V kv){return _t.Insert(kv);}//查找iterator Find(const K key){_t.Find(key);}//operator[]V operator[](const K key){pairiterator, bool ret Insert(make_pair(key, V()));return ret.first-second;}
private:RBTreeK, pairconst K, V, MapKeyOfT _t;
};
