Семинар 11. Дерево поиска с неявным ключом

Сравнение дерева поиска и дерева отрезков. Выделение отрезка при помощи Split/Join. Неявный ключ = номер в обходе. Хранение количества вершин в поддереве. Хранение дополнительной информации о поддереве и запросы на отрезке, функция Update. Хранение отложенных модификаций и модификации на отрезке, функция Actualize.

Использование указателя на вершину в качестве ручки. Определение ручки по номеру. Определение номера по ручке и хранение отцов вершин.

Реализация функции Split (код/алгоритм) для Treap. Нулевой указатель = пустое дерево.

Примеры. Дерево отрезков {+=, min(a)}. Набор строк с разрезанием и конкатенацией. Операции развернуть отрезок: реализация через два дерева и через отложенные модификации.

Задача про изоморфное упорядоченное дерево со Всесибирской 2012 года (задача 9). Представление дерева в виде правильной скобочной последовательности, хранение ПСП в дереве поиска с неявным ключом. Выполнение операций изменения и ручки. Полиномиальный хеш и совпадение ПСП, поддержка хеша в качестве статистики. Время работы. Разрешение коллизий.

Видео для студентов заочного отделения: https://my.compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4401/