国内做视频课程的网站有哪些,数据库型网站,太原学网站开发的学校,html网页设计规则代码个人主页点击直达#xff1a;小白不是程序媛
C系列专栏#xff1a;C干货铺
代码仓库#xff1a;Gitee 目录
前言
红黑树的概念
红黑树的性质
红黑树结点的定义
红黑树的插入操作
插入新的结点
检查规则进行改色
情况一
情况二
情况三
插入完整代码
红黑树的验…
个人主页点击直达小白不是程序媛
C系列专栏C干货铺
代码仓库Gitee 目录
前言
红黑树的概念
红黑树的性质
红黑树结点的定义
红黑树的插入操作
插入新的结点
检查规则进行改色
情况一
情况二
情况三
插入完整代码
红黑树的验证
红黑树的删除(了解)
红黑树和AVL树的比较
红黑树的应用 前言
上篇文章中我们提到AVL树通过旋转来控制防止二叉树退化成为单只树但是插入数据量过大且每个数据的紧密程度不大时插入一个数据时AVL树可能会触发多重旋转很是浪费时间。但是依然是一个有关数据BST(插入、查找、删除非常优秀的数据结构奈何那个时代人才济济10年后出现了比AVL树性能更优秀一点的红黑树Red Black Tree)。 红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路 径会比其他路径长出俩倍因而是接近平衡的。 红黑树的性质 1. 每个结点不是红色就是黑色2. 根节点是黑色的3. 如果一个节点是红色的则它的两个孩子结点是黑色的4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 这里我们可以再推出来一个性质红黑树中没有两个连续的红色结点 红黑树结点的定义
enum Colour
{RED,BLACK
};
templateclass k, class v
struct RBTreeNode
{//指向左孩子RBTreeNodek, v* _left;//指向右孩子RBTreeNodek, v* _right;//指向父亲RBTreeNodek, v* _parent;//键值对pairk, v _kv;//节点内的颜色Colour _col;//使用初始化列表初始化RBTreeNode(const pairk,vkv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv)//一定插入的是红色结点,_col(RED){}
};
为什么要将结点的默认颜色设置为红色 假设如果插入一个黑色结点相当于二叉树中的某一条路径多了一个黑色结点违反了红黑树的性质四需要对整棵树进行调整牵一发而动全身。如果插入红色结点恰好其父亲是黑色结点刚好不需要调整如果父亲是红色插入一个红色只需要对这条路径或者这条路径的这块区域进行变色就可以符合红黑树的条件。 红黑树的插入操作
红黑树是在二叉搜索树的基础上加上其平衡限制条件因此分两步按照搜索二叉树的规则插入新的结点、检查规则进行改色
插入新的结点
//首先判断根结点是否为空if (_root nullptr){//开辟根节点_root new Node(kv);//红黑树的根节点一定是黑色的_root-_col BLACK;return true;}//不为空根据左小右大找到要插入的位置Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}//找到位置开始插入结点cur new Node(kv);//插入的新增结点应该为红色cur-_col RED;//根据左小右大插入if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}
依然是基于搜索二叉树的特点左小右大进行插入 注搜索二叉树中没有相同的两个结点 检查规则进行改色
因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何 性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连 在一起的红色节点此时需要对红黑树分情况来讨论
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
情况一
cur为红p为红g为黑u存在且为红
Node* grandfather parent-_parent;//第一种情况(父亲和叔叔都存在且都为红爷爷为黑)// g(黑)// p(红) u(红)// 插入 c(红) //修改后(父亲和叔叔修改为黑色爷爷改为红色)// g(红)// p(黑) u(黑)// 插入 c(红) //当父亲不为空且父亲的颜色为红时一直向上修改//直到父亲结点为空时代表修改到了根节点//先讨论左边插入右边插入和左边插入雷同if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle uncle-_col RED){//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上变颜色cur grandfather;parent cur-_parent;}
情况二
cur为红p为红g为黑u不存在/u存在且为黑 p为g的左孩子cur为p的左孩子则进行右单旋转相反p为g的右孩子cur为p的右孩子则进行左单旋转p、g变色--p变黑g变红 else//第二种情况(爷爷为黑色父亲为红色叔叔不存在或者叔叔存在为黑色)//当叔叔不存在时候cur一定是插入的新的结点//当叔叔存在且为黑色的时候cur一定不是插入的新节点而是之前是黑色的但是通过下面子树的变色变上来成为了红色//恰好此时的叔叔是黑色的直接对这一部分进行变色//处理方式都是一样的先左(右)旋再进行变色 叔叔的颜色是不会变的{if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;// g(黑)// p(红)//插入c(红// g(黑)// p(红) u(黑)//插入c(红//旋转改色的结果// p(黑// c(红) g(红)// u(黑)}
情况三
cur为红p为红g为黑u不存在/u存在且为黑 p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转则转换成了情况2 插入完整代码 bool Insert(const pairk, v kv){//首先判断根结点是否为空if (_root nullptr){//开辟根节点_root new Node(kv);//红黑树的根节点一定是黑色的_root-_col BLACK;return true;}//不为空根据左小右大找到要插入的位置Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}//找到位置开始插入结点cur new Node(kv);//插入的新增结点应该为红色cur-_col RED;//根据左小右大插入if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}//插入介绍后开始调整颜色while (parent parent-_col RED){Node* grandfather parent-_parent;//第一种情况(父亲和叔叔都存在且都为红爷爷为黑)// g(黑)// p(红) u(红)// 插入 c(红) //修改后(父亲和叔叔修改为黑色爷爷改为红色)// g(红)// p(黑) u(黑)// 插入 c(红) //当父亲不为空且父亲的颜色为红时一直向上修改//直到父亲结点为空时代表修改到了根节点//先讨论左边插入右边插入和左边插入雷同if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle uncle-_col RED){//变色parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上变颜色cur grandfather;parent cur-_parent;}else//第二种情况(爷爷为黑色父亲为红色叔叔不存在或者叔叔存在为黑色)//当叔叔不存在时候cur一定是插入的新的结点//当叔叔存在且为黑色的时候cur一定不是插入的新节点而是之前是黑色的但是通过下面子树的变色变上来成为了红色//恰好此时的叔叔是黑色的直接对这一部分进行变色//处理方式都是一样的先左(右)旋再进行变色 叔叔的颜色是不会变的{if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;// g(黑)// p(红)//插入c(红// g(黑)// p(红) u(黑)//插入c(红//旋转改色的结果// p(黑// c(红) g(红)// u(黑)}else//第三种情况和第二种情况差不多 只不过cur不再是左孩子而是右孩子// 左旋后就是第二中情况//先进行左旋在进行右旋最后再改色{// g(黑) //左旋- g(黑)// p(红) c(红)// 插入c(红 p(红// g(黑) //左旋- g(黑)// p(红) u(黑) c(红) u(黑)// 插入c(红 p(红//右旋// c(红)// p(红) g(红)// u(黑)RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else//右边插入{Node* uncle grandfather-_left;if (uncle uncle-_col RED){// 变色//////parent-_col uncle-_colBLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p // c//RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;} 注情况三中含有的旋转和AVL树中的旋转是一样的旋转的代码在本篇文章中就不展示了大家可以在上篇文章AVL树中找到。 红黑树的验证
红黑树的检测分为两步
1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列) void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}
2. 检测其是否满足红黑树的性质 bool Check(Node* root, int blacknum,const int refVal){if (root nullptr){//走到空代表一条路走完了//用参考的黑色结点数和所求的黑色节点数进行比较if (blacknum ! refVal){cout 存在黑色结点数量不相等的路径 endl;return false;}return true;}//遇到红色结点判断其父亲结点是否为红色结点即可if (root-_col RED root-_parent-_col RED){cout 有连续的红色结点 endl;return false;}if (root-_col BLACK){blacknum;}return Check(root-_left, blacknum,refVal) Check(root-_right, blacknum,refVal);}bool IsBalance(){if (_root nullptr)return true;if (_root-_col RED)return false;int refVal 0;Node* cur _root;//先求出其中一条路中含有多少个黑色结点//一边递归一边进行往下比较while (cur){if (cur-_col BLACK){refVal;}cur cur-_left;}int blacknum 0;return Check(_root, blacknum,refVal);} 红黑树的删除(了解)
和AVL树的删除一样通过插入操作我们对红黑树的认识和了解已经差不多了想要了解删除的朋友可以可参考《算法导论》或者《STL源码剖析》 红黑树和AVL树的比较 红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log2(N))红黑树不追 求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 红黑树的应用 1. C STL库 -- map/set、mutil_map/mutil_set2. Java 库3. linux内核4. 其他一些库 今天的对数据结构中基于二叉搜索树的红黑树(RBTree)的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下个人主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是我前进的动力
