Деревья поиска (10 апреля 2018)

  1. BST
    1. Определение, хранение, find, add, симметричный обход, next, del.
    2. Обработка равных ключей (сделать разными, хранить в вершине count/list, ≤ и >)
    3. Добавляем возможности списка (прошивка, предыдущий и следующий за O(1))
    4. Добавляем возможности хеш-таблицы (find и del за O(1)). Удаление через ленивость.
    5. Пишем код next. Итератор в set.
    6. Пишем 3 версии добавления (обычная, персистентная, указатели).
    7. [skipped] [практика] Прямой обход

  2. AVL
    1. Определение, ограничение на высоту, малые и большие вращения (single/double)
    2. Перебалансировка после add, доказательство леммы "не более одного вращения на add"
− Перерыв −
  1. Дерево по неявному ключу
    1. Поддержка размеров поддеревьев. Новые запросы: getIndex(x), getValue(i), insert(i, x).
    2. Неявный ключ, массив с операциями insert(i, x), erase(i), get(i), set(i, x) за O(logn).

  2. Другие деревья
    1. B-tree, 2-3-tree
    2. B*-tree, B+-tree, оценка h×log(k) = log(n) для B-tree (find, insert, erase)
    3. 2-3-4-tree, RB-tree, AA-tree
    4. Применение B-tree (диск) и RB-tree (set)

  3. [skipped] [практика] Операции на отрезке в дереве по неявному ключу со split и merge
    1. [skipped] [практика] Sum, Min, +=, =, reverse
    2. [skipped] [практика] rotate(a, a+k, a+n) за O(logn)