Сбалансированные деревья, часть 2

  1. Не сбалансированное дерево
    1. Операция на отрезке L ≤ x ≤ R: сумма x, сумма y, минимум по y.
    2. Как это делать через Split(L, R). Как это делать в AVL.
    3. Операция на отрезке L ≤ x ≤ R: увеличить все y на dy, присвоить всем y некоторое значение y0 (модификация на отрезке, проталкивание информации вниз)
  2. Treap по неявному ключу: rotate(a, a+k, a+n) за O(logn)
  3. Rope (интерфейс) = treap + reverse
  4. Skip-list
  5. Другие деревья
    1. 2-3-tree, k-tree, B-tree
    2. 2-3-4-tree, RB-tree, AA-tree
    3. B-tree, B*-tree, B+-tree, оценка h×log(k) = log(n) для B-tree (find, insert, erase)
    4. Применение RB-tree: set<int>, set<int>::iterator − не меняется
  6. Интерфейсы
    1. Insert, Delete, Find : Хештаблица, BST (STL::unordered_set, STL::set)
    2. Insert, Delete, LowerBound : Сортированный массив + бинарный поиск + пополняемость, BST (STL::set)
    3. Insert, Delete, k-th element : BST (STL::tree)
    4. Rope : Дерево поиска с операциями split/merge + reverse (STL::rope)
  7. Персистентное
    1. В Offline, в online
    2. Garbage Collector
    3. Peristent stack and queue in O(1)
    4. RBST, пересистентное RBST (отличие от treap в том, что мы не храним y)
    5. Применение RBST: решение задачи "memory manager". Запрос "копировать память", обработка за O(logn).
  8. Оптимальность деревьев
    1. Статическая (определение, оптимальное дерево поиска за O(n2))
    2. Аналогия с Хаффменом
    3. Динамическая (определение, Tango Tree)