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

Сравнение дерева поиска и дерева отрезков. Отличия: ключ = номер и операции на отрезке.

Неявный ключ = номер в обходе. Реализация Split и Join. Хранение количества вершин в поддереве. Пустое дерево: нулевой указатель / sentinel.

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

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

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

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