Двоичные Деревья Поиска

Выполнила: Соленникова София Сергеевна

В работе рассматриваются три подхода к построению эффективных структур данных для поиска. Первая часть посвящена splay-деревьям - самонастраивающейся структуре, использующей эвристику splaying для перемещения запрошенного узла в корень. Проводится амортизированный анализ, доказываются теоремы статической оптимальности, статического пальца и рабочего множества. Вторая часть посвящена алгоритму Кнута построения оптимальных статических бинарных деревьев поиска за время O(n²) с учётом успешных и неудачных поисков. Доказывается теорема о монотонности корней, позволяющая ускорить алгоритм. Третья часть анализирует амортизационную эффективность правила «перемещение в начало» (move-to-front) для списков и его аналога LRU для подкачки страниц, показывая их оптимальность с точностью до константного множителя.

Презентация (Соленникова) (PPTX, 1,17 Мб)

Итоговая документация