algorithm - 如何在红黑树中旋转

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)和重新着色。

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