Python 中红黑树的插入

红色黑色树

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

红色黑色树插入算法

1. 从树的根节点开始。
2. 沿着二叉搜索树的性质向下遍历树，找到新节点插入的合适位置。
3. 将新节点作为红色叶子节点插入。
4. 使用一系列旋转和重新着色操作，修复由插入可能引起的任何红黑树属性的违规。

代码

输出

插入

BST 插入

首先，像在标准二叉搜索树 (BST) 中一样插入新节点。根据键值的比较，将节点放置在合适的位置。将节点着色为红色：插入时，将新插入的节点着色为红色。这最初可能会违反红黑树的某些属性。

修复违规 (插入修复)

为了确保树维护红黑属性，您需要执行一系列称为“插入修复”的重新着色和旋转操作。这种修复在容纳新的红色节点时，会恢复树的平衡和属性。

1. 检查新插入节点的父节点是否也是红色的。如果是，则可能违反了红色属性。
2. 如果父节点的叔叔节点是红色的，则将父节点和叔叔节点重新着色为黑色，并将祖父节点重新着色为红色。这会在路径上维护黑色属性，并有助于恢复红色属性。
3. 如果父节点的兄弟节点是黑色或无效，则执行旋转和重新着色以恢复平衡。根据新插入的节点是其父节点的左子节点，父节点是其祖父节点的右子节点（反之亦然），执行适当的旋转和重新着色。
4. 如果需要，重复这些步骤，向上遍历树，直到所有属性都得到恢复。

平衡树：重新着色和旋转

双红

当新插入节点的父节点和叔叔节点都是红色时，将父节点和叔叔节点重新着色为黑色，并将祖父节点重新着色为红色。这确保了红色属性得到恢复。该过程可能一直向上进行，以修复进一步的不平衡。

不匹配

当新插入的节点是右子节点的左子节点（或反之）时，会执行旋转操作来重新对齐树。这维护了黑色属性并确保了平衡。