最透彻的红黑树详解（图文并茂，一文全解）

　　前言
　　刚开始接触红黑树的时候，感觉很难。其实不然，红黑树只是情况分的多了一点而已，相较于线段树，主席树等等，简单多了。对于红黑树3种插入维护4种删除维护没必要去记忆，稍作了解，对于红黑树的性质和特点，需要特别记忆。
　　本专栏知识点是通过零声教育的线上课学习，进行梳理总结写下文章，对cclinux课程感兴趣的读者，可以点击链接：CCLinux服务器开发后台架构师【零声教育】学习视频教程腾讯课堂课程介绍详细查看课程的服务。
　　注意，本文图中红黑树的叶子结点默认不画出来为什么要有红黑树二叉搜索树
　　二叉搜索树（又叫二叉排序树，BST）：对于任意一个结点，其左子树的值必定小于该结点，其右子树的值必定大于该结点。那么中序遍历的时候，就是有序的了。理论上来说，增加，删除，修改的时间复杂度都是O（log（N））。但是它存在一个致命的问题。
　　退化：向树中插入〔1，2，3，4，5，6〕，此时树退化成了一个链表，增加，删除，修改的时间复杂度退化为O（N）
　　添加图片注释，不超过140字（可选）平衡二叉搜索树
　　平衡二叉搜索树（AVLTree）：它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉搜索树。如果向树中插入〔1，2，3，4，5，6〕
　　添加图片注释，不超过140字（可选）
　　可以看到AVLTree在最坏的情况下，依然保持了绝对的平衡：左右两个子树的高度差的绝对值不超过1。那么AVLTree是如何保证平衡的呢，是通过旋转，可以看到，无论是插入还是删除元素，都要去通过旋转维护整个树的平衡。AVL查询元素：O（log（N））AVL插入元素：最多一次旋转O（1），加上查询的时间O（log（N）），插入的复杂度O（log（N））AVL删除元素：必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价比较大，删除最多需要log（N）次旋转，加上查询的时间，删除的复杂度O（2log（N））红黑树
　　我们发现，AVL树未免太严格了一些，有没有一种数据结构，能让AVL树不那么严格平衡，降低维护平衡的开销，同时又不能像BST一样退化呢？
　　当然有，就是本文所写的红黑树（rbTree）：rbTree查询元素：O（log（N））rbTree插入元素：插入最多2次旋转，加上查询的时间O（log（N）），插入的复杂度O（log（N））rbTree删除元素：删除最多需要3次旋转，加上查询的时间，删除的复杂度O（log（N））
　　虽然插入和删除元素后，需要旋转和变色（本文中统一为维护），但是这一时间复杂度可以估算为O（1）不计
　　因为rbTree的第6条性质（见下文）所以红黑树的查询效率略低与AVL的查询红黑树和AVL插入的速度差不多红黑树删除的速度比AVL快，因为AVL删除最多需要og（N）次旋转红黑树的应用场景cstlmap，set（红黑树的封装）进程调度cfs（用红黑树存储进程的集合，把调度的时间作为key，那么树的左下角时间就是最小的）内存管理（每次使用malloc的时候都会分配一块小内存出来，那么这么块就是用红黑树来存，如何表述一段内存块呢，用开始地址长度来表示，所以key开始地址，val大小）epoll中使用红黑树管理socketfdnginx中使用红黑树管理定时器，中序遍历第一个就是最小的定时器红黑树的性质（重点）每个结点是红的或者黑的根结点是黑的每个叶子结点是黑的（因为这条性质，一般用叶子结点在代码中被特殊表示）如果一个结点是红的，则它的两个儿子都是黑的（不存在相邻红色）从任一节点到叶子节点，所包含的黑色节点数目相同（即黑高度相同）最长路径长度不超过最短路径长度的2倍（2n1，一条黑红黑红一条全黑）红黑树的定义defineRED0defineBlACK1typedefintKEYTYPE；typedefstructrbtreenode｛unsignedcharcolor；颜色structrbtreenodeleft；左子树structrbtreenoderight；右子树structrbtreenodeparent；父结点KEYTYPEkey；voidvalue；｝rbtreenode；红黑树结点typedefstructrbtree｛rbtreenoderoot；根结点rbtreenodenil；通用叶子结点｝rbtree；红黑树红黑树的左旋与右旋
　　动三个方向，改6个指针。通过旋转，调整左右高度，使树达到平衡。
　　添加图片注释，不超过140字（可选）
　　左旋leftRotate（T，x）中右左中
　　降低X结点的高度，提高X结点右结点（即Y）的高度。x的右子树指向y的左子树本来指向x结点的父指针，改成指向yy的左子树指向x结点
　　添加图片注释，不超过140字（可选）
　　右旋rightRotate（T，y）中左中右
　　降低Y结点的高度，提高Y结点左结点（即X）的高度。y的左子树指向x的右子树本来指向y结点的父指针，改成指向xx的右子树指向y结点
　　添加图片注释，不超过140字（可选）左旋leftRotate（T，x）中右左中降低X结点的高度，提高X结点右结点（即Y）的高度。voidleftrotate（rbtreeT，rbtreenodex）｛rbtreenodeyxright；1xrightyleft；x的右子树指向y的左子树if（yleft！Tnil）｛yleftparentx；y的左子树的父节点指向x｝2yparentxparent；y的父结点指向x的父结点if（xparentTnil）｛如果x是根结点Trooty；｝elseif（xxparentleft）｛xparentlefty；本来指向x结点的父指针，改成指向y｝else｛xparentrighty；｝3yleftx；y的左子树指向x结点xparenty；x的父节点指向y｝右旋copy左旋的代码left改成right，right改成leftx改成y，y改成xvoidrightrotate（rbtreeT，rbtreenodey）｛rbtreenodexyleft；1yleftxright；if（xright！Tnil）｛xrightparenty；｝2xparentyparent；if（yparentTnil）｛Trootx；｝elseif（yyparentright）｛yparentrightx；｝else｛yparentleftx；｝3xrighty；yparentx；｝红黑树插入结点与插入维护红黑树的三种情况插入结点
　　在插入结点时，我们始终认为插入这个结点之前，原来的红黑树是满足红黑树性质的，那么插入的位置容易找，就是不断的对比key，最终找到位置，那么新增的结点是什么颜色呢？我们通过性质发现：如果新结点是黑色，违背了第5条性质如果新结点是红色，可能违背第4条性质
　　而第四条性质，我们可以通过旋转与上色的方式修复，所以在我们插入结点的时候，我们始终认为新结点是红色因为传入的key可能是字符，可能是整形，所以要提取出来这里可以看出，其实可以封装成一个模板intkeycompare（KEYTYPEa，KEYTYPEb）｛这里假设是intif（ab）｛return1；｝elseif（ab）｛return1；｝else｛return0；｝｝voidrbtreeinsert（rbtreeT，rbtreenodez）｛找位置rbtreenodexTroot；rbtreenodeyTnil；y是x的父节点while（x！Tnil）｛二分找位置yx；if（keycompare（zkey，xkey）0）｛xxleft；｝elseif（keycompare（zkey，xkey）0）｛xxright；｝else｛如果key相等，看自己的业务情景重复插入可以不修改直接退出，可以修改valreturn；｝｝插入zparenty；if（yTnil）｛Trootz；｝elseif（keycompare（zkey，ykey）0）｛yleftz；｝else｛yrightz；｝zleftTnil；zrightTnil；zcolorRED；维护红黑树rbtreeinsertfixup（T，z）；｝插入结点后维护红黑树
　　我们知道新增结点是红色，如果新结点是父节点也是红色，那么就需要维护红黑树了。
　　如果父结点是爷结点是左子树，可以归纳出来三种情况。同理如果父结点是爷结点是右子树，我们也可以归纳出来三种情况。但是这三种情况的差异就是旋转方向的区别而已。一共是6种情况，但是归纳出来其实是3种，读者不要搞错了。
　　在下面的图中：z表示新增结点，y表示叔结点父结点是爷结点是左子树1。叔结点是红色的将叔结点和父结点变黑，爷结点变红将当前结点变成爷结点（因为爷结点是红，爷结点的父节点也可能是红，所以要递归维护）
　　添加图片注释，不超过140字（可选）2。叔结点是黑色的且新结点是左子树将父结点变成黑色，爷结点变成红色以爷结点为中心右旋
　　添加图片注释，不超过140字（可选）3。叔结点是黑色的且新结点是右子树以父结点为中心左旋将父结点变黑色，爷结点变红色以爷结点为中心右旋
　　添加图片注释，不超过140字（可选）父结点是爷结点是右子树1。叔结点是红色的将叔结点和父结点变黑，爷结点变红将当前结点变成爷结点（因为爷结点是红，爷结点的父节点也可能是红，所以要递归维护）
　　添加图片注释，不超过140字（可选）2。叔结点是黑色的且新结点是左子树以父结点为中心右旋将父结点变黑色，爷结点变红色以爷结点为中心左旋
　　添加图片注释，不超过140字（可选）3。叔结点是黑色的且新结点是右子树将父结点变成黑色，爷结点变成红色以爷结点为中心左旋
　　添加图片注释，不超过140字（可选）维护代码修复第4条性质voidrbtreeinsertfixup（rbtreeT，rbtreenodez）｛while（zparentcolorRED）｛父结点是红色的，需要调整if（zparentzparentparentleft）｛如果父结点是爷结点是左子树rbtreenodeyzparentparentright；叔结点if（ycolorRED）｛叔结点是红色的先变色，叔，父变黑zparentcolorBLACK；ycolorBLACK；爷结点变红zparentparentcolorRED；下面的调整完了，调整上面zzparentparent；｝else｛叔父结点是黑色if（zzparentright）｛新节点是在右边zzparent；rbtreeleftrotate（T，z）；｝zparentcolorBLACK；zparentparentcolorRED；rbtreerightrotate（T，zparentparent）；｝｝else｛如果父结点是爷结点是右子树rbtreenodeyzparentparentleft；叔父结点if（ycolorRED）｛叔父结点是红色的先变色，叔，父变黑zparentcolorBLACK；ycolorBLACK；爷结点变红zparentparentcolorRED；下面的调整完了，调整上面zzparentparent；｝else｛叔父结点是黑色if（zzparentleft）｛新节点是在左边zzparent；rbtreerightrotate（T，z）；｝zparentcolorBLACK；zparentparentcolorRED；rbtreeleftrotate（T，zparentparent）；｝｝｝最后别忘了根节点始终是黑色TrootcolorBLACK；｝红黑树删除结点与删除维护红黑树的四种情况删除结点
　　我们定义：覆盖结点：z（被指定删除的结点，实际上被覆盖）删除结点：y（实际上被删除的结点，一般是后继结点）轴心结点：x（维护红黑树的结点）
　　红黑树删除结点根据改结点的左右子树分为三种情况：没有左右子树有且仅有一个子树左右子树都有
　　对不同情况的处理：情况1：直接删除该结点情况2：将该结点的唯一子树挂到父结点上，然后删除该结点情况3：找一个删除结点y（后继结点）覆盖指定结点z，然后删除删除结点y，对于这个删除结点y来说，它的情况一定是情况1或情况2删除代码rbtreenoderbtreemini（rbtreeT，rbtreenodex）｛while（xleft！Tnil）｛xxleft；｝returnx；｝找后继结点rbtreenoderbtreesuccessor（rbtreeT，rbtreenodex）｛rbtreenodeyxparent；右子树不为空，则找右子树中最左的元素if（xright！Tnil）｛returnrbtreemini（T，xright）；｝找到结点第一个父结点while（（y！Tnil）（xyright））｛xy；yyparent；｝returny；｝覆盖结点z删除结点y轴心结点xrbtreenoderbtreedelete（rbtreeT，rbtreenodez）｛rbtreenodeyTnil；rbtreenodexTnil；if（（zleftTnil）（zrightTnil））｛yz；如果没有孩子或只有一个｝else｛如果有两个子树则找后继yrbtreesuccessor（T，z）；｝一般x是y的右子树，找到轴心结点if（yleft！Tnil）｛xyleft；｝elseif（yright！Tnil）｛xyright；｝将该结点的唯一子树挂到父结点上，然后删除该结点xparentyparent；if（yparentTnil）｛根结点Trootx；｝elseif（yyparentleft）｛yparentleftx；｝else｛yparentrightx；｝进行覆盖操作if（y！z）｛zkeyykey；zvalueyvalue；｝黑色才需要调整if（ycolorBLACK）｛rbtreedeletefixup（T，x）；｝returny；｝删除结点后维护红黑树
　　想一想，删除一个结点，该结点是什么颜色的时候才需要维护红黑树呢？如果是红色，没有违反任何性质。所以如果是红色直接删除即可，无需维护如果是黑色，黑色被删除，那么必定违反第5条性质，破坏了黑高，所以我们需要针对这一情况进行维护
　　如果当前结点是父结点的左子树的情况，可以归纳出来四种情况。同理如果当前结点是父结点的右子树，我们也可以归纳出来四种情况。但是这四种情况的差异就是旋转方向的区别而已（镜像的）。一共是8种情况，但是归纳出来其实是4种，读者不要搞错了。当前结点是父结点的左子树的情况1。当前结点的兄弟结点是红色的兄弟节点变成黑色父节点变成红色父节点做左旋将兄弟结点调整为父节点的右子树
　　添加图片注释，不超过140字（可选）2。当前结点的兄弟结点是黑色的，而且兄弟结点的两个孩子结点都是黑色的兄弟节点变成红色轴心结点变为父节点
　　添加图片注释，不超过140字（可选）3。当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是红色的，右孩子是黑色的将左孩子涂黑将兄弟节点变红对兄弟节点右旋将兄弟结点调整为父节点的右子树现在情况3就会变成情况4，接着做情况4的步骤
　　添加图片注释，不超过140字（可选）4。当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是黑色的，右孩子是红色的将兄弟节点换成父节点的颜色把父节点和兄弟节点的右孩子涂黑对父节点做左旋设置x指针，指向根节点
　　添加图片注释，不超过140字（可选）当前结点是父结点的右子树的情况1。当前结点的兄弟结点是红色的兄弟节点变成黑色父节点变成红色父节点做右旋将兄弟结点调整为父节点的左子树2。当前结点的兄弟结点是黑色的，而且兄弟结点的两个孩子结点都是黑色的兄弟节点变成红色轴心结点变为父节点3。当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是黑色的，右孩子是红色的将右孩子变黑将兄弟节点变红对兄弟结点左旋将兄弟结点调整为父节点的左子树现在情况3就会变成情况4，接着做情况4的步骤4。当前结点的兄弟结点是黑色的，而且兄弟结点的左孩子是红色的，右孩子是黑色的将兄弟节点换成父节点的颜色把父节点和兄弟节点的左孩子变黑对父节点做右旋将轴心结点调整为根结点维护代码voidrbtreedeletefixup（rbtreeT，rbtreenodex）｛如果x是红色，变成黑色，如果x是黑色，需要调整while（（x！Troot）（xcolorBLACK））｛当前结点是父结点的左子树if（xxparentleft）｛兄弟节点rbtreenodewxparentright；情况1：兄弟节点为红色if（wcolorRED）｛兄弟节点变成黑色wcolorBLACK；父节点变成红色xparentcolorRED；父节点做左旋rbtreeleftrotate（T，xparent）；将兄弟结点调整为父节点的右子树wxparentright；｝情况2：兄弟节点是黑色的，且兄弟的左孩子和右孩子都是黑色if（（wleftcolorBLACK）（wrightcolorBLACK））｛兄弟节点变成红色wcolorRED；轴心结点变为父节点xxparent；｝else｛情况3：x的兄弟节点是黑色的，兄弟的左孩子是红色，右孩子是黑色if（wrightcolorBLACK）｛将左孩子涂黑wleftcolorBLACK；将兄弟节点变红wcolorRED；对兄弟节点右旋rbtreerightrotate（T，w）；重新设置x的兄弟节点wxparentright；｝情况4：x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的将兄弟节点换成父节点的颜色wcolorxparentcolor；把父节点和兄弟节点的右孩子涂黑xparentcolorBLACK；wrightcolorBLACK；对父节点做左旋rbtreeleftrotate（T，xparent）；设置x指针，指向根节点xTroot；｝｝else｛当前结点是父结点的右子树兄弟节点rbtreenodewxparentleft；情况1：兄弟结点为红色if（wcolorRED）｛兄弟节点变成黑色wcolorBLACK；父节点变成红色xparentcolorRED；父节点做右旋rbtreerightrotate（T，xparent）；将兄弟结点调整为父节点的左子树wxparentleft；｝情况2：兄弟节点是黑色的，且兄弟的左孩子和右孩子都是黑色if（（wleftcolorBLACK）（wrightcolorBLACK））｛兄弟节点变成红色wcolorRED；轴心结点变为父节点xxparent；｝else｛情况3：x的兄弟结点是黑色的，兄弟的左孩子是黑色，右孩子是红色if（wleftcolorBLACK）｛将右孩子变黑wrightcolorBLACK；将兄弟节点变红wcolorRED；对兄弟结点左旋rbtreeleftrotate（T，w）；将兄弟结点调整为父节点的左子树wxparentleft；｝情况4：x的兄弟结点是黑色的，兄弟的左孩子是红色，右孩子是黑色将兄弟节点换成父节点的颜色wcolorxparentcolor；把父节点和兄弟节点的左孩子变黑xparentcolorBLACK；wleftcolorBLACK；对父节点做右旋rbtreerightrotate（T，xparent）；将轴心结点调整为根结点xTroot；｝｝｝继承节点变为黑色，为了弥补失去的黑高xcolorBLACK；｝红黑树的遍历、查询、测试rbtreenoderbtreesearch（rbtreeT，KEYTYPEkey）｛rbtreenodenodeTroot；while（node！Tnil）｛if（keynodekey）｛nodenodeleft；｝elseif（keynodekey）｛nodenoderight；｝else｛returnnode；｝｝returnTnil；｝voidrbtreetraversal（rbtreeT，rbtreenodenode）｛if（node！Tnil）｛rbtreetraversal（T，nodeleft）；printf（key：d，color：d，nodekey，nodecolor）；rbtreetraversal（T，noderight）；｝｝intmain（）｛intkeyArray〔20〕｛24，25，13，35，23，26，67，47，38，98，20，19，17，49，12，21，9，18，14，15｝；rbtreeT（rbtree）malloc（sizeof（rbtree））；if（TNULL）｛printf（mallocfailed）；return1；｝Tnil（rbtreenode）malloc（sizeof（rbtreenode））；TnilcolorBLACK；TrootTnil；rbtreenodenodeTnil；inti0；for（i0；i20；i）｛node（rbtreenode）malloc（sizeof（rbtreenode））；nodekeykeyArray〔i〕；nodevalueNULL；rbtreeinsert（T，node）；｝rbtreetraversal（T，Troot）；printf（）；for（i0；i20；i）｛rbtreenodenoderbtreesearch（T，keyArray〔i〕）；rbtreenodecurrbtreedelete（T，node）；free（cur）；rbtreetraversal（T，Troot）；printf（）；｝｝
　　原文链接：随处可见的红黑树详解cheems的博客CSDN博客