红黑树详解 一.红黑树介绍1.红黑树的概念红黑树是一颗二叉搜索树增加了一个储存位来表示颜色可以是红色或者黑色。通过对从根到叶子(指的是nullptr节点)的路径上每个节点颜色的约束红黑树确保了没有一条路径会超出其他路径长度的两倍因而接近平衡。2.红黑树的规则每条路径的结尾都是NIL节点(传统的叶节点而是空节点为了方便准确标识所有路径)1.红黑树节点不是黑色就是红色2.整棵树的根节点一定是黑色3.如果一个节点是红色的那么它的两个孩子必然是黑色的也就是说在红黑树的任意路径上没有连续的两个红节点4.对于任意节点从该节点到其所有NULL节点的路径上黑节点的数量相同。注意有些树上会补充NIL节点都是黑色的规则。后面讲解的细节中会忽略NIL。为什么红黑树确保了没有一条路径会超出其他路径长度的两倍1.由规则3可得最短路径(极端情况)的节点全是黑节点设其高度为bh(black height)2.为了让路径更长那么就得让路径上的红节点多一点但不允许存在连续的红节点那么路径最长时(极端情况)就是每一个黑节点接一个红节点路径长为2 * bh3.综合而言设红黑树的每条路径的长度为xbh x 2 * bh;3.红黑树的效率设红黑树的节点个数为N最短路径长为h那么有2^h - 1 N 2^(2 * h) - 1所以h约等于logN也就是说增删查改最多要走2*logN故其效率是O(logN)。相比于AVL树红黑树的表达相对于AVL树要抽象一点AVL树通过对高度差的观察控制了平衡而红黑树是通过四条规则约束间接实现了近似平衡。它们的效率是同一档次的但插入相同的数据时红黑树的旋转次数要少一点因为它对平衡的控制相对轻松而旋转消耗比较大所以实际应用中红黑树是使用更多的。二.红黑树的实现1.红黑树的结构enumColor{RED,BLACK};templateclassk,classvstructRBTreeNode{typedefRBTreeNodek,vNode;RBTreeNode(constpairk,vdatapairk,v()):_kv(data),_left(nullptr),_parent(nullptr),_right(nullptr),_col(BLACK){}pairk,v_kv;Node*_parent;Node*_left;Node*_right;Color _col;};templateclassk,classvclassRBTree{typedefRBTreeNodek,vNode;public:private:Node*_rootnullptr;};2.红黑树的插入1.插入的大概过程1.按照二叉搜索树的插入规则插入后我们只需要观察它是否符合红黑树的四大规则2.如果是空树插入那么插入的节点为根节点且颜色为black如果是非空树插入那么插入的节点必须为red因为插入black节点后会破坏规则4它是很难维护的3.非空树插入新节点后新节点为红色如果其parent节点为black则没有违反规则插入结束4.非空树插入新节点后新节点为红色如果其parent节点为red则会违反规则3需要进一步分析。重要节点说明新插入的节点为cur( c )其父节点为parent( p )祖父节点为grandparent( g )叔节点为uncle( u )。新插入节点后如果要进一步分析那么四个重要节点中会有三个节点的颜色是知道的cur和parent都是red(它们导致要进一步分析)grandparent为black只有uncle未知。以下的分析就是围绕uncle的不同来分类的。设bh为每条路径黑节点的数量。2.情况一变色uncle为红色分析p、u都是红色此时把它们变黑g变红这样解决了p、c连续红节点的问题也没有改变以g为根的两条路径的bh使得以g为根的子树符合红黑树的规则。但要注意的是g变红了如果g的parent是黑色那么插入结束如果是红色那么就要让g变成c继续向上更新。抽象图理解这里只展示了p为g的左孩子的情况插入右子树也差不多。一直更新到g为根节点或它的oarent为black为止。单变色要的条件uncle存在且为redboolinsert(constpairk,vdata){//先普通的插入if(!_root){_rootnewNode(data);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(data.firstcur-_kv.first){parentcur;curcur-_left;}elseif(data.firstcur-_kv.first){parentcur;curcur-_right;}elsereturnfalse;}curnewNode(data);cur-_colRED;cur-_parentparent;if(data.firstparent-_kv.first)parent-_leftcur;elseparent-_rightcur;//调整节点的colwhile(parentparent-_colRED)//更新到cur为根节点会自动跳出{Node*grandparentparent-_parent;if(parentgrandparent-_left)//cur插入在左子树的情况{Node*unclegrandparent-_right;if(uncleuncle-_colRED)//情况1//uncle为红的情况将parent和uncle置为黑gp置为红{parent-_colBLACK;uncle-_colBLACK;grandparent-_colRED;curgrandparent;parentcur-_parent;}}else//cur插入在右子树的情况{Node*unclegrandparent-_left;if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;grandparent-_colRED;curgrandparent;parentcur-_parent;}}}_root-_colBLACK;//保存根节点为黑returntrue;}3.情况2单旋变色当uncle为空或其_col为black时单靠变色时无法解决问题的还得加上旋转。当u不存在时cur一定时新插入的节点如图假设u不存在时cur不是新插入节点因为都更新到这一步了ABC肯定是存在黑节点的但g的右子树没有黑节点所以这种情况不存在u为空cur只能是新插入的节点。当u存在且颜色为黑时cur一定不是新插入节点假设cur为新插入节点明显可见在插入cur前以g为根的树的左右子树黑接待你个数就不同所以u为黑cur必不可能是新插入节点。抽象图分析这里分析p为g的右孩子。可见如果p是g的右孩子cur是p的右孩子只需要以g为旋点左旋最后p:red-blackg:black-red即可。单旋 变色要的条件1.uncle不存在或存在且为black2.当p为g的左/右孩子时cur为p的左/右孩子。while(parentparent-_colRED){Node*grandparentparent-_parent;if(parentgrandparent-_left){Node*unclegrandparent-_right;if(uncleuncle-_colRED)//uncle为红的情况将parent和uncle置为黑gp置为红{parent-_colBLACK;uncle-_colBLACK;grandparent-_colRED;curgrandparent;parentcur-_parent;}elseif(unclenullptr||uncle-_colBLACK){if(curparent-_left)//单旋接变色//情况2{// g// p u//cRotateR(grandparent);parent-_colBLACK;grandparent-_colRED;}break;}}else//p gp-r{Node*unclegrandparent-_left;if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;grandparent-_colRED;curgrandparent;parentcur-_parent;}elseif(unclenullptr||uncle-_colBLACK){if(curparent-_right)//单旋接变色{// g// u p// cRotateL(grandparent);parent-_colBLACK;grandparent-_colRED;}break;}}}//左右单旋voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;Node*Pparentparent-_parent;parent-_leftsubLR;parent-_parentsubL;if(subLR)subLR-_parentparent;if(parent_root)_rootsubL;subL-_rightparent;subL-_parentPparent;if(PparentPparent-_leftparent)Pparent-_leftsubL;elseif(Pparent)Pparent-_rightsubL;}voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;Node*Pparentparent-_parent;parent-_rightsubRL;parent-_parentsubR;if(subRL)subRL-_parentparent;if(parent_root)_rootsubR;subR-_leftparent;subR-_parentPparent;if(PparentPparent-_leftparent)Pparent-_leftsubR;elseif(Pparent)Pparent-_rightsubR;}4.情况3双旋变色抽象图分析p为g的右孩子。可见当p为g的右孩子cur为p的左孩子时得先以p为旋点右旋在以p为旋点左旋最后进行变色处理g:black-red;c:red-black;双旋 变色的条件1.uncle不存在/存在且为黑2.p为g的右/左孩子时c为p的左/右孩子while(parentparent-_colRED){Node*grandparentparent-_parent;if(parentgrandparent-_left){Node*unclegrandparent-_right;if(uncleuncle-_colRED)//uncle为红的情况将parent和uncle置为黑gp置为红{parent-_colBLACK;uncle-_colBLACK;grandparent-_colRED;curgrandparent;parentcur-_parent;}elseif(unclenullptr||uncle-_colBLACK){if(curparent-_left)//单旋接变色{// g// p u//cRotateR(grandparent);parent-_colBLACK;grandparent-_colRED;}else//双旋接变色{// g// p u// cRotateL(parent);RotateR(grandparent);cur-_colBLACK;grandparent-_colRED;}break;}}else//p gp-r{Node*unclegrandparent-_left;if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;grandparent-_colRED;curgrandparent;parentcur-_parent;}elseif(unclenullptr||uncle-_colBLACK){if(curparent-_right)//单旋接变色{// g// u p// cRotateL(grandparent);parent-_colBLACK;grandparent-_colRED;}else//双旋接变色{// g// u p// cRotateR(parent);RotateL(grandparent);cur-_colBLACK;grandparent-_colRED;}break;}}}5.插入的完整代码boolinsert(constpairk,vdata){//先普通的插入if(!_root){_rootnewNode(data);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(data.firstcur-_kv.first){parentcur;curcur-_left;}elseif(data.firstcur-_kv.first){parentcur;curcur-_right;}elsereturnfalse;}curnewNode(data);cur-_colRED;cur-_parentparent;if(data.firstparent-_kv.first)parent-_leftcur;elseparent-_rightcur;//调整节点的colwhile(parentparent-_colRED){Node*grandparentparent-_parent;if(parentgrandparent-_left){Node*unclegrandparent-_right;if(uncleuncle-_colRED)//uncle为红的情况将parent和uncle置为黑gp置为红{parent-_colBLACK;uncle-_colBLACK;grandparent-_colRED;curgrandparent;parentcur-_parent;}elseif(unclenullptr||uncle-_colBLACK){if(curparent-_left)//单旋接变色{// g// p u//cRotateR(grandparent);parent-_colBLACK;grandparent-_colRED;}else//双旋接变色{// g// p u// cRotateL(parent);RotateR(grandparent);cur-_colBLACK;grandparent-_colRED;}break;}}else//p gp-r{Node*unclegrandparent-_left;if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;grandparent-_colRED;curgrandparent;parentcur-_parent;}elseif(unclenullptr||uncle-_colBLACK){if(curparent-_right)//单旋接变色{// g// u p// cRotateL(grandparent);parent-_colBLACK;grandparent-_colRED;}else//双旋接变色{// g// u p// cRotateR(parent);RotateL(grandparent);cur-_colBLACK;grandparent-_colRED;}break;}}}_root-_colBLACK;//保存根节点为黑returntrue;}在插入过程中红黑树靠什么增加bh大小的单看情况1、2、3每执行一次bh的大小时不变的。在插入过程中其大小的变化只会由一种情况引起那就是在变色环节while (parent parent-_col RED)中一直更新到根节点且当g为根节点时u为red这是会按情况1执行让根变为red后跳出循环再在循环外让根变黑这时bh就增加了1。三.红黑树的检验判断一棵树是否为红黑树只要看它是否满足红黑树的四条规则就好了templateclassk,classvclassRBTree{typedefRBTreeNodek,vNode;public:boolisbalance(){if(_rootnullptr)returntrue;if(_root-_colRED)returnfalse;intway0;Node*cur_root;while(cur)//获取单条路径的bh{if(cur-_colBLACK)way;curcur-_left;}returncheck(_root,0,way);}boolcheck(Node*root,intblacknum,constintrefnum)//refnum为每条路径的黑节点个数{if(rootnullptr){if(blacknumrefnum)//代码走到着时就说明一条路走完了returntrue;else{cout有路径的黑色节点数不相等endl;returnfalse;}}if(root-_colBLACK)blacknum;else//r-c red//检查子树不太方便因为有两个而且还不一定存在所以检查parent{if(root-_parentroot-_parent-_colRED)returnfalse;}returncheck(root-_left,blacknum,refnum)check(root-_right,blacknum,refnum);}