1. B-tree
1.0 короткое напоминание
1.1 Add
1.2 Delete
1.3 Вариации B-tree (больше ключей, меньше (B*), данные в листьях (B+))
1.4 Определение 2-3-tree, 2-3-4-tree
1.5 Красно-чёрное дерево, связь с 2-3-4-tree, применение в STL, мало памяти
1.6 AA-tree, связь с 2-3-tree.

2. Случайные деревья
2.1 Определение через случайный выбор корня
2.2 Вспоминаем Q.Sort
2.2 Lm: сумма Size_i = сумме depth_v
2.3 Lm: E(depth_v) <= 2 ln(n)
2.4 Другое определение случайного дерева: через add в случайном порядке, эквивалетность
2.5 Утверждение без доказательства: E[max depth_v] <= 4 ln(n) [*]
* На самом деле <= 3 ln(n) + O(1) и есть в домахе

3. Декартово дерево
3.1 Определение декартово дерева.
3.2 Lm: если y = unique, то существует и ровно одно
3.3 Lm: если y = rand, то получили случайное дерево
3.4 Def Treap: Декартово дерево, где y = rand
3.5 Пишем Split и Merge
3.6 Выражаем Add и Delete

4. Персистентные структуры
4.1 BST (уже есть, но больше памяти)
4.2 Массив (как Implicit Key)
4.3 Массив Через "Дерево отрезков"
4.4 Философия: весь мир состоит из массивов
4.5 [Плохо, есть в дз] Персистентизируем любую структуру, например СНМ

5. Персистентные структуры данных: продвинутые
5.1 RBST (замена y-ков)