[C++] 深入理解红黑树与代码实现

1. 红黑树的概念红黑树是一颗二叉搜索树具备二叉搜索树的所有性质。可以跳转至这篇文章了解二叉搜索树C深入理解二叉搜索树与代码实现红黑树在二叉搜索树的基础上还具有以下性质只有红色和黑色两种节点根节点为黑色任何一条路径都不会出现连续的红色节点任何一条路径上的黑色节点数量相同红黑树在二叉搜索树的基础上通过控制颜色来控制平衡最长路径不超过最短路径的两倍。为什么呢根据性质4极端场景下的最短路径全是黑色节点假设最短路径是bblack由规则23可知极端场景下的最长路径为一黑一红节点间隔组成那么最长路径为2 * b但并不是每一棵红黑树的最长 / 最短路径都符合以上的极端情况因此假设任意一条路径长度为x那么b x 2 * b。2. 时间复杂度分析假设N是红黑树中节点的数量h是最短路径的长度那么可以得出2^h -1 N 2^(2*h) -1的结论由此可以推断出 h 近似为logN。也就是说红黑树增删查改的最坏情况也就是走最长路径即2 * logN时间复杂度的量级还是O(logN)。红黑树和AVL树都是通过不同的方式使二叉搜索树尽量平衡因此他们的效率位于同一档次且红黑树对平衡的控制没那么严格因此旋转次数更少C的STL中也更多使用红黑树作为底层容器。3. 红黑树的实现3.1 红黑树的结构节点红黑树仅仅在平衡规则部分与AVL树不同因此红黑树的节点中没有平衡因子而是用颜色作为枚举值来表示。剩余成员和AVL树相同父节点指针左右孩子指针key / value。树红黑树的成员为根节点。以下是以key / value为例的红黑树框架// 枚举值表示颜色enumColour{RED,BLACK};// 这里我们默认按key/value结构实现templateclassK,classVstructRBTreeNode{// 这里更新控制平衡也要加入parent指针pairK,V_kv;RBTreeNodeK,V*_left;RBTreeNodeK,V*_right;RBTreeNodeK,V*_parent;Colour _col;RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};templateclassK,classVclassRBTree{private:Node*_rootnullptr;typedefRBTreeNodeK,VNode;public://...};3.2 红黑树的插入红黑树的插入逻辑和二叉搜索树相同即找到一个合适的空位置插入。插入后仅需观察颜色是否符合规则即可若为空树插入的节点为根节点颜色设置为黑插入结束。不为空树插入的节点颜色设置为红如果父节点为黑则符合条件插入结束若父节点为红则不满足规则3不能出现连续的红色节点需要向上调整颜色 / 旋转。对于是否需要旋转主要观察的是uncle节点也就是父节点的兄弟节点如图插入的是x节点parent节点为6uncle节点为15grandparent节点为103.2.1 情况一仅变色当uncle节点存在且为红色时仅需变色即可如果grandparent节点的父节点仍然是红色则一直向上更新如果父节点为黑色则停止更新最坏情况是一路向上更新到了根节点此时需要将根节点变为黑色停止更新。3.2.2 情况二旋转 变色当uncle节点不存在或者为黑色时需要旋转 变色。我们可以通过uncle节点的状态来推断cur节点的性质如果uncle节点不存在则cur节点一定是新增节点如果uncle节点存在且为黑则cur节点一定不是新增节点。假设法证明如下旋转究竟需要单旋还是双旋判断条件和AVL树相同。即看curparentgrandparent节点是否在一条直线上如果在则单旋否则双旋。变色要解决连续红色节点的问题同时还要保证各条路径上的黑色节点数量相同接下来我们具体情况具体分析。⭕左单旋当gpc节点呈一条直线且pc均为右孩子节点时需要进行左单旋。旋转后pc节点均为红色为了避免出现连续红色节点需要将p节点变为黑色原先左边路径有两个黑色节点为了保持一致需要更改g的颜色为红色。由于之前证明了c节点一定不是新增节点因此旋转前每条路径的黑色节点个数是符合规则4任意路径黑色节点数量相同的只需要保持原先路径的黑色节点数量不变即可不需要改变c节点的颜色。⭕右单旋右单旋的场景就是左单旋的水平翻转变色规则相同⭕左右双旋:当p为g的右孩子节点c为p的左孩子节点时需要进行左右双旋。旋转后pc节点均为红色为了保证没有连续的红色节点并且路径上黑色节点数量一致需要将c节点变为黑色g节点变为红色。⭕右左双旋右左双旋的场景就是左右双旋的水平翻转变色规则相同红黑树插入代码实现boolInsert(constpairK,Vkv){//根if(!_root){_rootnewNode(kv);_root-_colBLACK;returntrue;}//非根Node*cur_root;Node*parentnullptr;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;//p在g左if(parentgrandfather-_left){Node*unclegrandfather-_right;//u存在且为红-变色继续向上处理if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;grandfather-_colRED;curgrandfather;parentgrandfather-_parent;}else//u不存在或为黑{if(curparent-_left){RotateR(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}//p在g右else{Node*unclegrandfather-_left;//仅变色if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;grandfather-_colRED;curparent;parentgrandfather;}else//旋转 变色{if(curparent-_right){RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;}else{RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;}break;}}}//一律设置为黑_root-_colBLACK;returntrue;}//右旋voidRotateR(Node*pParent){Node*parentpParent;Node*subLparent-_left;Node*subLRsubL-_right;//1.parent和subLRparent-_leftsubLR;if(subLR){subLR-_parentparent;}Node*parentParentparent-_parent;//2.parent和subLparent-_parentsubL;subL-_rightparent;//3.subL和parentParentif(parentParentnullptr){_rootsubL;subL-_parentnullptr;}else{if(parentParent-_leftparent){parentParent-_leftsubL;}else{parentParent-_rightsubL;}subL-_parentparentParent;}}//左旋voidRotateL(Node*pParent){Node*parentpParent;Node*subRparent-_right;Node*subRLsubR-_left;//1.parent和subRLparent-_rightsubRL;if(subRL){subRL-_parentparent;}//2.parent和subRNode*parentParentparent-_parent;parent-_parentsubR;subR-_leftparent;//3.subR和parentParentif(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentParent-_leftparent){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}}在写双旋代码的过程中可以按照以下顺序实现思路更清晰parent节点和subRL / subLR节点parent节点和subR / subL节点subR / subL节点和parentParent节点3.3 红黑树的查找按照二叉搜索树的规则查找即可时间复杂度为O(logN)//查找Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_left;}elseif(cur-_kv.firstkey){curcur-_right;}else{returncur;}}returnnullptr;}4. 红黑树的验证红黑树的验证主要根据四点规则开展满足了规则就能保证最长路径不超过最短路径的两倍规则1无需多言2可以直接检查根规则3前序遍历检查遇到红⾊结点查孩⼦会涉及分类讨论和是否存在的问题比较麻烦因此采用检查⽗节点的颜⾊的方式是否合法规则4可以通过前序遍历并用形参记录根到当前结点的blackNum(⿊⾊结点数量)前序遍历遇到⿊⾊结点就blackNum⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值依次⽐较即可。代码验证boolCheck(Node*root,intblackNum,constintrefNum){if(rootnullptr){// 前序遍历走到空时意味着一条路径走完了//cout blackNum endl;if(refNum!blackNum){cout存在黑色结点的数量不相等的路径endl;returnfalse;}returntrue;}// 检查孩子不太方便因为孩子有两个且不一定存在反过来检查父亲就方便多了if(root-_colREDroot-_parent-_colRED){coutroot-_kv.first存在连续的红色结点endl;returnfalse;}if(root-_colBLACK){blackNum;}returnCheck(root-_left,blackNum,refNum)Check(root-_right,blackNum,refNum);}boolIsBalance(){if(_rootnullptr)returntrue;if(_root-_colRED)returnfalse;// 参考值intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}returnCheck(_root,0,refNum);}// 本期内容就到这里啦如果对你有帮助请三连支持我是青云我们下期见^_~