Работа ZigZag и ZigZig в дереве сплайнов?

Question

Рассмотреть мое дерево, как это

                 5
                / \
               3   7
              / \ / \
             2  4 6  8

в том, что когда мы ищем элемент 2 в этот раз будет выполнена зигзагообразная операция, поэтому сначала мы поворачиваем parent and ancestor of 2 затем мы поворачиваем parent and 2,

в том же случае, рассмотрим мы ищем 4 В этот раз будет выполнена зигзагообразная операция. в этом первом мы вращаем 4 and its parent затем 4 and its ancestor будет повернут.

почему мы так, зигзагообразно, почему мы не поворачиваем parent and ancestor вместо searching node and parent,

Пожалуйста, объясните мне?? Заранее спасибо.

Answer 1

Порядок вращений важен. Вот что делает анализ доходностью O(lg n) время на операцию амортизируется по последовательности m операций. splay(x) Эвристика перемещает узел x к корню дерева, но вместо того, чтобы просто вращать x, пока он не станет корнем, шаг зигзага сначала вращает родителя x, а затем вращает x. Например, если бы мы просто вращали x, пока он не стал корнем, анализ не принесет ничего полезного.

Вы описываете что-то другое здесь. Вы хотите всегда сначала повернуть родительский элемент, а затем повернуть дочерний элемент. Вы должны формально доказать, что эта эвристика хороша, если вы думаете, что это так, но чтобы ответить на вопрос: порядок вращения в деревьях сплайнов гарантирует O(m lg n) ограничен последовательностью из m операций.