Семинар по алгоритмам и структурам данных «Статическая оптимальность и другие свойства Splay-дерева»
Мамай Игорь Борисович
доцент департамента больших данных и информационного поиска
18 марта 2025 в 18:10
Докладчик: Игорь Мамай, ФКН НИУ ВШЭ
Тема: Статическая оптимальность и другие свойства Splay-дерева
Аннотация:
На семинаре речь пойдет про Splay-дерево. Эта структура данных широко известна и многие знакомы не только с ее определением, но и с тем, как выбираются потенциалы для оценки амортизированного времени работы Splay-дерева. Поэтому мы только вспомним саму функцию потенциала и сформулируем лемму об амортизированном времени работы операции Splay для произвольной вершины дерева.
Далее мы подробно обсудим, как выбор весов элементов позволяет вывести теорему о статической оптимальности Splay-дерева, а также теорему о балансе, теорему о рабочем множестве и теорему о статических указателях.
В дополнение мы обсудим, как можно получить нижнюю оценку на время работы статически оптимального двоичного дерева поиска. А также обсудим алгоритм, который за 𝓞(n2) строит самое быстрое статичное двоичное дерево поиска для заданного набора запросов.
В конце мы затронем теорему о последовательном доступе к элементам Splay-дерева. Эта теорема говорит о том, что для произвольного Splay-дерева последовательный доступ к его элементам в порядке возрастания требует 𝓞(n) действий. Этот результат показывает преимущество Splay-дерева над любым статичным деревом и дает почву для веры в справедливость гипотезы о динамической оптимальности Splay-дерева.
Место проведения: Покровский бульвар 11, аудитория D506