Деревья поиска (4 декабря 2014)

  1. Интерфейсы
    1. HashTable: add, del, find
    2. set<int>: add, del, find, lower_bound, next, prev
    3. BST: add, del, find, lower_bound, next, prev, nth_element, calc_function(L,R)
    4. Дерево по неявному ключу: add(i), del(i), nth_element, calc_function(L, R)
  2. Реализация дерева по неявному ключу на примере недо-AVL [code]
  3. Сравнение различных деревьев
    1. AVL, RB
    2. Treap, Splay − деревья со split и merge: удобно считать функцию на отрезке, в случае неявного ключа можно менять местами куски массива за O(logn)
    3. Splay − статическая оптимальность (элементы, к которым мы часто обращаемся, проталкиваются наверх)
  4. RB-tree
    1. RB-Tree → 2-3-4-tree → 2-3-tree
    2. AA-Tree − версия RB-Tree, в которой красным может быть только правый сын
    3. Добавление в 2-3-Дерево. k-tree − обобщение 2-3-tree (оно же B*-tree).
  5. Персистентные структуры данных
    1. Дерево без overhead
    2. Массив, любая структура с overhead в O(logn) раз
    3. Делаем наше недо-AVL дерево персистентным [code]