Декартово и Splay деревья (СПБГУ МатМех, весна 2013, спецкурс 344-й группы)

  1. Какие существуют структуры данных? [15 минут]
    1. Массив (vector, queue, dequeue)
      1. Stack на массиве: get(i) за O(1), set(i) за O(1), добавить/удалить в конец за O(1)
      2. Dequeue на циклическом массиве: get(i) за O(1), set(i) за O(1), добавить/удалить в начало/конец за O(1)
      3. Статитический массив. Динамический массив (удвоение).
      4. Сортированный массив: Find(x) и Count(L,R) за O(logN)
    2. Хештаблицы (hash_set, hash_map)
      1. Самая простая реализация List hashTable[]
      2. find(x), add(x), del(x) за O(1)
      3. При переполнении: удвоение
      4. iterate_all за O(k): прикрепленный список
    3. Куча (priority_queue, make_heap)
      1. get_min за O(1)
      2. add, del за O(logN)
    4. BST, Бинарное дерево поиска (set, map)
      1. find(x), add(x), del(x), lower_bound(x) за O(logN)
      2. iterate_all в отсортированном порядке за O(k)
      3. iterate(L, R) в отсортированном порядке за O(k)
      4. get_min и get_max за O(1)
    5. Решим задачу count(L,R), add(x), del(x)
      1. Решение1: O(n), O(1), O(1)
      2. Решение2: O(k), O(logN), O(logN)
      3. Решение3: O(√ n ), O(1), O(1)
  2. Декартово дерево по явному ключу [30-35 минут]
    1. Определение (Heap по y, BST по x)
    2. Единственность в случае, когда все x и y различны
    3. Оценка средней высоты случайного дерева (сумма по i, j: вероятность того, что i -- предок j)
    4. Основные операции декартова дерева: Split и Merge (определение)
    5. Add и Del через Split и Merge
    6. Split (вместе с кодом)
    7. Merge (вместе с кодом)
    8. Not read Add и Del, работающие в 3 раза быстрее (только 1 Split/Merge)
  3. Задачи на декартово дерево [15-20 минут]
    1. k-й элемент
    2. findNext, findPrev
    3. Count(L, R), Sum(L, R) MinZ(L, R)
    4. Покрасить отрезок [L..R] в цвет C
  4. Декартово дерево по неявному ключу [20 минут]
    1. Массив = декартово дерево пар (i, ai)
    2. Пусть мы храним size, перепишем split так, чтобы он вместо x использовал size
    3. Итог: ключ можно не хранить
    4. Новые операции: insert, delete, rotate, swap
    5. Not read Reverse на отрезке
  5. Splay-дерево [если останется время]
    1. Splay: v → root
    2. Add: обычный find + протолкнуть вершину в корень
    3. Merge, Split, Delete через Splay
    4. Малое вращение, два больших вращения -- zig-zig и zig-zag
    5. Выражение больших вращений через малые
    6. Splay: последовательность вращений. Время работы одного Splay = O(depthv)
    7. Основа оценки времени работы: оценка потенциальной функции ∑vlog(size[v])
    8. Формулировки теорем про время работы: Balance, Static Optimiality, Static Finger, Working Set