Деревья поиска, часть 2 (16 апреля 2021)

1. Вступительный код
   1. Пишем bst + lowerbound
   2. Пишем avl.add + avl.del
   
   
2. B+-Tree
   1. Ключи только в листьях. Делаем Add, Del.
   
   
3. [12 минут] Случайные деревья
   1. Определения: средняя глубина вершины, глубина дерева, случайное дерево (Def1: добавляем случайную перестановку; Def2: корнем является случайный элемент)
   2. Lm: сумма размеров поддеревьев равна сумме глубин
   3. Оценка средней глубины случайного дерева 2ln(n) и такая же на глубину вершины (ссылаемся на QuickSort, в котором доказали факт про сумму размеров поддеревьев)
   4. Все операции в случайном дереве поиска работают за O(logn). Если исходные данные случайны, то дерево на выходе тоже случайно.
   5. Утверждение без док-ва: оценка максимальной глубины дерева, полученного при добавлении случайной перестановки 4ln(n)
   
   
4. [18 минут] Декартово Дерево (treap, дерамида, дуча, курево) (1989 Aragon + Seidel)
   1. Cartesian tree : BST по x_i, Heap по y_i. Наивный алгоритм построения.
   2. Treap для ключей {x_i} − Cartesian tree для {x_i, y_i=random}.
   3. Единственность декартового дерева и оценка средней глубины: см. тему случайные деревья
   4. Общая идея деревьев, начинающихся со split и merge : add и del получаем бесплатно.
   5. Операции split и merge, пишем split и merge.
   6. [skipped] [практика] Операция insert через 1 split и delete через 1 merge
   7. [skipped] [практика] Построение Cartesian tree по сортированным x_i за O(n)

1. Персистентные структуры данных: база
   1. Дерево поиска уже есть (минусы: больше памяти).
   2. Массив (O(1) → O(logn)) через дерево поиска по неявному ключу.
   3. Весь мир (состоит из массивов и деревьев).
   4. Простейший персистентный массив (дерево отрезков) и разница с персистентным деревом по неявному ключу (как у B и B+)
   5. Дерево версий для offline-задач
   
   
2. Персистентные структуры данных: продвинутые
   1. RBST (решаем проблему y-ков)
   2. PersistentDequeue (L,Pairs,R) за O(logn)
   3. PersistentStack, PersistentQueue через лениво копирующийся стек за O(1) (5 стеков).
   
   
3. garbage collector
   1. Постановка задачи: не все версии персистентного дерева нужны. Что делать?
   2. ссылочный (счётчик ссылок)
   3. stack-allocator + rebuild
   4. shared_ptr

1. Частичная персистентность и fat node.
   1. Виды персистентности: partial, full, confluent (functional)
   2. Идея fat node. Наивное применение для массива: проблемы в full, O(log n) для partial.
   3. Применение для дерева поиска: 1 доп ячейка на вершину. Получаем изменение за O(1) доп времени и памяти.
   4. Какие BST хороши в данном контексте: AVL сбалансированно, делает O(1) изменений указателей и высот ⇒ идеально. Кстати, O(1) для высот даже не обязательно.
   5. Задачи, которые мы можем так решать: persistent scanline с O(n) памяти. Жутко полезная задача: локализация точки в планарном графе [O(n), O(logn)].
   6. Что ещё мы получили? Любую ссылочную структуру, у которой не более p = O(1) входящих ссылок можно поддерживать через p+1 доп ячеек на вершину. Например, двусвязный список, дек.