Почему алгоритм вращения Splay Tree учитывает как родительский, так и родительский узел?

Я не совсем понимаю, почему при ротации в структуре данных Splay Tree учитывается не только родительский узел рейтингового узла, но и прародитель (операция zig-zag и zig-zig). Почему следующее не работает:

Когда мы вставляем, например, новый узел в дерево, мы проверяем, вставляем ли мы в левое или правое поддерево. Если мы вставим в левое, мы повернем результат вправо, и наоборот для правого поддерева. Рекурсивно это было бы что-то вроде этого

Tree insert(Tree root, Key k){
    if(k < root.key){
        root.setLeft(insert(root.getLeft(), key);
        return rotateRight(root);
    }
    //vice versa for right subtree
}

Это должно избежать всей процедуры "splay", вы не думаете?

Более простой алгоритм балансировки может потребовать амортизированного времени на оборот в худшем случае. Предположим, что дерево - это просто совершенно неуравновешенный путь правильных детей; ни у одного узла нет левого потомка. Единственный лист этого дерева - дерево с максимальным ключом. Если вы поворачиваете этот шаг за шагом до корня, вы использовали n - 1 поворотов, и результирующее дерево все еще полностью не сбалансировано.$\Omega(n)$$n-1$

$n^2/2$$\Omega(n)$$\Omega(n)$

Этот плохой пример появляется в оригинальной бумаге Splay Tree от Sleator и Tarjan.

$x$$x$$x$

Преимущество этого более сложного алгоритма состоит в том, что он не только доставляет доступ к узлу к корню, но также перемещает каждого предка узла, к которому осуществляется доступ, примерно на полпути к корню , но никогда не перемещает ни один узел более чем на постоянное число уровней от корень.

$O(\log n)$$\Omega(n)$

Короче говоря: Splaying перемещает узлы вверх быстро и вниз медленно.