wordpress模板获取数据,哈尔滨网站优化对策,潍坊自助建站模板,上海模板建站源码目录 一、适配器红黑树 二、红黑树再设计 1. 重新设计 RBTree 的模板参数 2. 仿函数模板参数 3. 正向迭代器 构造 operator*() operator-() operator!() operator() operator--() 正向迭代器代码 4. 反向迭代器 构造 operator* operator- operator operator-- operat… 目录 一、适配器红黑树 二、红黑树再设计 1. 重新设计 RBTree 的模板参数 2. 仿函数模板参数 3. 正向迭代器 构造 operator*() operator-() operator!() operator() operator--() 正向迭代器代码 4. 反向迭代器 构造 operator* operator- operator operator-- operator! 反向迭代器代码 5. 红黑树主体 begin()、end()、 rbegin()、rend() insert 返回值 find返回值 STL标准库设计 6. 再设计后完整的RBTree代码 三、set、map封装 1. set基础封装 2. map基础封装 3. insert 4. map::operator[] 5. find 6. erase 7. 测试 一、适配器红黑树 STL在封装set、map时直接适配了RBTree——红黑树这里的红黑树相较上文我们的红黑树这里实现了构造、拷贝构造、赋值运算符重载、析构、删除节点等函数
//枚举定义结点的颜色
enum Colour
{RED,BLACK
};//红黑树结点的定义
templateclass K, class V
struct RBTreeNode
{//三叉链RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;//存储的键值对pairK, V _kv;//结点的颜色int _col; //红/黑//构造函数RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};//红黑树的实现
templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public://构造函数RBTree():_root(nullptr){}//拷贝构造RBTree(const RBTreeK, V t){_root _Copy(t._root, nullptr);}//赋值运算符重载现代写法RBTreeK, V operator(RBTreeK, V t){swap(_root, t._root);return *this;}//析构函数~RBTree(){_Destroy(_root);_root nullptr;}//查找函数Node* Find(const K key){Node* cur _root;while (cur){if (key cur-_kv.first) //key值小于该结点的值{cur cur-_left; //在该结点的左子树当中查找}else if (key cur-_kv.first) //key值大于该结点的值{cur cur-_right; //在该结点的右子树当中查找}else //找到了目标结点{return cur; //返回该结点}}return nullptr; //查找失败}//插入函数pairNode*, bool Insert(const pairK, V kv){if (_root nullptr) //若红黑树为空树则插入结点直接作为根结点{_root new Node(kv);_root-_col BLACK; //根结点必须是黑色return make_pair(_root, true); //插入成功}//1、按二叉搜索树的插入方法找到待插入位置Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first) //待插入结点的key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (kv.first cur-_kv.first) //待插入结点的key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //待插入结点的key值等于当前结点的key值{return make_pair(cur, false); //插入失败}}//2、将待插入结点插入到树中cur new Node(kv); //根据所给值构造一个结点Node* newnode cur; //记录新插入的结点便于后序返回if (kv.first parent-_kv.first) //新结点的key值小于parent的key值{//插入到parent的左边parent-_left cur;cur-_parent parent;}else //新结点的key值大于parent的key值{//插入到parent的右边parent-_right cur;cur-_parent parent;}//3、若插入结点的父结点是红色的则需要对红黑树进行调整while (parentparent-_col RED){Node* grandfather parent-_parent; //parent是红色则其父结点一定存在if (parent grandfather-_left) //parent是grandfather的左孩子{Node* uncle grandfather-_right; //uncle是grandfather的右孩子if (uncleuncle-_col RED) //情况1uncle存在且为红{//颜色调整parent-_col uncle-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}else //情况2情况3uncle不存在 uncle存在且为黑{if (cur parent-_left){RotateR(grandfather); //右单旋//颜色调整grandfather-_col RED;parent-_col BLACK;}else //cur parent-_right{RotateLR(grandfather); //左右双旋//颜色调整grandfather-_col RED;cur-_col BLACK;}break; //子树旋转后该子树的根变成了黑色无需继续往上进行处理}}else //parent是grandfather的右孩子{Node* uncle grandfather-_left; //uncle是grandfather的左孩子if (uncleuncle-_col RED) //情况1uncle存在且为红{//颜色调整uncle-_col parent-_col BLACK;grandfather-_col RED;//继续往上处理cur grandfather;parent cur-_parent;}else //情况2情况3uncle不存在 uncle存在且为黑{if (cur parent-_left){RotateRL(grandfather); //右左双旋//颜色调整cur-_col BLACK;grandfather-_col RED;}else //cur parent-_right{RotateL(grandfather); //左单旋//颜色调整grandfather-_col RED;parent-_col BLACK;}break; //子树旋转后该子树的根变成了黑色无需继续往上进行处理}}}_root-_col BLACK; //根结点的颜色为黑色可能被情况一变成了红色需要变回黑色return make_pair(newnode, true); //插入成功}//删除函数bool Erase(const K key){//用于遍历二叉树Node* parent nullptr;Node* cur _root;//用于标记实际的待删除结点及其父结点Node* delParentPos nullptr;Node* delPos nullptr;while (cur){if (key cur-_kv.first) //所给key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (key cur-_kv.first) //所给key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //找到了待删除结点{if (cur-_left nullptr) //待删除结点的左子树为空{if (cur _root) //待删除结点是根结点{_root _root-_right; //让根结点的右子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //进行红黑树的调整以及结点的实际删除}else if (cur-_right nullptr) //待删除结点的右子树为空{if (cur _root) //待删除结点是根结点{_root _root-_left; //让根结点的左子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //进行红黑树的调整以及结点的实际删除}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent cur;Node* minRight cur-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_kv.first minRight-_kv.first; //将待删除结点的key改为minRight的keycur-_kv.second minRight-_kv.second; //将待删除结点的value改为minRight的valuedelParentPos minParent; //标记实际删除结点的父结点delPos minRight; //标记实际删除的结点break; //进行红黑树的调整以及结点的实际删除}}}if (delPos nullptr) //delPos没有被修改过说明没有找到待删除结点{return false;}//记录待删除结点及其父结点用于后续实际删除Node* del delPos;Node* delP delParentPos;//调整红黑树if (delPos-_col BLACK) //删除的是黑色结点{if (delPos-_left) //待删除结点有一个红色的左孩子不可能是黑色{delPos-_left-_col BLACK; //将这个红色的左孩子变黑即可}else if (delPos-_right) //待删除结点有一个红色的右孩子不可能是黑色{delPos-_right-_col BLACK; //将这个红色的右孩子变黑即可}else //待删除结点的左右均为空{while (delPos ! _root) //可能一直调整到根结点{if (delPos delParentPos-_left) //待删除结点是其父结点的左孩子{Node* brother delParentPos-_right; //兄弟结点是其父结点的右孩子//情况一brother为红色if (brother-_col RED){delParentPos-_col RED;brother-_col BLACK;RotateL(delParentPos);//需要继续处理brother delParentPos-_right; //更新brother否则在本循环中执行其他情况的代码会出错}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParentPos-_col RED){delParentPos-_col BLACK;break;}//需要继续处理delPos delParentPos;delParentPos delPos-_parent;}else{//情况三brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空if ((brother-_right nullptr) || (brother-_right-_col BLACK)){brother-_left-_col BLACK;brother-_col RED;RotateR(brother);//需要继续处理brother delParentPos-_right; //更新brother否则执行下面情况四的代码会出错}//情况四brother为黑色且其右孩子是红色结点brother-_col delParentPos-_col;delParentPos-_col BLACK;brother-_right-_col BLACK;RotateL(delParentPos);break; //情况四执行完毕后调整一定结束}}else //delPos delParentPos-_right //待删除结点是其父结点的左孩子{Node* brother delParentPos-_left; //兄弟结点是其父结点的左孩子//情况一brother为红色if (brother-_col RED) //brother为红色{delParentPos-_col RED;brother-_col BLACK;RotateR(delParentPos);//需要继续处理brother delParentPos-_left; //更新brother否则在本循环中执行其他情况的代码会出错}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParentPos-_col RED){delParentPos-_col BLACK;break;}//需要继续处理delPos delParentPos;delParentPos delPos-_parent;}else{//情况三brother为黑色且其右孩子是红色结点左孩子是黑色结点或为空if ((brother-_left nullptr) || (brother-_left-_col BLACK)){brother-_right-_col BLACK;brother-_col RED;RotateL(brother);//需要继续处理brother delParentPos-_left; //更新brother否则执行下面情况四的代码会出错}//情况四brother为黑色且其左孩子是红色结点brother-_col delParentPos-_col;delParentPos-_col BLACK;brother-_left-_col BLACK;RotateR(delParentPos);break; //情况四执行完毕后调整一定结束}}}}}//进行实际删除if (del-_left nullptr) //实际删除结点的左子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_right;if (del-_right)del-_right-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_right;if (del-_right)del-_right-_parent delP;}}else //实际删除结点的右子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_left;if (del-_left)del-_left-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_left;if (del-_left)del-_left-_parent delP;}}delete del; //实际删除结点return true;}private://拷贝树Node* _Copy(Node* root, Node* parent){if (root nullptr){return nullptr;}Node* copyNode new Node(root-_data);copyNode-_parent parent;copyNode-_left _Copy(root-_left, copyNode);copyNode-_right _Copy(root-_right, copyNode);return copyNode;}//析构函数子函数void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;//建立subRL与parent之间的联系parent-_right subRL;if (subRL)subRL-_parent parent;//建立parent与subR之间的联系subR-_left parent;parent-_parent subR;//建立subR与parentParent之间的联系if (parentParent nullptr){_root subR;_root-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}}//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* parentParent parent-_parent;//建立subLR与parent之间的联系parent-_left subLR;if (subLR)subLR-_parent parent;//建立parent与subL之间的联系subL-_right parent;parent-_parent subL;//建立subL与parentParent之间的联系if (parentParent nullptr){_root subL;_root-_parent nullptr;}else{if (parent parentParent-_left){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}}//左右双旋void RotateLR(Node* parent){RotateL(parent-_left);RotateR(parent);}//右左双旋void RotateRL(Node* parent){RotateR(parent-_right);RotateL(parent);}Node* _root; //红黑树的根结点
};二、红黑树再设计
1. 重新设计 RBTree 的模板参数 之前我们的RBTree模板参数是Key-Value模型但此时我们不得不再考虑设计新的模板参数因为STL中set、map都是适配红黑树那么同一个RBTree模板如何同时适配setKey模型、mapKey-Value模型呢
templateclass K, class T
class RBTree为什么要设计为KT模板 根据是set 还是 mapT有两种可能 key 或 pairK, T所以我们需要第一个模板参数K它绝对是Key。 设计成KT是为了适配 find 、erase函数因为 find 函数需要参数Key如果以之前的模板参数设计set调用时很方便直接传递Key而map只能传递pair键值对那么 find 内部还要根据上层是set还是map来解析传递的模板参数是裸露的Key还是在键值对中的Key但是对于底层红黑树来说它并不知道上层容器是map还是set所以如果不修改模板参数那么这无疑加重了红黑树中 find 的设计难度 所以set、map都后退一步全都以统一的模板参数适配RBTreeset多传递一个模板参数Key、map将V修改为pairK, V这样set、map就可以协调统一的适配RBTree可以说set是跟着map “陪跑”因为set、map共用的红黑树底层 set容器K和T都代表键值Keymap容器K代表键值KeyT代表由Key和Value构成的键值对
//set
RBTreeK, K _t;//map
RBTreeK, pairK, V _t; 在红黑树中 typedef RBTreeNodeT Node红黑树节点直接接收参数T更改后代码如下
//红黑树结点的定义
templateclass T
struct RBTreeNode
{//三叉链RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;//存储的数据T _data;//结点的颜色int _col; //红/黑//构造函数RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};2. 仿函数模板参数 红黑树重新设计模板参数后节点存储的是T类型这个T即可能是Key也可能是pairKey, Value键值对那么如果在find函数内进行节点的Key大小比较时如果正确获取Key用来比较大小呢 底层红黑树的插入比较时因为T的类型不确定所以我们可以模仿list模拟实现时使用的仿函数来比较大小但是这里我们不直接在仿函数内比较大小而是使用 KeyOfT 类用它创建一个类对象使用仿函数来获取 T 中 Key而不是直接进行比较 对于setT 就是key对于mapT是pair所以要返回 pair 的 first 为什么不将仿函数功能复合直接设计成比大小返回bool类型 因为可能有指针等类型不能按平常的比较来比较并且在STL的set、map设计中还有一个用户传递的模板参数compare它的仿函数是专门用来比较的。 KeyOfT是红黑树内部用的两个仿函数各干各的活。如果都交给一个仿函数那么要排列组合设计很多种类型比较。 当底层红黑树需要进行两个结点之间键值的比较时都会通过传入的仿函数来获取相应结点的键值然后再进行比较下面以红黑树的查找函数为例 //查找函数
iterator Find(const K key)
{KeyOfT kot;Node* cur _root;while (cur){if (key kot(cur-_data)) //key值小于该结点的值{cur cur-_left; //在该结点的左子树当中查找}else if (key kot(cur-_data)) //key值大于该结点的值{cur cur-_right; //在该结点的右子树当中查找}else //找到了目标结点{return iterator(cur); //返回该结点}}return end(); //查找失败
}3. 正向迭代器
构造 红黑树的迭代器封装红黑树节点指针即可同list模拟实现迭代器传入三个模板参数是为了更好的设计const迭代器 //正向迭代器
templateclass T, class Ref, class Ptr
struct __TreeIterator
{typedef RBTreeNodeT Node; //结点的类型typedef __TreeIteratorT, Ref, Ptr Self; //正向迭代器的类型Node* _node; //正向迭代器所封装结点的指针//构造函数__TreeIterator(Node* node):_node(node) //根据所给结点指针构造一个正向迭代器{}};operator*()
当对正向迭代器进行解引用操作时我们直接返回 对应结点数据的引用
Ref operator*()
{return _node-_data; //返回结点数据的引用
}operator-()
当对正向迭代器进行-操作时我们直接返回对应结点数据的指针
Ptr operator-()
{return _node-_data; //返回结点数据的指针
}operator!()
operator重载! 和 比较时直接比较Node*即可地址最容易比较是否相等
//判断两个正向迭代器是否不同
bool operator!(const Self s) const
{return _node ! s._node; //判断两个正向迭代器所封装的结点是否是同一个
}
//判断两个正向迭代器是否相同
bool operator(const Self s) const
{return _node s._node; //判断两个正向迭代器所封装的结点是否是同一个
}迭代器设计最难的部分是迭代器的和--因为底层适配的是红黑树——非序列式容器或--是在树中移动 operator()
如果当前节点右子树不为空找右子树的最左节点--找左子树的左右节点如果当前结点的右子树为空则操作后应该在该结点的祖先结点中找到孩子不在父亲右的祖先
//前置
Self operator()
{if (_node-_right) //结点的右子树不为空{//寻找该结点右子树当中的最左结点Node* left _node-_right;while (left-_left){left left-_left;}_node left; //后变为该结点}else //结点的右子树为空{//寻找孩子不在父亲右的祖先Node* cur _node;Node* parent cur-_parent;while (parentcur parent-_right){cur parent;parent parent-_parent;}_node parent; //后变为该结点}return *this;
}operator--()
如果当前结点的左子树不为空则--操作后应该找到其左子树当中的最右结点。如果当前结点的左子树为空则--操作后应该在该结点的祖先结点中找到孩子不在父亲左的祖先
//前置--
Self operator--()
{if (_node-_left) //结点的左子树不为空{//寻找该结点左子树当中的最右结点Node* right _node-_left;while (right-_right){right right-_right;}_node right; //--后变为该结点}else //结点的左子树为空{//寻找孩子不在父亲左的祖先Node* cur _node;Node* parent cur-_parent;while (parentcur parent-_left){cur parent;parent parent-_parent;}_node parent; //--后变为该结点}return *this;
}正向迭代器代码
templateclass T, class Ref, class Ptr
struct __TreeIterator
{typedef RBTreeNodeT Node;typedef __TreeIteratorT, Ref, Ptr Self;/*不管此时__TreeIterator是普通迭代器还是const迭代器我们typedef的Iterator类型都是普通的迭代器*/typedef __TreeIteratorT, T, T* Iterator;//成员变量Node* _node;//构造函数__TreeIterator(Node* node):_node(node){}//当__TreeIterator是const迭代器时这里用普通迭代器构造const迭代器这是一个构造函数//当_TreeIterator是普通迭代器时这里用普通迭代器构造const迭代器这是一个拷贝构造函数__TreeIterator(const Iterator it):_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}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 cur parent-_left){cur parent;parent cur-_parent;}_node parent;}return *this;}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;// 找孩子是父亲左的那个祖先节点就是下一个要访问的节点while (parent){if (cur parent-_left) break;else{cur cur-_parent;parent parent-_parent;}}_node parent;}return *this;}bool operator!(const Self s) const{return _node ! s._node;}bool operator(const Self s) const{//拿地址来比较return _node s._node;}}; 4. 反向迭代器 在反向迭代器当中只有一个成员变量那就是反向迭代器封装的正向迭代器。反向迭代器的中成员函数都是通过调用正向迭代器对应的函数来完成相应功能的 构造 同list模拟实现反向迭代器直接适配正向迭代器
#pragma oncetemplateclass Iterator, class Ref, class Ptr
struct ReverseIterator
{typedef ReverseIteratorIterator, Ref, Ptr Self; //反向迭代器自身类型//封装普通迭代器Iterator _it;//构造ReverseIterator(Iterator it):_it(it){}};
operator* Ref operator* (){return *_it;}operator- Ptr operator-(){return _it.operator-();}operator 适配正向迭代器直接--即可。 Self operator(){--_it;return *this;}operator-- 适配正向迭代器直接即可 Self operator--(){_it;return *this;}注意我们实现的都是前置的或--
operator! bool operator!(const Self s) const{return _it ! s._it;}bool operator(const Self s) const{return _it s._it;}
反向迭代器代码
#pragma oncetemplateclass Iterator, class Ref, class Ptr
struct ReverseIterator
{typedef ReverseIteratorIterator, Ref, Ptr Self; //反向迭代器自身类型//封装普通迭代器Iterator _it;//构造ReverseIterator(Iterator it):_it(it){}Ref operator* (){return *_it;}Ptr operator-(){return _it.operator-();}Self operator(){--_it;return *this;}Self operator--(){_it;return *this;}bool operator!(const Self s) const{return _it ! s._it;}bool operator(const Self s) const{return _it s._it;}}; 5. 红黑树主体 我们需要在红黑树的实现当中进行迭代器类型的typedef。需要注意的是为了让外部能够使用typedef后的正向迭代器类型iterator我们需要在public区域进行typedef begin()、end()、
begin函数返回中序序列当中第一个结点的正向迭代器即最左结点。end函数返回中序序列当中最后一个结点下一个位置的正向迭代器这里直接用空指针构造一个正向迭代器
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node; //结点的类型
public:typedef __TreeIteratorT, T, T* iterator;typedef __TreeIteratorT, const T, const T* const_iterator;iterator begin(){//寻找最左结点Node* left _root;while (leftleft-_left){left left-_left;}//返回最左结点的正向迭代器return iterator(left);}iterator end(){//返回由nullptr构造得到的正向迭代器不严谨return iterator(nullptr);}const_iterator begin() const{Node* leftMin _root;while (leftMin leftMin-_left){leftMin leftMin-_left;}return iterator(leftMin);}const_iterator end() const{return iterator(nullptr);}private:Node* _root; //红黑树的根结点
};rbegin()、rend()
rbegin函数返回中序序列当中最后一个结点的反向迭代器即最右结点。rend函数返回中序序列当中第一个结点前一个位置的反向迭代器这里直接用空指针构造一个反向迭代器。
templateclass K, class T, class KeyOfT
struct RBTree
{typedef RBTreeNodeT Node;
public:typedef __TreeIteratorT, T, T* iterator;typedef __TreeIteratorT, const T, const T* const_iterator;typedef ReverseIteratoriterator, T, T* reverse_iterator;typedef ReverseIteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin(){Node* right _root;while (right right-_right){right right-_right;}return reverse_iterator(iterator(right));}reverse_iterator rend(){return reverse_iterator(iterator(nullptr));}const_reverse_iterator rbegin() const{Node* right _root;while (right right-_right){right right-_right;}return reverse_iterator(iterator(right));}const_reverse_iterator rend() const{return reverse_iterator(iterator(nullptr));}private:Node* _root; //红黑树的根结点
};insert 返回值
pairiterator, bool insert(const K key); 如果插入成功那么返回新插入的节点的迭代器与 true 构成的 pair如果插入失败相应的Key已经存在那么返回已经存在的 Key 对应的节点迭代器与 false构成的pair 所以在红黑树主体部分如果 insert 内部要返回 bool 类型时我们 make_pair 返回 pairiterator, bool类型即可 //插入函数
pairiterator, bool Insert(const T data)
{if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root), true);}Node* parent nullptr;Node* cur _root;KeyOfT kot;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);cur-_col RED;Node* newnode cur;if (kot(parent-_data) kot(data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else // u不存在 或 存在且为黑{if (cur parent-_left){// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else // parent grandfather-_right{Node* uncle grandfather-_left;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_right){// g// p// cRotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(iterator(newnode), true);
}
find返回值 同理在返回处 make_pair 即可。
注意如果没找到需返回end() iterator Find(const K key)
{Node* cur _root;KeyOfT kot;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();
}
STL标准库设计 上述所实现的迭代器是有缺陷的因为理论上我们对end()位置的正向迭代器进行--操作后应该得到最后一个结点的正向迭代器但我们实现end()时是直接返回由nullptr构造得到的正向迭代器的因此上述实现的代码无法完成此操作。 下面我们来看看CSLT库当中的实现逻辑 CSTL库当中实现红黑树时在红黑树的根结点处增加了一个头结点该头结点的左指针指向红黑树当中的最左结点右指针指向红黑树当中的最右结点父指针指向红黑树的根结点。 在该结构下实现begin()时直接用头结点的左孩子构造一个正向迭代器即可实现rbegin()时直接用头结点的右孩子构造一个反向迭代器即可实际是先用该结点构造一个正向迭代器再用正向迭代器构造出反向迭代器而实现end()和rend()时直接用头结点构造出正向和反向迭代器即可。此后通过对逻辑的控制就可以实现end()进行--操作后得到最后一个结点的正向迭代器。 但实现该结构需要更改当前很多函数的逻辑例如插入结点时若插入到了红黑树最左结点的左边或最右结点的右边此时需要更新头结点左右指针的指向
6. 再设计后完整的RBTree代码
#pragma once
#includeiostream
#include ReverseIterator.h
using namespace std;enum Colour
{RED,BLACK
};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){}
};// set-RBTreeK, K, SetKeyOfT _t;
// map-RBTreeK, pairK, V, MapKeyOfT _t;
templateclass K, class T, class KeyOfT
struct RBTree
{typedef RBTreeNodeT Node;
public:typedef __TreeIteratorT, T, T* iterator;typedef __TreeIteratorT, const T, const T* const_iterator;typedef ReverseIteratoriterator, T, T* reverse_iterator;typedef ReverseIteratorconst_iterator, const T, const T* const_reverse_iterator;iterator begin(){Node* leftMin _root;while (leftMin leftMin-_left){leftMin leftMin-_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* leftMin _root;while (leftMin leftMin-_left){leftMin leftMin-_left;}return iterator(leftMin);}const_iterator end() const{return iterator(nullptr);}reverse_iterator rbegin(){Node* right _root;while (right right-_right){right right-_right;}return reverse_iterator(iterator(right));}reverse_iterator rend(){return reverse_iterator(iterator(nullptr));}const_reverse_iterator rbegin() const{Node* right _root;while (right right-_right){right right-_right;}return reverse_iterator(iterator(right));}const_reverse_iterator rend() const{return reverse_iterator(iterator(nullptr));}//构造函数RBTree():_root(nullptr){}//拷贝构造RBTree(const RBTreeK, T, KeyOfT t){_root _Copy(t._root, nullptr);}//赋值运算符重载现代写法RBTreeK, T, KeyOfT operator(RBTreeK, T, KeyOfT t){swap(_root, t._root);return *this; //支持连续赋值}//析构函数~RBTree(){_Destroy(_root);_root nullptr;}iterator Find(const K key){Node* cur _root;KeyOfT kot;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();}//插入函数pairiterator, bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root), true);}Node* parent nullptr;Node* cur _root;KeyOfT kot;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);cur-_col RED;Node* newnode cur;if (kot(parent-_data) kot(data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else // u不存在 或 存在且为黑{if (cur parent-_left){// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else // parent grandfather-_right{Node* uncle grandfather-_left;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_right){// g// p// cRotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(iterator(newnode), true);}//删除函数bool Erase(const K key){KeyOfT kot;//用于遍历二叉树Node* parent nullptr;Node* cur _root;//用于标记实际的待删除结点及其父结点Node* delParentPos nullptr;Node* delPos nullptr;while (cur){if (key kot(cur-_data)) //所给key值小于当前结点的key值{//往该结点的左子树走parent cur;cur cur-_left;}else if (key kot(cur-_data)) //所给key值大于当前结点的key值{//往该结点的右子树走parent cur;cur cur-_right;}else //找到了待删除结点{if (cur-_left nullptr) //待删除结点的左子树为空{if (cur _root) //待删除结点是根结点{_root _root-_right; //让根结点的右子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //进行红黑树的调整以及结点的实际删除}else if (cur-_right nullptr) //待删除结点的右子树为空{if (cur _root) //待删除结点是根结点{_root _root-_left; //让根结点的左子树作为新的根结点if (_root){_root-_parent nullptr;_root-_col BLACK; //根结点为黑色}delete cur; //删除原根结点return true;}else{delParentPos parent; //标记实际删除结点的父结点delPos cur; //标记实际删除的结点}break; //进行红黑树的调整以及结点的实际删除}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent cur;Node* minRight cur-_right;while (minRight-_left){minParent minRight;minRight minRight-_left;}cur-_data minRight-_data; //将待删除结点的_data改为minRight的_datadelParentPos minParent; //标记实际删除结点的父结点delPos minRight; //标记实际删除的结点break; //进行红黑树的调整以及结点的实际删除}}}if (delPos nullptr) //delPos没有被修改过说明没有找到待删除结点{return false;}//记录待删除结点及其父结点用于后续实际删除Node* del delPos;Node* delP delParentPos;//调整红黑树if (delPos-_col BLACK) //删除的是黑色结点{if (delPos-_left) //待删除结点有一个红色的左孩子不可能是黑色{delPos-_left-_col BLACK; //将这个红色的左孩子变黑即可}else if (delPos-_right) //待删除结点有一个红色的右孩子不可能是黑色{delPos-_right-_col BLACK; //将这个红色的右孩子变黑即可}else //待删除结点的左右均为空{while (delPos ! _root) //可能一直调整到根结点{if (delPos delParentPos-_left) //待删除结点是其父结点的左孩子{Node* brother delParentPos-_right; //兄弟结点是其父结点的右孩子//情况一brother为红色if (brother-_col RED){delParentPos-_col RED;brother-_col BLACK;RotateL(delParentPos);//需要继续处理brother delParentPos-_right; //更新brother否则在本循环中执行其他情况的代码会出错}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParentPos-_col RED){delParentPos-_col BLACK;break;}//需要继续处理delPos delParentPos;delParentPos delPos-_parent;}else{//情况三brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空if ((brother-_right nullptr) || (brother-_right-_col BLACK)){brother-_left-_col BLACK;brother-_col RED;RotateR(brother);//需要继续处理brother delParentPos-_right; //更新brother否则执行下面情况四的代码会出错}//情况四brother为黑色且其右孩子是红色结点brother-_col delParentPos-_col;delParentPos-_col BLACK;brother-_right-_col BLACK;RotateL(delParentPos);break; //情况四执行完毕后调整一定结束}}else //delPos delParentPos-_right //待删除结点是其父结点的左孩子{Node* brother delParentPos-_left; //兄弟结点是其父结点的左孩子//情况一brother为红色if (brother-_col RED) //brother为红色{delParentPos-_col RED;brother-_col BLACK;RotateR(delParentPos);//需要继续处理brother delParentPos-_left; //更新brother否则在本循环中执行其他情况的代码会出错}//情况二brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delParentPos-_col RED){delParentPos-_col BLACK;break;}//需要继续处理delPos delParentPos;delParentPos delPos-_parent;}else{//情况三brother为黑色且其右孩子是红色结点左孩子是黑色结点或为空if ((brother-_left nullptr) || (brother-_left-_col BLACK)){brother-_right-_col BLACK;brother-_col RED;RotateL(brother);//需要继续处理brother delParentPos-_left; //更新brother否则执行下面情况四的代码会出错}//情况四brother为黑色且其左孩子是红色结点brother-_col delParentPos-_col;delParentPos-_col BLACK;brother-_left-_col BLACK;RotateR(delParentPos);break; //情况四执行完毕后调整一定结束}}}}}//进行实际删除if (del-_left nullptr) //实际删除结点的左子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_right;if (del-_right)del-_right-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_right;if (del-_right)del-_right-_parent delP;}}else //实际删除结点的右子树为空{if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_left;if (del-_left)del-_left-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_left;if (del-_left)del-_left-_parent delP;}}delete del; //实际删除结点return true;}private://拷贝树Node* _Copy(Node* root, Node* parent){if (root nullptr){return nullptr;}Node* copyNode new Node(root-_data);copyNode-_parent parent;copyNode-_left _Copy(root-_left, copyNode);copyNode-_right _Copy(root-_right, copyNode);return copyNode;}//析构函数子函数void _Destroy(Node* root){if (root nullptr){return;}_Destroy(root-_left);_Destroy(root-_right);delete root;}//左单旋void RotateL(Node* parent){_rotateCount;Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}//右单旋void RotateR(Node* parent){_rotateCount;Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright)curright-_parent parent;Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}//检查红黑树颜色bool CheckColour(Node* root, int blacknum, int benchmark){if (root nullptr){if (blacknum ! benchmark)return false;return true;}if (root-_col BLACK){blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 出现连续红色节点 endl;return false;}return CheckColour(root-_left, blacknum, benchmark) CheckColour(root-_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr)return true;if (root-_col ! BLACK){return false;}// 基准值int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_root);}int Height(Node* root){if (root nullptr)return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}private:Node* _root nullptr;public:int _rotateCount 0;
};
三、set、map封装
1. set基础封装
#include RBTree.hnamespace my_set
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::reverse_iterator reverse_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}reverse_iterator rbegin(){return _t.rbegin();}reverse_iterator rend(){return _t.rend();}pairiterator, bool insert(const K key){}void erase(const K key){}iterator find(const K key){}private:RBTreeK, K, SetKeyOfT _t;};
} 2. map基础封装
#include RBTree.hnamespace my_map
{templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename RBTreeK, pairK, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairK, V, MapKeyOfT::reverse_iterator reverse_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}reverse_iterator rbegin(){return _t.rbegin();}reverse_iterator rend(){return _t.rend();}pairiterator, bool insert(const pairK, V kv){}V operator[](const K key){}void erase(const K key){}iterator find(const K key){}private:RBTreeK, pairK, V, MapKeyOfT _t;};
}
3. insert
set
pairiterator, bool insert(const K key)
{return _t.Insert(key);
} set 的迭代器 typedef 了红黑树的 const_iterator
typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;map
pairiterator, bool insert(const pairK, V kv)
{return _t.Insert(kv);
} map 的 iterator 没有 typedef 红黑树的 const_iterator
typedef typename RBTreeK, pairK, V, MapKeyOfT::iterator iterator;编译 问题的引发在封装map的operator[] 函数时需要用到insert函数的pairiterator, bool返回值但是此时 set 的返回处出现问题 C2440 “return”: 无法从“std::pair__TreeIteratorT,T ,T *,bool”转换为“std::pair__TreeIteratorT,const T ,const T *,bool” 摸索 set 底层适配 RBtree 结构 所以 set 的 insert 调用的是 RBTree 的 insert 函数又 RBTree 的 insert 函数返回的是 pairiterator, bool 类型这里的 iterator是红黑树返回的普通迭代器类型 注意如果在 set.h 文件中此时 pair 的 iterator 类型其实是 const_iterator 类型因为我们是根据 STL 中的 set 设计来设计我们的 set STL 中 set 的 iterator 其实是 const_iterator 的 typedef是为了保证set的key不被修改因为底层红黑树节点是靠key来构建的一旦key被修改那么整个树的结构就会混乱无序 所以 set 的 insert 在 return _t.Insert 时在 pair 的构造函数的初始化列表处会发生普通迭代器构造 const 迭代器的过程 所以我们需要在红黑树迭代器类中再手写一个构造函数参数是普通迭代器用来支持普通迭代器向const迭代器转换 迭代器类中默认生成的拷贝构造就已经够用了因为成员变量类型是Node*是内置类型可以浅拷贝那么为什么还要设计迭代器的拷贝构造 其实这里并不是拷贝构造而是重载构造函数。当 set 的 insert 返回时我们先来看pair类的构造函数
此时T1类型是const_iterator
template class T1, class T2
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair(): first(T1()) , second(T2()){}pair(const T1 a, const T2 b): first(a) 此时的参数a是普通iterator, second(b) first是const_iterator{}
}; 我们发现在pair 的构造函数的初始化列表处出现了以普通迭代器构造const迭代器的过程而我们的迭代器此时并没有专门接收迭代器类型的构造函数 所以我们要在红黑树的迭代器类中实现一个迭代器构造函数支持从普通迭代器转为const迭代器功能 我们如何在一个const迭代器类中获得普通迭代器类型 在迭代器类设计时typedef一个普通迭代器即可 //不管此时__TreeIterator是普通迭代器还是const迭代器//我们typedef的Iterator类型都是普通的迭代器typedef __TreeIteratorT, T, T* Iterator;不管此时__TreeIterator 是普通迭代器还是 const 迭代器我们 typedef 的 Iterator 类型都是普通的迭代器 //当__TreeIterator是const迭代器时这里用普通迭代器构造const迭代器这是一个构造函数//当_TreeIterator是普通迭代器时这里用普通迭代器构造const迭代器这是一个拷贝构造函数__TreeIterator(const Iterator it):_node(it._node){}
当 __TreeIterator 是const迭代器时这里用普通迭代器构造const迭代器这是一个构造函数因为我们在迭代器类中已经写过构造函数了所以还需要重载一个以迭代器为参数的构造函数当 __TreeIterator 是普通迭代器时这里用普通迭代器构造const迭代器这是一个拷贝构造函数 4. map::operator[] map::operator[]功能我们在map介绍时已经讲过了返回 insert 返回的 iterator 的 second 数据的引用即不管insert是否成功我们都能获取Key的value的引用
V operator[](const K key)
{pairiterator, bool ret insert(make_pair(key, V()));iterator it ret.first;return it-second;
}
5. find 调用适配的红黑树的Find函数即可
iterator find(const K key)
{return _t.Find(key);
}
6. erase 调用适配的红黑树的Erase函数即可
void erase(const K key)
{_t.Erase(key);
}
7. 测试
#include iostream#include MyMap.h
#include MySet.hint main()
{//验证mapmy_map::mapint, int m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(4, 4));m.insert(make_pair(3, 8));m.insert(make_pair(5, 1));my_map::mapint, int::reverse_iterator mit m.rbegin();while (mit ! m.rend()){cout mit-first : mit-second endl;mit;}cout endl;m[1] 100;m[99] 120;m[3] 4;for (const auto e : m){cout e.first : e.second endl;}cout endl;//验证setmy_set::setint s;s.insert(5);s.insert(15);s.insert(54);s.insert(23);s.insert(0);s.insert(9);s.insert(4);my_set::setint::iterator sit s.begin();while (sit ! s.end()){cout *sit ;sit;}cout endl;for (const auto e : s){cout e ;}return 0;}
