个人主页ꪔ小林Y✨个人专栏《C小白闯关日记》《C语言小白闯关日记》《数据结构入门——从原理到实战》,《拾光Linux》《网络安全》代码信条每一行代码都是成长的脚印每一次调试成功都是对坚持的回应目录红黑树1.红黑树定义及规则2.红黑树的实现1红黑树的基本结构2红黑树的插入红黑树插入代码实现红黑树1.红黑树定义及规则定义红黑树是一颗二叉搜索树他的每个结点增加一个存储位来表示结点的颜色红/黑。通过对任何一条从根到叶子的路径上各个节点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而接近平衡。规则1每个节点不是红色就是黑色2根节点是黑色注意红黑树可以是空树3如果一个节点是红色则他的两个孩子节点必须是黑色也就是说任意一条路径不会有连续的红色节点4对于任意一个节点从该节点到其所有NULL节点的简单路径上均包含相同数量的黑色节点红黑树增删查改时间复杂度O(logN)2.红黑树的实现1红黑树的基本结构//枚举表示颜色enumColour{RED,BLACK};//key/value实现templateclassK,classVstructRETreeNode{pairK,V_kv;RETreeNodeK,V*_left;RETreeNodeK,V*_right;RETreeNodeK,V*_parent;Colour _col;RETreeNode(constpatrK,vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};templateclassK,classVclassRBTree{typedefRBTreeNodeK,VNode;public:private:Node*_rootnulptr;};2红黑树的插入插入一个值按照二叉搜索树的规则进行插入须符合以下规则空树插入新增节点为黑色非空树插入新增节点必须为红色。否则破坏规则4。非空树插入后新增为红如果父亲节点是黑色没有违反任何规则插入结束。非空树插入后新增为红如果父亲节点是红色违反规则3进一步分析 (假设新增节点c(cur),父亲节点p爷爷节点g叔叔节点u)3.1情况一变色叔叔存在且为红即c为红p为红u存在且为红则将p和u变黑g变红。把g当做新的c继续向上处理。若g就是根则再变为黑3.2情况二单旋变色叔叔不存在或者存在且为黑c为红p为红g为黑u不存在或者存在且为黑。u不存在则c一定是新增节点u存在且为黑则c一定不是新增c之前是黑色的是在c的子树中插入符合情况一变色将c从黑色变成红色更新上来的。这里单纯的变色无法解决问题需要变色旋转如果p是g的左c是p的左那么先以g为旋转点进行右单旋再把p变黑g变红即可。p变成课这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则。如果p是g的右c是p的右那么先以g为旋转点进行左单旋再把p变黑g变红即可。p变成课这颗树新的根。例3.3情况三双旋变色如果p是g的左c是p的右那么先以p为旋转点进行左单旋再以g为旋转点进行右单旋再把c变黑g变红即可。c变成课这颗树新的根。如果p是g的右c是p的左那么先以p为旋转点进行右单旋再以g为旋转点进行左单旋再把c变黑g变红即可。c变成课这颗树新的根。例红黑树插入代码实现boolInsert(constpairK,Vkv){//空树插入黑色节点if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}//新增红色curnewNode(kv);cur-_colRED;if(parent-_kv.firstkv.first){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;//父亲存在且为红while(parentparent-_colRED){Node*grandfatherparent-_parent;if(grandfather-_leftparent){// g// p u//cNode*unclegrandfather-_right;//情况一叔叔存在且为红,变色即可if(uncleuncle-_colRED){//变色继续往上处理parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else// 叔叔不存在或者叔叔存在且为黑{// g// p u//c// 情况二单旋变色if(curparent-_left){RotateR(geandfather);parent-_colBLACK;grandfather-_colRED;}else{// g// p u// c//情况三双旋变色RotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}else{// g// u pNode*unclegrandfather-_left;//情况一叔叔存在且为红,变色即可if(uncleuncle-_colRED){//变色继续往上处理parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else// 叔叔不存在或者叔叔存在且为黑{// g// u p// c// 情况二单旋变色if(curparent-_right){RotateL(geandfather);parent-_colBLACK;grandfather-_colRED;}else{// g// u p// c//情况三双旋变色RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}//不存在父亲_root-_colBLACK;returntrue;}到这儿本期C——【红黑树】定义及其实现的内容就结束了。如果文中有表述不准的地方或是你有更清晰的理解思路强烈欢迎在评论区留言交流——技术路上多碰撞才能更快进步觉得内容对你有帮助的话别忘了点赞❤️➕收藏方便后续回顾复习想跟着一起系统学习数据结构的朋友也可以点击关注下一期我们会聚焦更进一步的学习。不见不散✌️
个人主页ꪔ小林Y✨个人专栏《C小白闯关日记》《C语言小白闯关日记》《数据结构入门——从原理到实战》,《拾光Linux》《网络安全》代码信条每一行代码都是成长的脚印每一次调试成功都是对坚持的回应目录红黑树1.红黑树定义及规则2.红黑树的实现1红黑树的基本结构2红黑树的插入红黑树插入代码实现红黑树1.红黑树定义及规则定义红黑树是一颗二叉搜索树他的每个结点增加一个存储位来表示结点的颜色红/黑。通过对任何一条从根到叶子的路径上各个节点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而接近平衡。规则1每个节点不是红色就是黑色2根节点是黑色注意红黑树可以是空树3如果一个节点是红色则他的两个孩子节点必须是黑色也就是说任意一条路径不会有连续的红色节点4对于任意一个节点从该节点到其所有NULL节点的简单路径上均包含相同数量的黑色节点红黑树增删查改时间复杂度O(logN)2.红黑树的实现1红黑树的基本结构//枚举表示颜色enumColour{RED,BLACK};//key/value实现templateclassK,classVstructRETreeNode{pairK,V_kv;RETreeNodeK,V*_left;RETreeNodeK,V*_right;RETreeNodeK,V*_parent;Colour _col;RETreeNode(constpatrK,vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};templateclassK,classVclassRBTree{typedefRBTreeNodeK,VNode;public:private:Node*_rootnulptr;};2红黑树的插入插入一个值按照二叉搜索树的规则进行插入须符合以下规则空树插入新增节点为黑色非空树插入新增节点必须为红色。否则破坏规则4。非空树插入后新增为红如果父亲节点是黑色没有违反任何规则插入结束。非空树插入后新增为红如果父亲节点是红色违反规则3进一步分析 (假设新增节点c(cur),父亲节点p爷爷节点g叔叔节点u)3.1情况一变色叔叔存在且为红即c为红p为红u存在且为红则将p和u变黑g变红。把g当做新的c继续向上处理。若g就是根则再变为黑3.2情况二单旋变色叔叔不存在或者存在且为黑c为红p为红g为黑u不存在或者存在且为黑。u不存在则c一定是新增节点u存在且为黑则c一定不是新增c之前是黑色的是在c的子树中插入符合情况一变色将c从黑色变成红色更新上来的。这里单纯的变色无法解决问题需要变色旋转如果p是g的左c是p的左那么先以g为旋转点进行右单旋再把p变黑g变红即可。p变成课这颗树新的根这样子树黑色结点的数量不变没有连续的红色结点了且不需要往上更新因为c的父亲是黑色还是红色或者空都不违反规则。如果p是g的右c是p的右那么先以g为旋转点进行左单旋再把p变黑g变红即可。p变成课这颗树新的根。例3.3情况三双旋变色如果p是g的左c是p的右那么先以p为旋转点进行左单旋再以g为旋转点进行右单旋再把c变黑g变红即可。c变成课这颗树新的根。如果p是g的右c是p的左那么先以p为旋转点进行右单旋再以g为旋转点进行左单旋再把c变黑g变红即可。c变成课这颗树新的根。例红黑树插入代码实现boolInsert(constpairK,Vkv){//空树插入黑色节点if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}//新增红色curnewNode(kv);cur-_colRED;if(parent-_kv.firstkv.first){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;//父亲存在且为红while(parentparent-_colRED){Node*grandfatherparent-_parent;if(grandfather-_leftparent){// g// p u//cNode*unclegrandfather-_right;//情况一叔叔存在且为红,变色即可if(uncleuncle-_colRED){//变色继续往上处理parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else// 叔叔不存在或者叔叔存在且为黑{// g// p u//c// 情况二单旋变色if(curparent-_left){RotateR(geandfather);parent-_colBLACK;grandfather-_colRED;}else{// g// p u// c//情况三双旋变色RotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}else{// g// u pNode*unclegrandfather-_left;//情况一叔叔存在且为红,变色即可if(uncleuncle-_colRED){//变色继续往上处理parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else// 叔叔不存在或者叔叔存在且为黑{// g// u p// c// 情况二单旋变色if(curparent-_right){RotateL(geandfather);parent-_colBLACK;grandfather-_colRED;}else{// g// u p// c//情况三双旋变色RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}//不存在父亲_root-_colBLACK;returntrue;}到这儿本期C——【红黑树】定义及其实现的内容就结束了。如果文中有表述不准的地方或是你有更清晰的理解思路强烈欢迎在评论区留言交流——技术路上多碰撞才能更快进步觉得内容对你有帮助的话别忘了点赞❤️➕收藏方便后续回顾复习想跟着一起系统学习数据结构的朋友也可以点击关注下一期我们会聚焦更进一步的学习。不见不散✌️
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
