Сортировка выворачиванием / Comments / Habr

ov7a May 27 2020 at 19:35

Мораль сей басни такова: если приходится иметь дело с бинарным деревом поиска — работайте с ним как со splay tree, т.е. при любом действии с любым узлом дерева делайте этот узел корнем.

Очень странный вывод. Люди целые статьи пишут про сравнение поведения различных ДДП в зависимости от сценария использования, а тут такое однозначное утверждение. Конкретно в этом случае квадратичный случай в худшем случае меняется за счет того, что splay-дерево — самобалансирующееся и имеет логарифмическую амортизованную сложность операций. Но с тем же успехом подошло бы любое самобалансирующееся дерево — красно-черное или АВЛ, например.

Кроме того, тупое поднятие в корень без использования процедур zig, zigzag и zigzig может все равно привести к линейной сложности операции. Про комбинацию этих трех процедур есть доказательство, что там все будет ок, а если, например, использовать только zig (им тоже элемент в корень можно поднять), то можно получить квадратичную сложность операции в худшем случае.

Comments 3

valemak May 27 2020 at 20:27

Согласен, рекомендация звучит слишком безапелляционной, немного переформулировал этот абзац.

Да, я когда программировал эту операцию лично убедился, что одного zig вполне достаточно для поднятия узла наверх. Но в анимации, конечно, используется комбинированный подход.

ov7a May 27 2020 at 20:32

Так в том-то и дело, что если использовать только zig, то там с тем же успехом можно получить квадратичную сложность. В некоторых случаях это будет хуже чем с обычным ДДП,