Сбалансированные деревья (26 апреля 2017)

  1. BST (перенесено на практику)
    1. Хранение, прямой обход
    2. Node*, итератор
  2. Другие деревья
    1. B-tree, 2-3-tree
    2. 2-3-4-tree, RB-tree, AA-tree
    3. B*-tree, B+-tree, оценка h×log(k) = log(n) для B-tree (find, insert, erase)
    4. Применение B-tree и RB-tree
− Перерыв −
  1. Случайные деревья
    1. Определения: средняя глубина вершины, глубина дерева, случайное дерево (Def1: добавляем случайную перестановку; Def2: корнем является случайный элемент)
    2. Lm: сумма размеров поддеревьев равна сумме глубин
    3. Оценка средней глубины случайного дерева 2ln(n) и такая же на глубину вершины (ссылаемся на QuickSort, в котором доказали факт про сумму размеров поддеревьев)
    4. Все операции в случайном дереве поиска работают за O(logn). Если исходные данные случайны, то дерево на выходе тоже случайно.
    5. Утверждение без док-ва: оценка максимальной глубины дерева, полученного при добавлении случайной перестановки 4ln(n)
  2. Декартово Дерево (treap, дерамида, дуча, курево) (1989 Aragon + Seidel)
    1. Определение, примеры. Наивный алгоритм построения.
    2. Единственность декартового дерева и оценка средней глубины.
    3. Операции split и merge (код split пишем, merge − нет)
    4. Операции insert и erase через split, merge
    5. [skipped] (на практику) Операция insert через 1 split и delete через 1 merge
− Перерыв −
  1. Дерево по неявному ключу
    1. Поддержка размеров поддеревьев, ответ на запрос k-й элемент
    2. Неявный ключ, массив с операциями insert(i, x), erase(i), get(i), set(i, x) за O(logn)
    3. Простейший персистентный массив и разница с персистентным деревом по неявному ключу
  2. RBST
  3. Ссылочный garbage collector
  4. Операции на отрезке в дереве по неявному ключу со split и merge
    1. Sum, Min
    2. +=, =
    3. reverse
    4. rotate(a, a+k, a+n) за O(logn)
  5. Skip-list
  6. Splay-tree
  7. RBST
  8. Ссылочный garbage collector