《算法—深入浅出》红黑树的删除
发布网友
发布时间：2023-12-29 16:09
共1个回答
热心网友
时间：2024-08-04 02:27
二、《算法—深入浅出》红黑树的旋转
三、《算法—深入浅出》红黑树的插入
四、《算法—深入浅出》红黑树的删除
在《红黑树的旋转》一篇中提到过，RBT的删除稍微比插入要复杂一点，那么如何复杂？又是如何删除与调整？本篇将会给大家揭开面纱！
为了能更清楚简单的描述整个过程，本篇将分为：
给定一个节点key 或 value，根据红黑树的特点：
如下图，我们要删除值为5的节点：
如果我们直接删除节点5，那么就要选择节点2 或者 节点8为新的根节点（取代节点5这个根，不是整个 RBT 的根），无论选择哪个节点为新根节点，都会不满足红黑树的第5点，从 RBT 的根到任意叶子节点，其路径上的黑色节点数相同。
那么，我们就没有好的办法了么？
办法肯定是有的，而且还有两种办法，当然，实际上只是一种方法，只是采取的策略不同而已！
首先，我们发现，比5次小的数是节点2的右节点，而比5次大的数是节点8的左节点，因此，我们可以选举节点3或节点6来成为新的节点，我们看看分别选用新的节点后，红黑树的结果如何？
我们发现，无论是采用『前驱选举法』还是『后继选举法』选举出的新根节点，来取代老节点，都满足红黑树的5条要求，而且不用调整（后文中会讲道哪些情况下不用调整，哪些情况下需要调整）。
那么前驱与后继是如何实现的，又有什么要求？
如果两个儿子都不存在，则需要考虑被删除节点的颜色（ 右节点同理，只是条件相左）：
先假设各节点的名称：
下面将对第 2 点中的 5 种情况用图来直观的分析：
