АиСД S02E07. Splay дерево

Алгоритмы и структуры данных. Семестр 2. Лекция 7.
На седьмой лекции мы продолжили говорить про сбалансированные деревья поиска. Изучили, как работает Splay дерево и поговорили о том, почему оно может быть лучше других деревьев поиска.
Университет ИТМО, 2022 г.

[@ddvamp]

Можно ли выполнять однократный поворот не в конце, а в начале? Не ухудшится ли от этого асимптотика?

[@pavelmavrin]

Отличный вопрос. Кажется, что нет. Попробуйте повторить анализ асимптотикти и проверить, так ли это.