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