• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Семинар по алгоритмам и структурам данных «Статическая оптимальность и другие свойства Splay-дерева»

Мероприятие завершено

Мамай Игорь Борисович
доцент департамента больших данных и информационного поиска

18 марта 2025 в 18:10

Докладчик: Игорь Мамай, ФКН НИУ ВШЭ 

Тема: Статическая оптимальность и другие свойства Splay-дерева

Аннотация: 

На семинаре речь пойдет про Splay-дерево. Эта структура данных широко известна и многие знакомы не только с ее определением, но и с тем, как выбираются потенциалы для оценки амортизированного времени работы Splay-дерева. Поэтому мы только вспомним саму функцию потенциала и сформулируем лемму об амортизированном времени работы операции Splay для произвольной вершины дерева.
Далее мы подробно обсудим, как выбор весов элементов позволяет вывести теорему о статической оптимальности Splay-дерева, а также теорему о балансе, теорему о рабочем множестве и теорему о статических указателях.

В дополнение мы обсудим, как можно получить нижнюю оценку на время работы статически оптимального двоичного дерева поиска. А также обсудим алгоритм, который за 𝓞(n2) строит самое быстрое статичное двоичное дерево поиска для заданного набора запросов.

В конце мы затронем теорему о последовательном доступе к элементам Splay-дерева. Эта теорема говорит о том, что для произвольного Splay-дерева последовательный доступ к его элементам в порядке возрастания требует 𝓞(n) действий. Этот результат показывает преимущество Splay-дерева над любым статичным деревом и дает почву для веры в справедливость гипотезы о динамической оптимальности Splay-дерева.

Место проведения: Покровский бульвар 11, аудитория D506

Регистрация