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

  1. [12 минут] Случайные деревья
    1. Определения: средняя глубина вершины, глубина дерева, случайное дерево (Def1: добавляем случайную перестановку; Def2: корнем является случайный элемент)
    2. Lm: сумма размеров поддеревьев равна сумме глубин
    3. Оценка средней глубины случайного дерева 2ln(n) и такая же на глубину вершины (ссылаемся на QuickSort, в котором доказали факт про сумму размеров поддеревьев)
    4. Все операции в случайном дереве поиска работают за O(logn). Если исходные данные случайны, то дерево на выходе тоже случайно.
    5. Утверждение без док-ва: оценка максимальной глубины дерева, полученного при добавлении случайной перестановки 4ln(n)

  2. [18 минут] Декартово Дерево (treap, дерамида, дуча, курево) (1989 Aragon + Seidel)
    1. Cartesian tree : BST по xi, Heap по yi. Наивный алгоритм построения.
    2. Treap для ключей {xi} − Cartesian tree для {xi, yi=random}.
    3. Единственность декартового дерева и оценка средней глубины: см. тему случайные деревья
    4. Общая идея деревьев, начинающихся со split и merge : add и del получаем бесплатно.
    5. Операции split и merge, пишем split и merge.
    6. [skipped] [практика] Операция insert через 1 split и delete через 1 merge
    7. [skipped] [практика] Построение Cartesian tree по сортированным xi за O(n)
− Перерыв −
  1. Персистентные структуры данных: база
    1. Дерево поиска уже есть (минусы: больше памяти).
    2. Массив (O(1) → O(logn)) через дерево поиска по неявному ключу.
    3. Весь мир (состоит из массивов и деревьев).
    4. Простейший персистентный массив (дерево отрезков) и разница с персистентным деревом по неявному ключу (как у B и B*)
    5. Дерево версий для offline-задач

  2. Персистентные структуры данных: продвинутые
    1. RBST (решаем проблему y-ков)
    2. PersistentStack, PersistentQueue через лениво копирующийся стек за O(1) (5 стеков).
    3. PersistentDequeue (L,Pairs,R) за O(logn)
    4. garbage collector : ссылочный, stack-allocator + rebuild
− Перерыв −
  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 доп ячеек на вершину. Например, двусвязный список, дек.

  2. Деревья, хранящие только размер
    1. Spacegoat tree: size left, size right ≤ α*size
    2. Chinese tree: деревья, которые следят за "размер внука не более половины меня"