Сбалансированные деревья, часть 1

  1. Не сбалансированное дерево (1960, Windley + Booth + Colin + Hibbard)
    1. Определение дерева поиска. Сколько деревьев соответствует одной перестановке?
    2. Хранение: бинарное, произвольное, упорядочить вершины и хранить только отца, хранение дерева в файле
    3. insert (две версии: обычная и персистентная)
    4. find, right/left neighbour, erase
    5. Обходы дерева: симметричный (сортированный массив), прямой (хранение и восстановление дерева)
    6. Вывод дерева: дерево → массив; дерево → 2D-картинка
    7. Определения: глубина вершины, средняя глубина вершины, глубина дерева, случайное дерево (добавляем случайную перестановку)
    8. Lm: сумма размеров поддеревьев равна сумме глубин
    9. Оценка средней глубины случайного дерева 2ln(n) (ссылаемся на QuickSort)
    10. Оценка максимальной глубины дерева, полученного при добавлении случайной перестановки 4ln(n) (только формулировка)
    11. Все операции работают за O(h). Теперь пытаемся ограничить высоту.
    12. Сортировка деревом, LowerBound на вставку O(logn).
    13. Вспоминаем сортированный массив и хеш-таблицу. Insert и LowerBound O(h), Del за O(1), Find за O(1)
    14. Что потом делать с Find, если он вернул указатель на вершину? Ссылки на предков.
    15. Операции next и prev, прошивка дерева (next и prev за O(1) в худшем, дерево + двусвязный список)
  2. AVL (1962, Adelson-Velsky + Landis)
    1. Определение, инвариант высот
    2. Оценки на size[h], h[size]
    3. Хранение, удобства реализации: node::null; calc(): size, h
    4. small/big rotation, insert, выражение big rotation через 2 small rotation
    5. Оценка количества вращений при insert: O(1)
    6. Удаление. Максимальное количество вращений равно h/2.
    7. [не успеем] Операция на отрезке L ≤ x ≤ R: сумма x, сумма y, минимум по y.
    8. [не успеем] Операция на отрезке L ≤ x ≤ R: увеличить все y на dy, присвоить всем y некоторое значение y0 (модификация на отрезке, проталкивание информации вниз)
    9. Напоминание: операция find за O(1).
  3. Идея неявного ключа (implicit key)
    1. Поддержка размеров поддеревьев, ответ на запрос k-й элемент
    2. Неявный ключ, массив с операциями insert(i, x), erase(i) за O(logn)
  4. Персистентное дерево (persistent tree)
    1. Определение персистентной структуры данных: любая операция изменения, например insert, не меняет старую и возвращает новую структуру данных
    2. Примитивная структура: персистентный массив с O(1) на обращение и O(n) на модификацию
    3. Примитивная структура: персистентный массив с O(n) на обращение и O(1) на модификацию
    4. Персистентное дерево поиска. Массив корней и ацикличный граф. Копирование пути от корня до вершины. Картинка для добавления нового элемента.
    5. Персистентное AVL дерево: все функции вместо того, чтобы менять старые вершина, создают новые. Пример с вращениями.
    6. Оценка времени: не поменялось. Оценка памяти: O(nlogn) после n операций.
  5. Декартово Дерево (treap, дерамида, дуча, курево) (1989 Aragon + Seidel)
    1. Определение, примеры. Наивный алгоритм построения.
    2. Единственность декартового дерева (поддерево декартово дерева является декартовым деревом, далее индукция)
    3. Оценка средней глубины, оценка макисмальной глубины, доказательство того, что наивный алгоритм построения работает за O(nlogn).
    4. Операции split и merge
    5. Операции insert и erase через split, merge
    6. Операция insert через 1 split (а вот delete через 1 merge на практике)
    7. Замечание про равные ключи
      1. {x, count} (для каждого x есть ровно одна вершина)
      2. {x, какой-то ключ различающий x-ы} (для каждого x есть столько вершин, сколько раз x входит, но все пары различны)
      3. Всё делать через split и merge, которые не меняют порядок
    8. [не успеем] Декартово дерево по неявному ключу: rotate(a, a+k, a+n) за O(logn)
    9. [не успеем] В декартовом дереве по неявному ключу можно хранить массив (доступ к элементу за O(logn) + дополнительные операции)
  6. Peristent world
    1. Peristent tree уже было
    2. Peristent array: tree + implicit key