Деревья поиска (9 апреля 2021)

1. BST
   1. Определение, хранение
   2. find, add, время работы = глубина
   3. Симметричный обход и сортировка. Нижняя оценка через сортировку.
   4. Обработка равных ключей (сделать разными, хранить в вершине count/list, ≤ и <)
   5. next, prev, применение, как итератор в set.
   6. Добавляем возможности списка (прошивка, предыдущий и следующий за O(1))
   7. Добавляем возможности хеш-таблицы (find за O(1)).
   8. Удаление через ленивость (del = find + O(1))
   9. Честный del за O(глубины)
   10. Пишем 3 версии добавления (обычная, персистентная, указатели).
   11. [skipped] [практика] Прямой обход
   
   
2. AVL (1962 Adelson-Velsky and Landis)
   1. Определение, ограничение на высоту, связь высоты и размера
   2. Малые и большие вращения (single/double). Большое через два малых.
   3. Перебалансировка после add
   4. Доказательство леммы "не более одного вращения на add"
   5. [skipped] [практика] del, merge, split

1. Дерево по неявному ключу
   1. Поддержка размеров поддеревьев.
   2. Новые запросы (всё ешё явный ключ): getIndex(x), getValue(i), insert(i, x).
   3. STL : pbds::tree. Почему такое не умеет set?
   4. Неявный ключ, массив с операциями insert(i, x), erase(i), get(i), set(i, x) за O(logn).
   5. STL : rope
   
   
2. Другие деревья
   1. B-tree : мотивация про жёсткий диск, добавление, время работы
   2. Оценка log_k(n)×log(k) = log(n) для B-tree (find, insert, erase). Число обращений к диску = log_k.
   3. B^*-tree, B⁺-tree − храним не массив, а дерево, храним ключи и в промежуточных вершинах тоже.
   4. 2-3-tree
   5. 2-3-4-tree, RB-tree, AA-tree : применение AA-tree (set)
   
   
3. [skipped] [практика] Операции на отрезке в дереве по неявному ключу со split и merge
   1. [skipped] [практика] Sum, Min, +=, =, reverse
   2. [skipped] [практика] rotate(a, a+k, a+n) за O(logn)