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

  1. [35 минут] Не сбалансированное дерево (1960, Windley + Booth + Colin + Hibbard)
    1. Определения: BST = Binary Search Tree. Глубина вершины. Balanced BST.
    2. Хранение: бинарное (left,right,parent), произвольное (left,next,parent), хранение в файле, генерация: упорядочить вершины и хранить только отца
    3. Код insert (три версии: return Node*; return void; персистентная)
    4. Операции find, rightmost, leftmost, next, previous
    5. Прошивка дерева. Rightmost, leftmost, next, previous за O(1) в худшем = дерево + двусвязный список + ссылки на rightmost и leftmost.
    6. Удаление
    7. Обходы дерева: симметричный (сортированный массив), прямой (хранение и восстановление дерева)
    8. Сортировка деревом, LowerBound на вставку O(logn).
    9. Вывод. Можно просто вывести сортированный массив. Дерево → 2D-картинка. Корень справа или корень сверху. Код для случая "корень справа".
    10. Добавляем хеш-таблицу и ленивость. Insert и LowerBound O(h), Del за O(1), Find за O(1)
    11. Как удалить вершину, которую вернул за O(1) Find? Ссылки на предков.
    12. Модификации дерева = set<int>: multiset<int>, map<int,int>
  2. [30 минут] AVL (1962, Adelson-Velsky + Landis)
    1. Определение, инвариант высот. Оценки на size[h], h[size].
    2. single/double rotation (малое/большое вращение), insert, выражение double rotation через две опреации single rotation
    3. Док-во корректноти insert, оценка количества вращений при insert: O(1).
    4. Красивый пример на доске из ~10 последовательных добавлений.
    5. Удаление. Максимальное количество вращений равно 0.5*h.
  3. [25 минут] Персистентное дерево (persistent tree)
    1. Определение персистентной структуры данных: любая операция изменения, например insert, не меняет старую и возвращает новую структуру данных
    2. Персистентное дерево поиска. Массив корней и ацикличный граф. Копирование пути от корня до вершины. Картинка для добавления нового элемента.
    3. Персистентное AVL дерево: все функции вместо того, чтобы менять старые вершина, создают новые. Персистентный код добавления.
    4. Оценка времени: не поменялось. Оценка памяти: O(nlogn) после n операций.
    5. Персистентный массив
      1. Примитивная структура: персистентный массив с O(1) на обращение и O(n) на модификацию
      2. Примитивная структура: персистентный массив с O(n) на обращение и O(1) на модификацию
      3. Массив → map<int,int> → персистентное AVL-дерево