=^_^= Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 04 - Про обычные деревья и Splay-дерево

Note: Звездочкой отмечены темы, на которые на лекции времени не хватило.

Краткий план лекции на тему "Про обычные деревья и Splay-дерево"

  1. Деревья от Олега Давыдова (AVL, RB, ...)
  2. Бинарные деревья поиска (все операции, которые можно просто делать за O(logn))
  3. Splay-tree
  4. Linking-Cutting trees
  5. MaxFlow за O(nmlogn)

Полный план лекции

  1. Деревья от Олега Давыдова
    1. AVL-tree (добавление - 2 случая = 2 разных вращения, удаление - спуск вниз, еще 1 случай)
    2. RB-tree (red-black)
    3. 2-3-tree, 2-3-4-tree
    4. AA-tree
  2. Бинарные деревья поиска
    1. Произвольные бинарные деревья поиска : Access, SiftUp
    2. SiftUp --> Split & Join
    3. Split & Join --> Insert & Delete
    4. Операции sum, min на отрезке
    5. K-е порядковое значение (храним size[v])
    6. Переход к неявному ключу, операции с массивами - вставка, поменять куски местами, переворот
    7. Путь в графе --> массив --> дерево поиска
  3. Splay-tree
    1. Операция Splay (root-case, zig-zig, zig-zag), Splay делает также SiftUp
    2. w[v], sum[v], rank[v] = log(sum[v]) (логарифмы все будут двоичными)
    3. Splay делает <= 1 + 3(rank[x'] - rank[x]) вращений. x = x' - начальная и конечная вершина
    4. m запросов работают за O(mlogn) (w[v] = 1)
  4. Linking-Cutting trees
    1. Постановка задачи : link, cut, addX, getMin
    2. Разбиение дерева на пути, каждый путь хранится как дерево поиска
    3. Операции explose & splice, выражение всех через explose
    4. Число splice-ов O(mlogn) => Исходная задача решается за O(m(logn)^2) произвольным деревом
    5. Применяя Splay-дерево, решаем исходную задачу за O(mlogn)
  5. MaxFlow за O(nmlogn)
    1. Алгоритм Диница, поиск блокирующего потока (напоминание)
    2. Построение дерева путей. Поиск блокирующего потока за O(mn)
    3. Поиск блокирующего потока за O(mlogn) с помощью Splay-tree