Является ли зигзагообразное вращение в Splay Tree отличным от двух правых или двух левых поворотов?

Question

Я понимаю, что зигзагообразное вращение - это в основном двойное вращение AVL. Является ли зигзагообразное вращение чем-то отличным от двух левых или двух правильных поворотов? Я думал, что это не так, но если я просто сделаю 2 правильных вращения для чего-то вроде изображения ниже, я получу неправильный ответ.

Если это действительно не то же самое, правильно ли предположить, что вращение зигзагообразного типа является особым типом вращения?

Answer 1

Разница заключается в том, какие узлы вы используете, чтобы сделать повороты и определенный порядок, в котором выполняются эти повороты. Давайте перейдем к узлам, которые мы используем в качестве ссылки для вращения в качестве базовых узлов, поэтому в случае зигзагового зигзавода у нас есть два базовых узла, первый из которых является родителем x в примере, т.е. p. Сначала мы делаем правое вращение вдоль этого узел, а затем мы делаем поворот вправо по узлу x. В том случае, если вы упомянули, что два правильных вращения будут выполняться на одних и тех же узлах. Таким образом, они заключаются в том, что они отличаются друг от друга с точки зрения того, какие узлы мы используем для вращения, и в каком порядке мы их используем. Зиг зиг сначала выполняет правое или левое вращение родителя, прежде чем совершать правый или левый поворот узла.