1632
правки
Изменения
м
rollbackEdits.php mass rollback
===find(tree, x)===
Эта операция выполняется как для обычного [[Дерево поиска, наивная реализация|бинарного деревапоиска]], только после нее запускается операция splay.
===merge(tree1, tree2)===
p(r) = p
'''if''' (v.right != '''null''')
p(v.right) = v
Реализация splay:
===Время работы===
В обоих обеих реализациях осуществляется проход по пути от корня к целевой вершине и/или обратно. По вышеупомянутой Лемме, путь состоит из <tex>O(\log n)</tex> вершин. Обработка каждой вершины имеет сложность <tex>O(1)</tex>. Таким образом, сложность приведенных выше операции splay {{---}} <tex>O(\log n)</tex>
==Анализ операции splay==
