Как вращаться в красном черном дереве

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 - это узел, который я хочу вставить), а zp - его отец.Поэтому я попытался выполнить шаги до левого поворота, и вот результат: так ли это?

Я искал в интернете и прочитал, что есть алгоритм двойного вращения, но я не могу понять, могу ли я использовать их здесь вместо одного вращения (например, яне знаю, что вправо повернуть узел с 4).

Answer 1

Вы следуете не тому делу.Я объяснил ответ в следующих шагах.На последнем шаге, т.е. вставке 9, мы должны выполнить левое вращение (4) и перекрасить.

Ниже приведен рисунок, на котором я объяснил шаги: