В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Алгоритмы и структуры данных, часть 1
/
осень 2018
/

Семинар 11. Дерево поиска с неявным ключом

Суббота, 08 декабря 2018
НГУ, ауд. 2128, НГУ, новый корпус
Список тем / 24 записи
    1.
    Лекция 1. Сложность и модели вычислений
    2.
    1. Вводное занятие
    3.
    Лекция 2. Сортировки
    4.
    2. Разное
    5.
    Лекция 3. Кучи (начало)
    6.
    3. Динамическое программирование
    7.
    Лекция 4. Кучи (продолжение)
    8.
    Семинар 4. Динамическое программирование
    9.
    Лекция 5. Порядковые статистики
    10.
    Семинар 5. Тестирование
    11.
    Лекция 6. Хеширование
    12.
    Семинар 6. Быстрое преобразование Фурье
    13.
    Лекция 7. Деревья поиска
    14.
    Семинар 7. Хеширование, итераторы
    15.
    Лекция 8. Деревья поиска: продолжение
    16.
    Семинар 8. Метод заметающей прямой
    17.
    Лекция 9. Задачи RMQ и LCA
    18.
    Семинар 9. Дерево отрезков
    19.
    Лекция 10. Система непересекающихся множеств
    20.
    Семинар 10. Разное
    21.
    Лекция 11. Структуры данных для геометрического поиска
    22.
    Семинар 11. Дерево поиска с неявным ключом
    23.
    Лекция 12. Задача о динамической связности в ненаправленном графе
    24.
    Семинар 12. Параллельные алгоритмы

Описание

Сравнение дерева поиска и дерева отрезков. Выделение отрезка при помощи Split/Join. Неявный ключ = номер в обходе. Хранение количества вершин в поддереве. Хранение дополнительной информации о поддереве и запросы на отрезке, функция Update. Хранение отложенных модификаций и модификации на отрезке, функция Actualize.

Использование указателя на вершину в качестве ручки. Определение ручки по номеру. Определение номера по ручке и хранение отцов вершин.

Реализация функции Split (код/алгоритм) для Treap. Нулевой указатель = пустое дерево.

Примеры. Дерево отрезков {+=, min(a)}. Набор строк с разрезанием и конкатенацией. Операции развернуть отрезок: реализация через два дерева и через отложенные модификации.

Задача про изоморфное упорядоченное дерево со Всесибирской 2012 года (задача 9). Представление дерева в виде правильной скобочной последовательности, хранение ПСП в дереве поиска с неявным ключом. Выполнение операций изменения и ручки. Полиномиальный хеш и совпадение ПСП, поддержка хеша в качестве статистики. Время работы. Разрешение коллизий.