Python 中红黑树的删除

红色黑色树

红黑树是一种二叉搜索树，它具有“近乎”平衡的附加属性。红黑树中的每个节点都有一个颜色，红色或黑色，这些颜色用于在插入和删除过程中保持平衡。

删除

BST 删除

首先，使用标准的 BST 删除来查找需要删除的节点。如果节点有一个或没有子节点，则删除它并用它的子节点（如果有）替换它。

保存要删除的节点的颜色，因为它稍后将用于确定是否应用“删除修复”。

修复违规（删除修复）

与插入一样，删除可能会违反红黑树属性，特别是双黑属性。您需要执行一系列重新着色、旋转和替换操作，这些操作称为“删除修复”。

1. 确定节点被删除的哪一侧（左侧或右侧），以及该节点的兄弟节点的颜色是红色还是黑色。
2. 如果兄弟节点是红色的，则执行旋转和重新着色，将问题转换为其他情况之一。
3. 如果兄弟节点是黑色的，并且它的两个子节点都是黑色的或无效的，则将兄弟节点重新着色为红色，并将双黑问题向上传播。
4. 如果兄弟节点是黑色的，并且至少有一个红色子节点，则执行旋转和重新着色，将问题转换为下一情况。
5. 重复这些步骤，向上遍历树，直到双黑问题传播到根节点之外或违规得到解决。

代码

输出

初始树

删除元素 40 后

删除元素 65 后

正确执行这些步骤可确保插入和删除操作具有良好的性能，并保持树的有用属性。