目录前言Part1. 前置知识Part2. 删除逻辑分析一开始删除的情况非向上调整Part2.1. 删除Part2.2. 调整Part3. 删除的四大情况删除节点为黑替代节点为nullptrPart3.1. w为红Part3.2. w为黑左右子均为黑Part3.3. w为黑右子为红左子不论Part3.4. w为黑左子为红右子为黑Part3.5. w在p的左边Part4. 删除代码实现Part5. 结语前言之前我们讲了关于红黑树的插入判断操作。接下来我们来看看红黑树最复杂的接口--删除吧。lets go!!!!!!!!!Part1. 前置知识上篇文章【知识讲解】 红黑树的基本接口讲解插入、判断等等-CSDN博客上篇文章我们讲述了两个推论和具体情况的处理具体怎么得到的可以看上篇文章这里简要的给出结论。这里给出了再调整过程中的最小调整单元这里的c可以理解为具体出问题的节点插入中的p由于p为红色导致连红p为c的父亲节点w为c的兄弟节点。我们假设h(x)为从x节点到nullptr路径上的黑色节点数目。则我们有推论1对于一个节点x它的两个子树的h一定相同。例h(c)h(w)推论2调整前h(p)调整后为h(p2)。则若h(p)h(p2)且p的颜色不变满足推论1的情况下就不用向上调整。具体情况处理我们要穷尽所有可能出现的情况且要尽量简要的方式达到正确的效果于是我们穷举与出问题的节点(c)最密切的节点(w)的所有情况这样就一定可以满足上面的要求。Part2. 删除逻辑分析一开始删除的情况非向上调整Part2.1. 删除删除操作主要分为两个阶段删除和调整。删除阶段就是二叉搜索树的删除逻辑具体可以看【知识讲解】 二叉搜索树的相关知识与实现-CSDN博客我们设待删除的节点为d根据二叉搜索树删除的逻辑我们知道删除一共就只有三个情况即d有右子无左子d有左子无右子d为叶子节点。d有两个子的情况可以通过转化法转化为上面的三种情况之一Part2.2. 调整那删除我们知道了我们怎么调整呢首先根据红黑树的规则每个节点非黑即红所以我们来分类讨论一下当删除的节点为红色时我们删除它不会违反任何规则直接就可以删除。当删除的节点为黑色时我们删除它会导致这个路径的黑高(h)减一导致其父亲结点的左右子树的h不相同违反红黑树黑高相同的规则要调整。所以我们调整的第一个大逻辑就有了当我们删除的结点的颜色为红色我们不用进行任何调整直接就可以结束关键在于当我们删除的是黑节点怎么办首先在删除后一定会有一个代替他的节点nullptr也算根据上面删除的逻辑我们可以得出这个代替节点一定不会是黑色的为啥因为d不可能同时存在左右两个子所以要是一边有黑节点那另一边是无法平衡的所以代替节点一定不为黑。其次当代替节点为红的时候我们只要把这个红色染黑调整就结束了相当于红色变为黑色把那个删除的黑色给补回来了。所以我们调整就又多了一种情况就是当删除后其代替节点为红时将其染黑结束调整。综上我们得到了两种情况就是当删除节点为红和代替节点为红接下来我们来分析一下其他的情况。现在代替节点不为红、黑。所以只能为nullptr(由于nullptr也为黑故前面的黑应该是存在且为黑)。现在比较好解决的情况已经排除了我们来看复杂的情况就是替代节点为nullptr。首先先明确删除后问题出在哪出在删除的地方少一个黑节点导致违反了红黑树的规则所以我们的目标就是把这个给补回来而我们肯定不能无中生有一个黑节点所以我们从哪补充自然是红节点染色。所以我们的思路就有了我们要红节点通过染色的方式补充失去的黑节点。而这个红节点在哪会有呢w?不会就算w是红节点我们也无法通过旋转、染色的方式调整好所以补充的节点只能出在w的子节点中这样我们才能通过旋转的方式将这个转嫁到失去黑节点的地方所以我们在细分情况的时候要根据w的子节点来。其次我们来分析一下h(w)为多少为一。为什么首先我们一开始删除的节点为黑为红就直接结束了其次替代节点为nullptr所以h(w)为一因为一开始h(c)这边就为一而他们在删除前为红黑树依据推论1右边也为一。综上我们来总结一下情况吧。1 删除节点为红直接删除结束。2 删除节点为黑替代节点为红删除后将其染为红色结束。3 删除节点为黑替代节点为nullptr由此引申出h(w)为固定的一穷举w的孩子的情况调整。逻辑理顺了我们来看看具体的情况吧。Part3. 删除的四大情况删除节点为黑替代节点为nullptr四大情况具体是什么呢我们来列一下1 w为红w的颜色会影响他的孩子的颜色所以要考虑他为红的情况2 w为黑左右子均为黑3 w为黑右子为红左子不论4 w为黑左子为红右子为黑p.s. nullptr也算是黑色节点Part3.1. w为红我们先来看图来看一下整个过程这里x那个三角形可以视为我们需要补充黑的节点。由于w为红所以其无法补充黑节点所以我们要旋转将w转化为黑来处理因为w为红孩子不可能为红所以无法补充新的黑。Part3.2. w为黑左右子均为黑这里要分为两个状况当p为红色时h(p)1,这时候只要把p、w染色就可以解决。当p为黑色时我们无法靠现有的条件来调整我们只能寄希望于上面的树交给上面来完成也就是p作为新的x向上调整。Part3.3. w为黑右子为红左子不论这样我们在不改变最上面那个节点的颜色下补全了缺失的黑节点这样就调整完成了。Part3.4. w为黑左子为红右子为黑当红色节点在w的右边时我们可以通过局部的旋转转化为上面情况三来处理。Part3.5. w在p的左边和上面的情况镜像对称。Part4. 删除代码实现bool erase(const K key) { Node* z find(key);//找到要删除的节点 Node* x nullptr;//替代节点 if (z nullptr) { return false; } colour col z-_col;//删除的结点的颜色 Node* parent z-_parent; int lor 0;//看删除的节点是在p的哪边 if (z-_left nullptrz-_right!nullptr)//二叉搜索树的删除逻辑 { if (z-_parent nullptr) { _root z-_right; z-_right-_parent nullptr; z-_right-_col BLACK; delete z; return true; } if (z-_parent-_left z) { z-_parent-_left z-_right; lor -1;//更新lor 区分情况 } else { z-_parent-_right z-_right; lor 1; } x z-_right; z-_right-_parent z-_parent; delete z; } else if (z-_left ! nullptr z-_right nullptr) { if (z-_parent nullptr) { _root z-_left; z-_left-_parent nullptr; z-_left-_col BLACK; delete z; return true; } if (z-_parent-_left z) { z-_parent-_left z-_left; lor -1; } else { z-_parent-_right z-_left; lor 1; } x z-_left; z-_left-_parent z-_parent; delete z; } else if (z-_left nullptr z-_right nullptr) { if (z-_parent nullptr) { delete z; _root nullptr; return true; } if (z-_parent-_left z) { z-_parent-_left nullptr; lor -1; } else { z-_parent-_right nullptr; lor 1; } x nullptr; delete z; } else { Node* y z-_right; while (y-_left ! nullptr) { y y-_left; } z-_kv y-_kv; col y-_col; parent y-_parent; if (y-_parent-_left y) { y-_parent-_left y-_right; lor -1; } else { y-_parent-_right y-_right; lor 1; } x y-_right; if (y-_right ! nullptr) { y-_right-_parent y-_parent; } delete y; } if (col RED)//如果删除的节点为红色 不用后续的调整了 { return true; } Node* w nullptr;//兄弟节点 if (lor 1) { w parent-_left;//看兄弟节点的位置 } else { w parent-_right; } while (x ! _root (xnullptr||x-_colBLACK))//当x为红色就不用循环 退出 当然当x为根节点时也要退出 { if (lor -1) { if (w-_col RED)//情况一 { w-_col BLACK; parent-_col RED; Node* tem w-_left; RotateL(parent); w tem; } else if (w-_col BLACK(w-_leftnullptr||w-_left-_colBLACK)(w-_rightnullptr||w-_right-_colBLACK))//情况二 { w-_col RED; x parent; if (x _root) { break; } else { if (x-_parent-_left x) { w x-_parent-_right; lor -1; } else { w x-_parent-_left; lor 1; } parent x-_parent; } } else if (w-_col BLACK w-_left ! nullptr w-_left-_col RED (w-_right nullptr || w-_right-_col BLACK))//情况四 { w-_left-_col BLACK; w-_col RED; Node* tem w-_left; RotateR(w); w tem; } else if (w-_col BLACK w-_right ! nullptr w-_right-_col RED)//情况三 { w-_col parent-_col; parent-_col BLACK; w-_right-_col BLACK; RotateL(parent); x _root;//定为_root退出循环 } } else//镜像对称 { if (w-_col RED) { w-_col BLACK; parent-_col RED; Node* tem w-_right; RotateR(parent); w tem; } else if (w-_col BLACK (w-_left nullptr || w-_left-_col BLACK) (w-_right nullptr || w-_right-_col BLACK)) { w-_col RED; x parent; if (x _root) { break; } else { if (x-_parent-_left x) { w x-_parent-_right; lor -1; } else { w x-_parent-_left; lor 1; } parent x-_parent; } } else if (w-_col BLACK w-_right ! nullptr w-_right-_col RED (w-_left nullptr || w-_left-_col BLACK)) { w-_right-_col BLACK; w-_col RED; Node* tem w-_right; RotateL(w); w tem; } else if (w-_col BLACK w-_left ! nullptr w-_left-_col RED) { w-_col parent-_col; parent-_col BLACK; w-_left-_col BLACK; RotateR(parent); x _root; } } } if (x ! nullptr) { x-_col BLACK;//为情况二p为红色情况服务 } _root-_col BLACK;//确保_root为黑节点 return true; }Part5. 结语这篇文章我们认识到了红黑树删除的实现接下来小编会带来map和set的模拟实现敬请期待~最后祝大家可以春风得意马蹄疾一日看尽长安花最后的最后要是觉得本文还可以的话可以点点赞关注小编一波谢谢大家~