如何在红黑树中旋转

Question

我正在尝试用红黑树解决此练习：我需要按此顺序插入 2、1、4、5、9。在最后一次输入之后，我需要用 Insert-Fixup 算法来平衡它：

我需要遵循的算法部分是：

if z == z.p.right
   z = z.p
   LEFT-ROTATE (T, z)
z.p.color = BLACK
z.p.p.color = RED
RIGHT-ROTATE (T, z.p.p)

（Z是我要插入的节点），z.p是它的父亲。所以我尝试按照步骤进行操作，直到向左旋转，这就是结果：对吗？

我在互联网上搜索，我读到有双旋转算法，但我不知道我是否可以在这里使用它们而不是使用单旋转（例如我不知道热向右旋转节点与 4).

Answer 1

您关注的案例有误。我已经在以下步骤中解释了答案。在最后一步，即插入9，我们必须进行左旋转（4）和重新着色。

以下是我解释步骤的图片：