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

25

Я не совсем понимаю, почему при ротации в структуре данных 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", вы не думаете?

Bober02
источник

Ответы:

30

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

плохой пример просто вращаться

N2/2Ω(N)Ω(N)

плохой пример продолжается

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

ИксИксИкс

выкладывать плохой пример

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

О(журналN)Ω(N)

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

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