Сплайс деревья: как зигзаг и зигзаг вращаются в деталях?

Question

Мне нужна помощь в понимании конкретного примера зигзагообразных и зигзагообразных вращений в деревьях сплайнов. Я читал о них в книге и в Википедии, а также в нескольких других онлайн-ресурсах, и хотя я могу понять их, когда они применяются к простым деревьям (т.е. деревьям с очень небольшим количеством узлов), я теряюсь, когда вижу примеры из них применяются к более крупным деревьям (то есть деревьям с большим количеством узлов).

В частности, я не понимаю, по крайней мере, один из этих 2 примеров:

Пример 1

(это не полный пример, но это часть, которую я не понимаю)

В (1) мы можем видеть, что узел, который должен быть развернут, является правым потомком левого потомка, и поэтому мы должны сделать зигзаг. Поэтому я могу понять, что происходит между (1) и (2), когда развертываемый узел теперь занял место своего родителя. В моем понимании, вся зигзагообразная операция произошла там. Итак, первое расширение закончено, и нам все еще нужно развернуть узел, пока он не окажется в корне дерева.

Я не понимаю, что происходит между (2) и (3). В (2) развертываемый узел является левым потомком левого потомка, поэтому я ожидал зигзагообразную операцию, при которой воспроизводимый узел вращается вокруг своего деда, то есть (20, Z). Вместо этого слайд показывает поворот с его родителем, (10, A). Зачем? Я ожидал, что наш расширяющий узел (8, N) выполняет зигзагообразное движение и, таким образом, занимает места (20, N), который является его прародителем, а также корнем. Почему вместо этого участвует родитель?

В ресурсе, где я нашел этот пример (слайды моего лектора), зигзагообразное вращение описывается как "вращать узел со своими родителями, а затем вращать узел со своим прародителем". Это то, что здесь происходит? Это причина того, почему между (2) и (3), (8, N) вращается с (10, A) вместо (20, Z)?

Я очень смущен этим описанием, потому что тогда вращение зигзагом описывается как "поворот узла с его прародителем, затем поворот узла с его родителем". Тем не менее, каждый раз, когда я видел пример вращения зигзагом, всегда есть только один поворот с прародителем узла и все. Я никогда не видел 2 вращения.

Тогда есть этот другой пример:

В этом примере операция splay включает в себя зиг-зиг. Как видите, здесь только 1 поворот. Затем происходит второе отображение, потому что доступ к узлу все еще не находится в корневой позиции.

То, что я ожидал бы вот что:

• Либо приведенные описания зигзаг и зигзаг верны, и поэтому во втором примере было бы 2 поворота: одно вокруг прародителя узла, затем одно вокруг его родителя.
• Или приведенное описание неверно, поэтому второй пример верен, но первый - не так, как мы повернули узел с его родителем, а не с прародителем, пока он находился в зигзагообразном положении.

Можете ли вы дать мне знать, если какой-либо из этих двух примеров является неправильным, и какой? Если никто из них не прав, где я не прав?

Спасибо за помощь.

PS: Поскольку очевидно, что я студент, я просто хотел бы сообщить вам, что я не задаю этот вопрос в контексте задания, и поэтому я не обманываю. Однако в этот понедельник у меня будет экзамен, и я надеюсь прояснить любое недоразумение перед тем, как сдать экзамен.

Answer 1

Распространение узла x является последовательностью шагов воспроизведения, пока x не станет корнем дерева. Эти шаги зиг, заг и зигзаг.

Для узла x его родительский p и родительский элемент pg, зигзагообразная операция на узле x определена для случая, когда p не является корнем, а x является правым потомком p, а p является левым потомком g: сначала поверните влево на x, затем поверните вправо на x. Ваш первый пример показывает именно этот случай: zig вращается влево x = (8, X) и его родительский p = (7, T), затем zag вращается вправо (8, X) и g = (10, A). Таким образом, этот пример показывает зигзаг на x, но само расширение не выполнено, потому что x еще не является root (то есть необходимо выполнить больше шагов расширения).

zig-zig определен для случая, когда оба x и p являются правыми потомками их соответствующих родителей: сначала поверните левое p, затем поверните левое x. Второе изображение вашего второго примера показывает результат зиг-зиг на x = (40, X), p = (37, P), g = (35, R): сначала p поворачивается влево, затем x поворачивается влево, На третьем рисунке второго примера показана дополнительная операция зигзага по оси x (вращение влево x, так как его родительский элемент p является корнем), перемещение к корню и завершение расширения x.

(Все операции зиг, зиг-зиг и зигзаг имеют свои симметричные аналоги).