Жадные алгоритмы → BST и AVL (19 апреля 2017)

  1. Приближённые алгоритмы
    1. [15 минут] ln(n)-OPT алгоритм для set cover (покрыть множество множествами)
  2. [25 минут] Задача про дедлайны, решения без динамики
    1. Идея "минимальный по времени брать выгодно". Решение за O(n2).
    2. Идея "жадно брать в порядке возрастания дедлайна". Если выгодно сделать замену, сделать замену.
    3. Доказательство корректности последней идеи.
− Перерыв −
  1. BST
    1. Определение, поиск, добавление и удаление
    2. Прошивка: предыдущий и следующий элемент, как бы двусвязный список
    3. Find и delete: при желании их умеют делать хеш-таблицу + ленивость
    4. Код добавления: обычная и персистентная (immutable) версии
    5. Персистентные структуры данных
  2. AVL
    1. Определение, ограничение на высоту, малые и большие вращения
    2. Перебалансировка после add, доказательство леммы "не более одного вращения на add"