网络公司+网站建设+小程序,申请一个电子邮箱,用宝塔做网站,企业服务专员红黑树 搜索二叉树搜索二叉树的模拟实现平衡搜索二叉树(AVL Tree)平衡搜索二叉树的模拟实现红黑树(Red Black Tree)红黑树的模拟实现 红黑树的应用(Map 和 Set)Map和Set的封装 搜索二叉树
搜索二叉树的概念#xff1a;二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树: 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
简单来说搜索二叉树的一个原则如果左右树根不为空左树永远比根小右树永远比根大 这个原则可运用到搜索二叉树的每个节点
用一张图来了解搜索二叉树
二叉搜索树的优点 查找效率如果现在要在数组中查找一个数字是否存在我们只能去遍历数组但是如果在搜索二叉树中查找从根节点开始判断要么查找的数比根小要么比根大要么和根相等如果要找的数在左边那么右树可以全部排除如果在右边那么左边的数可以全部排除以此往复下去每次都可以将一半的数据排除所以查找效率大大提高
二叉搜索树的缺点 极端情况还是在二叉搜索树中查找一个数字但是这个时候出现了一个极端情况 上图
这颗树符合搜索二叉树的原则吗 答案是 当然如果左右树不为空左树永远比根小右树永远比根大很显然这颗树就是搜索二叉树 那么再来看一张图
这颗树是搜索二叉树吗 我就不多说了
如果在以上两种情况下树的节点向左或者向右呈现线型结构这个时候再去查询一个数据假设这个数据在最下面比如上图中的 16 那搜索二叉树和数组有什么区别所以如果碰到这种极端情况搜素二叉树的优势就全没了
但是在一般的情况下搜索二叉树的查找效率和远远优于数组的
搜索二叉树的模拟实现
直接上代码 先来看一下搜索二叉树的整体框架
#pragma once
#includeiostreamusing namespace std;//自定义命名空间
namespace ys
{//定义搜索二叉树的节点//使用模板来定义数据类型templateclass Tstruct TreeNode{T _val;//数据TreeNode* _left;//左树TreeNode* _right;//右树//构造函数初始化TreeNode(T data):_val(data),_left(nullptr),_right(nullptr){}};//定义搜索二叉树类//使用模板接受数据类型templateclass Tclass Tree{//对树的结构体进行重命名方便后续操作typedef TreeNode node;public://插入bool insert(){}//删除bool erase(){}//查询bool find(){}//打印整颗树void Printf(){}private:node* _root nullptr;//根节点};
}
总共4个接口我们来逐一攻破 先从查询find开始 在搜索二叉树中查询一个数字是否存在从根节点开始查找如果等于根节点返回true否则和根节点比较大小比根小转到左树去查找比根大转到右树去查找 代码
//查询bool find(const T data){node* cur _root;while (cur){//找到了if (data cur-_val) return true;if (data cur-_val) cur cur-_left;//比根小转到左树else cur cur-_right;//比根大转到右树}return false;}插入(insert)和查询的逻辑大差不差首先还是比较要插入的数字比根小转到左树寻找要插入的位置比根大转到右树寻找要插入的位置
//插入bool insert(const T data){//如果根为空说明是空树直接插入根即可if (_root nullptr){_root new node(data);return true;}else{//首先查询树中是否有data如果有直接返回falseif (find(data)) return false;//如果没有再进行插入node* cur _root;node* prev nullptr;while (cur){//如果data小于根在左树寻找插入位置if (data cur-_val){prev cur;cur cur-_left;}//如果data大于根在右树寻找插入位置else{prev cur;cur cur-_right;}}//循环结束说明已经找到了插入的位置//插入到prev下面的两颗子树//判断插入prev左边还是右边if (data prev-_val)prev-_right new node(data);elseprev-_left new node(data);return true;}}最关键的来了删除(erase) 删除的步骤 1找到要删除的节点(cur)的父树(prev)
2判断要删除的节点是否有左右树 (1)如果只有左树将cur的左树连接到prev (2)如果只有右树将cur的右树连接到prev
3如果左右树都有 (1)将左树的最大节点和要删除的节点进行替换 (2)将右树的最小节点和要删除的节点进行替换
//删除bool erase(const T data){//树为空返回falseif (_root nullptr) return false;node* cur _root;node* prev nullptr;//记录父节点//找到要删除的节点while (cur){if (data cur-_val){prev cur;cur cur-_left;}else if(data cur-_val){prev cur;cur cur-_right;}//找到了要删除的节点//判断要删除的节点是否拥有左右树else{//如果cur的左树为空直接将cur的右树和cur的父树连接if (cur-_left nullptr){//判断cur是否为根节点if (cur _root){//如果cur就是根节点并且左树为空直接将cur的第一个右树设为root_root cur-_right;}else{if (prev-_left cur) prev-_left cur-_right;else prev-_right cur-_right;}}//如果cur的右树为空直接将cur的左树和cur的父树连接else if (cur-_right nullptr){//判断cur是否为根节点if (cur _root){//如果cur就是根节点并且左树为空直接将cur的第一个右树设为root_root cur-_right;}else{if (prev-_right cur) prev-_right cur-_left;else prev-_left cur-_left;}}//如果要删除的节点同时拥有左右树有两种删除方法else{//1使用左树的最大节点进行替换//2使用右树的最小节点进行替换//这里我们采用第一种方法使用左树的最大节点进行替换node* leftmax cur-_left;node* pleftmax nullptr;//找到左树的最大节点while (leftmax){pleftmax leftmax;leftmax leftmax-_right;}//如果左树的最大节点有左树//将最大节点的左树连接到他的父树if (leftmax-_left){pleftmax-_right leftmax;}//将要删除节点的数据和左树最大节点继续交换cur-_val leftmax-_val;//释放左树最大节点delete leftmax;leftmax nullptr;}return true;}}return false;}中序遍历 这个就不多说了直接上代码
void _printf(node* root){if (root nullptr) return;_printf(root-_left);cout root-_val ;_printf(root-_right);}//中序遍历打印整颗树void Printf(){if (_root nullptr) cout 空树 endl;_printf(_root);}整体代码
#pragma once
#includeiostreamusing namespace std;//自定义命名空间
namespace ys
{//定义搜索二叉树的节点//使用模板来定义数据类型templateclass Tstruct TreeNode{T _val;//数据TreeNode* _left;//左树TreeNode* _right;//右树//构造函数初始化TreeNode(T data):_val(data),_left(nullptr),_right(nullptr){}};//定义搜索二叉树类//使用模板接受数据类型templateclass Tclass Tree{typedef TreeNodeT node;public://插入bool insert(const T data){//如果根为空说明是空树直接插入根即可if (_root nullptr){_root new node(data);return true;}else{//首先查询树中是否有data如果有直接返回falseif (find(data)) return false;//如果没有再进行插入node* cur _root;node* prev nullptr;while (cur){//如果data小于根在左树寻找插入位置if (data cur-_val){prev cur;cur cur-_left;}//如果data大于根在右树寻找插入位置else{prev cur;cur cur-_right;}}//循环结束说明已经找到了插入的位置//插入到prev下面的两颗子树//判断插入prev左边还是右边if (data prev-_val)prev-_right new node(data);elseprev-_left new node(data);return true;}}//删除bool erase(const T data){//树为空返回falseif (_root nullptr) return false;node* cur _root;node* prev nullptr;//记录父节点//找到要删除的节点while (cur){if (data cur-_val){prev cur;cur cur-_left;}else if(data cur-_val){prev cur;cur cur-_right;}//找到了要删除的节点//判断要删除的节点是否拥有左右树else{//如果cur的左树为空直接将cur的右树和cur的父树连接if (cur-_left nullptr){//判断cur是否为根节点if (cur _root){//如果cur就是根节点并且左树为空直接将cur的第一个右树设为root_root cur-_right;}else{if (prev-_left cur) prev-_left cur-_right;else prev-_right cur-_right;}}//如果cur的右树为空直接将cur的左树和cur的父树连接else if (cur-_right nullptr){//判断cur是否为根节点if (cur _root){//如果cur就是根节点并且左树为空直接将cur的第一个右树设为root_root cur-_right;}else{if (prev-_right cur) prev-_right cur-_left;else prev-_left cur-_left;}}//如果要删除的节点同时拥有左右树有两种删除方法else{//1使用左树的最大节点进行替换//2使用右树的最小节点进行替换//这里我们采用第一种方法使用左树的最大节点进行替换node* leftmax cur-_left;node* pleftmax nullptr;//找到左树的最大节点while (leftmax){pleftmax leftmax;leftmax leftmax-_right;}//如果左树的最大节点有左树//将最大节点的左树连接到他的父树if (leftmax-_left){pleftmax-_right leftmax;}//将要删除节点的数据和左树最大节点继续交换cur-_val leftmax-_val;//释放左树最大节点delete leftmax;leftmax nullptr;}return true;}}return false;}//查询bool find(const T data){node* cur _root;while (cur){//找到了if (data cur-_val) return true;if (data cur-_val) cur cur-_left;//比根小转到左树else cur cur-_right;//比根大转到右树}return false;}void _printf(node* root){if (root nullptr) return;_printf(root-_left);cout root-_val ;_printf(root-_right);}//中序遍历打印整颗树void Printf(){if (_root nullptr) cout 空树 endl;_printf(_root);}private:node* _root nullptr;//根节点};
}
测试用例 插入
查询
删除
平衡搜索二叉树(AVL Tree)
搜索二叉树有两个极端情况 1当所有的节点都只有左树那么整颗树就会呈现出向左的一条线性结构
2当所有的节点都只有右树那么整颗树就会呈现出向右的一条线性结构 AVL 是大学教授 G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写他们两个提出的平衡二叉树的概念为了纪念他们将 平衡二叉树 称为 AVL树。 当搜索二叉树出现这两种情况的时候搜索二叉树的优势就全没有了所以为了避免这种情况出现伟大的早期程序员设计出了平衡搜索二叉树(AVL树)
AVL树的概念 AVL树本质是就是一棵搜索二叉树【但是】为了不让树呈现出一边倒的现象AVL树的设计者又给加了两个原则 1它是一棵空树或它的左右两个子树的高度之差(简称平衡因子)不超过1 2左右两个子树 也都是一棵平衡二叉树。
平衡因子 一个没有左树和右树的节点平衡因子为0 如果插入一个左树平衡因子减1 如果插入一个右树平衡因子加1 不论是平衡因子减1或者加1当前节点的父树的平衡因子也要跟随变动依次类推 【注意】当平衡因子 2或者 -2的时候说明这颗树已经不平衡了所以此时不要再向上调整父树平衡因子而是在不平衡的节点做出处理
AVL树的旋转 1左单旋 当一棵AVL树的右树高于左树的时候将右树向左边旋转 旋转方式1将25连接到20的右树
2将20练级到65的左树 旋转完成树已经达成平衡状态
2右单旋 当一个AVL树的左树高于右树将左树向右旋转
1,将60连接到70的左树 2将70连接到50的右树 旋转完成树已经达成平衡状态
3左右旋 新节点插入较高左子树的右侧—左右先左单旋再右单旋 1将2进行左旋 2将5进行右旋 旋转完成树已经达成平衡状态
4右左旋 新节点插入较高右子树的左侧—右左先右单旋再左单旋
先将5进行右旋 再将2进行左旋
平衡搜索二叉树的模拟实现
直接上代码
#includeiostream
#includeassert.h
using namespace std;namespace avlt
{templateclass K,class Vstruct AvlNode{pairK,V _kv;//值AvlNode* _left;//左树AvlNode* _right;//右树AvlNode* _parent;//父树int _bf;//平衡因子AvlNode(const pairK, V data ):_kv(data),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};templateclass K,class Vclass AvlTree{typedef AvlNodeK,V node;public://插入bool insert(const pairK, V data){//判断根节点是否为空if (_root nullptr){//如果根节点为空直接插入根节点_root new node(data);return true;}//查询树中是否已经存在要插入的数据if (find(data.first)){cout data.first 已存在 endl;return false;}//首先找到要插入的节点node* cur _root;node* parent nullptr;while (cur){if (cur-_kv.first data.first){parent cur;cur cur-_left;}else {parent cur;cur cur-_right;}}//插入并连接cur new node(data);if (parent-_kv.first cur-_kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}//向上更新平衡因子,直到检查到根节点while (parent){//更新平衡因子if (parent-_left cur)parent-_bf--;elseparent-_bf;//以parent为根节点的树是平衡的但不是完全平衡继续向上更新if (parent-_bf 1 || parent-_bf -1){//cur cur-_parent;cur parent;parent parent-_parent;}//平衡因子为0说明树是平衡的不要再做调整直接跳出循环else if (parent-_bf 0){break;}//平衡因子不平衡else if(parent-_bf 2 || parent-_bf -2){//右树高左单旋if (parent-_bf 2 cur-_bf 1){RotateL(parent);}//左树高右单旋else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}//左树的右树高,先左旋再右旋else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}//右树的左树高先右旋再左旋else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}elseassert(false);break;}elseassert(false);}return true;}private://旋转//左旋void RotateL(node* parent){node* subR parent-_right;node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;node* ppnode parent-_parent;subR-_left parent;parent-_parent subR;if (ppnode nullptr){_root subR;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}parent-_bf subR-_bf 0;}//右旋void RotateR(node* parent){node* subL parent-_left;node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}subL-_bf parent-_bf 0;}//左右旋void RotateLR(node* parent){node* subL parent-_left;node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1){parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else if (bf -1){parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 0){parent-_bf 0;subLR-_bf 0;subL-_bf 0;}else{cout 左右旋 endl;assert(false);}}//右左旋void RotateRL(node* parent){node* subR parent-_right;node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 1){subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf -1){subR-_bf 1;parent-_bf 0;subRL-_bf 0;}else if (bf 0){subR-_bf 0;parent-_bf 0;subRL-_bf 0;}else{cout 右左旋 endl;assert(false);}}//查询bool find(const K data){if (_root nullptr) return false;node* cur _root;while (cur){if (cur-_kv.first data)return true;if (cur-_kv.first data)cur cur-_left;elsecur cur-_right;}return false;}
public://中序遍历void _print(node* root){if (root nullptr) return;_print(root-_left);cout root-_kv.first : root-_kv.second endl;_print(root-_right);}void print(){_print(_root);}private:node* _root nullptr;//根结点};
}来看一下效果; 我们多试几次
红黑树(Red Black Tree)
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
红黑树的性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 红黑树本身就是一棵AVL树但是他比AVL树具有更高的效率
当红黑树不平衡的时候他不能像AVL树那样只进行旋转而是旋转加变色
假设现在有一个红黑树 cur为新插入的节点 此时新插入的cur违反了红黑树【如果一个节点是红色的则它的两个孩子结点是黑色的 】的规则 那么怎么解决这个问题呢
第一种情况叔叔节点存在且为红色只变色
第一步判断父树是否为黑色节点如果是黑色节点那就不用做处理因为没有违反红黑树的规则
第二步如果父树是红色节点将父树变成黑色节点 第三步如果叔叔节点存在将叔叔节点父树的兄弟节点也变成黑色 第四步将爷爷节点变成红色 第五步将爷爷节点当做一个新插入的节点继续向上更新变色
然后重复上面的4个步骤 如果最后发现走到了根节点必须将根节点变成黑色
第二种情况旋转加变色 当插入的节点没有叔叔节点的时候 首先将爷爷节点进行右单旋 再将父节点变成黑色爷爷节点变成红色
第三种情况叔叔存在且为黑 首先cur是新增节点但是一般情况下叔叔节点颜色和父节点颜色是相同的但是当上面这种情况出现后向上调整会变成 由于向上调整变色4被当做新增节点此时4的叔叔节点是黑色父节点是红色这个时候就要采用双旋的方案来解决这个问题 1将2左旋 2对7进行右旋
最后进行变色
当然红黑树增加节点旋转变色的情况很多但是上述几种方案基本概述了所有情况的原理其他情况与之不同的就是旋转的方向不一样原理都是一样的
红黑树的模拟实现
话不多说直接上代码
#pragma once
#includeiostreamusing namespace std;namespace rb_tree
{//枚举定义节点颜色enum Colour{RED,BLACK};//红黑树节点templateclass K,class Vstruct RBTreeNode{pairK, V _kv;//数据RBTreeNode* _left;//左树RBTreeNode* _right;//右树RBTreeNode* _parent;//父树Colour _col;//节点颜色RBTreeNode(const pairK, V data):_kv(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)//节点颜色初始化为红色{}};templateclass K,class Vclass RBTree{typedef RBTreeNodeK,V node;public://插入bool insert(const pairK,V data){//如果根节点为空插入根节点并将颜色改为黑色if (_root nullptr){_root new node(data);_root-_col BLACK;return true;}//找到可以插入的地方node* cur _root;node* parent nullptr;while (cur){if (cur-_kv.first data.first){parent cur;cur cur-_left;}else if(cur-_kv.first data.first){parent cur;cur cur-_right;}else return false;}//插入并连接cur new node(data);if (parent-_kv.first cur-_kv.first)parent-_left cur;elseparent-_right cur;cur-_parent parent;//如果父节点是黑色插入的节点是红色直接返回true不需要做处理if (parent-_col BLACK) return true;//如果父节点是红色开始处理while (parent parent-_col RED){//找到祖父节点node* grandfather parent-_parent;//找到叔叔节点if (grandfather-_left parent){node* uncle grandfather-_right;//如果叔叔节点不为空且是红色if (uncle uncle-_col RED){//将叔叔和父节点变黑uncle-_col parent-_col BLACK;//将祖父节点变红grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}//叔叔节点存在且为黑或者叔叔节点不存在else{//第一种情况// g// p u// cif (cur parent-_left){//对p继续右旋RotateR(parent);//再进行变色parent-_col BLACK;grandfather-_col RED;}//第二种情况// g// p u// celse{//先左旋parentRotateL(parent);//再右旋grandfatherRotateR(grandfather);//变色grandfather-_col RED;cur-_col BLACK;}break;}}//如果parent是祖父节点的右边叔叔节点就是祖父节点的左边else{//找到叔叔节点node* uncle grandfather-_left;//如果叔叔节点存在且为红if (uncle uncle-_col RED){uncle-_col BLACK;parent-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}//如果叔叔节点不存在或存在且为黑else{//第一种情况// g// u p// cif (cur parent-_right){//首先对grandfather进行左单旋RotateL(grandfather);//变色parent-_col BLACK;grandfather-_col RED;}//第二种情况// g// u p// celse{//首先对parent进行右单旋RotateR(parent);//再对grandfather进行左单旋RotateL(grandfather);//变色cur-_col BLACK;grandfather-_col RED;}}break;}}//不论什么情况下根节点都必须是黑色的_root-_col BLACK;return true;}//中序遍历void _print(node* root){if (root nullptr) return;_print(root-_left);cout root-_kv.first : root-_kv.second endl;_print(root-_right);}void print(){_print(_root);}private://左单旋void RotateL(node* parent){node* SubR parent-_right;node* SubRL SubR-_left;parent-_right SubRL;if (SubRL)SubRL-_parent parent;node* pparent parent-_parent;parent-_parent SubR;SubR-_left parent;if (pparent){if (pparent-_left parent)pparent-_left SubR;elsepparent-_right SubR;SubR-_parent pparent;}else{_root SubR;SubR-_parent nullptr;}}//右单旋void RotateR(node* parent){node* SubL parent-_left;node* SubLR SubL-_right;node* pparent parent-_parent;parent-_left SubLR;SubL-_right parent;parent-_parent SubL;if (SubLR)SubLR-_parent parent;if (pparent){if (pparent-_left parent)pparent-_left SubL;elsepparent-_right SubL;SubL-_parent pparent;}else{_root SubL;SubL-_parent nullptr;}}private:node* _root nullptr;//根节点};
}测试一下
#includeRBTree.h
#includeset
#includemap
#includeutility
#includectime
using namespace std;void test1()
{srand(time(nullptr));rb_tree::RBTreeint, int rb;for (int i 0; i 30; i){rb.insert(make_pair(rand() % 100, rand() % 10));}rb.print();
}int main()
{test1();return 0;
}再试几次 没毛病…
红黑树的应用(Map 和 Set)
Map和Set的基本使用
Map和Set的封装
看完Map和Set的基本使用基于上面的红黑树代码我们来手写一个简单的Map和Set 主要功能有三个插入查询迭代器
重点说一下迭代器和红黑树的模板参数设计
STL的map和set是共用红黑树的代码的也就是说一张红黑树的代码map可以直接封装set也可以
我们来看上面我们写的红黑树代码 我们设计的红黑树是key Value结构的如果是用在map上是合适的 但是set呢set的key就是value但往往set只有一个参数而要使用红黑树至少得两个参数那就不能使用这个红黑树了
怎么办STL的设计者想出了一个非常棒的点子修改红黑树的模板参数 set
map
我们来画图演示一下 首先将红黑树的参数改成三个第一个参数不重要重要的是第二个参数set和map指明参数类型的时候以第二个参数为准这样红黑树既可以让set使用也可以让map使用 但是问题又来了在插入的时候需要比较大小map传入的是一个pair对象不能直接比较所以第三个参数的作用就体现出来了这是一个仿函数类在比较的时候创建一个仿函数对象用仿函数去比较如果是set比较的是Key如果是map就返回Key去比较
不得不说STL这个设计非常棒
具体封装直接上代码 红黑树代码
#pragma once
#includeiostream
#includeassert.h
using namespace std;namespace rb_tree
{//枚举定义节点颜色enum Colour{RED,BLACK};//红黑树节点templateclass Tstruct RBTreeNode{T _data;//数据RBTreeNode* _left;//左树RBTreeNode* _right;//右树RBTreeNode* _parent;//父树Colour _col;//节点颜色RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)//节点颜色初始化为红色{}};//迭代器// Ref T Ptr T*templateclass T,class Ref,class Ptrstruct RBTreeIterator{typedef RBTreeIteratorT, Ref, Ptr Self;typedef RBTreeNodeT node;node* nod;RBTreeIterator(node* root):nod(root){}Ref operator *(){return nod-_data;}Ptr operator -(){return (nod-_data);}bool operator !(const Self data){return nod ! data.nod;}Self operator (){//如果nod的右树不为空右树的最左节点就是下一个位置if (nod-_right){node* subleft nod-_right;while (subleft-_left){subleft subleft-_left;}nod subleft;}//如果右树为空沿着到根的路径找子树为父树的左子树就是下一个位置else{node* cur nod;node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}nod parent;}return *this;}Self operator --(){//如果左树存在左树的右节点就是上一个否则左树就是上一个if (nod-_left){node* subright nod-_left;while (subright-_right){subright subright-_right;}nod subright;}else{//向上找如果当前节点是父树的右节点则父树就是上一个节点node* parent nod-_parent;node* cur nod;while (parent parent-_left nod){cur parent;parent cur-_parent;}nod parent;}return *this;}};templateclass T, class Ref, class Ptrstruct Reverse_Iterator{typedef Reverse_IteratorT,Ref,Ptr Self;typedef RBTreeNodeT node;RBTreeIteratorT,Ref,Ptr _it;Reverse_Iterator(node* root):_it(root){}//使用正向迭代器来构造反向迭代器Ref operator *(){return _it.nod-_data;}Ptr operator -(){return _it-nod;}bool operator !(const Self data){return _it.nod ! data._it.nod;}Self operator (){--_it;return *this;}Self operator --(){ _it;return *this;}};templateclass K, class T,class KeyOfTclass RBTree{public:typedef RBTreeNodeT node;typedef RBTreeIteratorT, T, T* iterator;//迭代器typedef Reverse_IteratorT, T, T* reverse_iterator;//反向迭代器public://迭代器iterator begin(){assert(_root);//返回树的最左节点node* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}reverse_iterator rbegin(){return reverse_iterator(nullptr);}reverse_iterator rend(){assert(_root);//返回树的最左节点node* cur _root;while (cur cur-_left){cur cur-_left;}return reverse_iterator(cur);}//插入bool insert(const T data){//如果根节点为空插入根节点并将颜色改为黑色if (_root nullptr){_root new node(data);_root-_col BLACK;return true;}//找到可以插入的地方node* cur _root;node* parent nullptr;KeyOfT kot;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;}elsereturn false;}//插入并连接cur new node(data);if (kot(parent-_data) kot(cur-_data))parent-_left cur;elseparent-_right cur;cur-_parent parent;//如果父节点是黑色插入的节点是红色直接返回true不需要做处理if (parent-_col BLACK) return true;//如果父节点是红色开始处理while (parent parent-_col RED){//找到祖父节点node* grandfather parent-_parent;//找到叔叔节点if (grandfather-_left parent){node* uncle grandfather-_right;//如果叔叔节点不为空且是红色if (uncle uncle-_col RED){//将叔叔和父节点变黑uncle-_col parent-_col BLACK;//将祖父节点变红grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}//叔叔节点存在且为黑或者叔叔节点不存在else{//第一种情况// g// p u// cif (cur parent-_left){//对p继续右旋RotateR(parent);//再进行变色parent-_col BLACK;grandfather-_col RED;}//第二种情况// g// p u// celse{//先左旋parentRotateL(parent);//再右旋grandfatherRotateR(grandfather);//变色grandfather-_col RED;cur-_col BLACK;}break;}}//如果parent是祖父节点的右边叔叔节点就是祖父节点的左边else{//找到叔叔节点node* uncle grandfather-_left;//如果叔叔节点存在且为红if (uncle uncle-_col RED){uncle-_col BLACK;parent-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}//如果叔叔节点不存在或存在且为黑else{//第一种情况// g// u p// cif (cur parent-_right){//首先对grandfather进行左单旋RotateL(grandfather);//变色parent-_col BLACK;grandfather-_col RED;}//第二种情况// g// u p// celse{//首先对parent进行右单旋RotateR(parent);//再对grandfather进行左单旋RotateL(grandfather);//变色cur-_col BLACK;grandfather-_col RED;}}break;}}//不论什么情况下根节点都必须是黑色的_root-_col BLACK;return true;}iterator find(const K data){node* cur _root;KeyOfT kot;while (cur){if (kot(cur-_data) data) return iterator(cur);else if (kot(cur-_data) data) cur cur-_left;else cur cur-_right;}return iterator(nullptr);}private://左单旋void RotateL(node* parent){node* SubR parent-_right;node* SubRL SubR-_left;parent-_right SubRL;if (SubRL)SubRL-_parent parent;node* pparent parent-_parent;parent-_parent SubR;SubR-_left parent;if (pparent){if (pparent-_left parent)pparent-_left SubR;elsepparent-_right SubR;SubR-_parent pparent;}else{_root SubR;SubR-_parent nullptr;}}//右单旋void RotateR(node* parent){node* SubL parent-_left;node* SubLR SubL-_right;node* pparent parent-_parent;parent-_left SubLR;SubL-_right parent;parent-_parent SubL;if (SubLR)SubLR-_parent parent;if (pparent){if (pparent-_left parent)pparent-_left SubL;elsepparent-_right SubL;SubL-_parent pparent;}else{_root SubL;SubL-_parent nullptr;}}private:node* _root nullptr;//根节点};
}set封装代码
#pragma once
#includeRBTree.hnamespace myset
{templateclass Kclass set{public:typedef rb_tree::RBTreeIteratorK, K, K* iterator;typedef rb_tree::Reverse_IteratorK, K, K* reverse_iterator;struct SetKeyOfT{K operator()(const K key){return key;}};//迭代器iterator begin(){return _rb.begin();}iterator end(){return _rb.end();}reverse_iterator rbegin(){return _rb.rbegin();}reverse_iterator rend(){return _rb.rend();}bool insert(const K data){return _rb.insert(data);}iterator find(K data){return _rb.find(data);}private:rb_tree::RBTreeK,K,SetKeyOfT _rb;};
}templateclass K,class V
class map
{struct MapKeyOfT{K operator()(const pairK, V data){return data.first;}};
private:rb_tree::RBTreeK, pairK, V, MapKeyOfT _rb;
};map封装代码
#pragma once
#includeRBTree.hnamespace mymap
{templateclass K, class Vclass map{struct MapKeyOfT{K operator()(const pairK, V data){return data.first;}};public:typedef rb_tree::RBTreeIteratorpairK, V, pairK, V, pairK, V* iterator;typedef rb_tree::Reverse_IteratorpairK, V, pairK, V, pairK, V* reverse_iterator;//迭代器iterator begin(){return _rb.begin();}iterator end(){return _rb.end();}reverse_iterator rbegin(){return _rb.rbegin();}reverse_iterator rend(){return _rb.rend();}bool insert(const pairK, V data){return _rb.insert(data);}iterator find(const K data){return _rb.find(data);}private:rb_tree::RBTreeK, pairK, V, MapKeyOfT _rb;};
}
