Деревья поиска (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]