Семинар по алгоритмам и структурам данных ФКН "Вероятностная структура данных Zip-дерево"

17 декабря 2024 в 18:10

Докладчик: Игорь Мамай, ФКН НИУ ВШЭ

Тема: Вероятностная структура данных Zip-дерево

Аннотация: Самобалансирующиеся двоичные деревья поиска занимают важное место среди структур данных, так как позволяют эффективно реализовать различные алгоритмы сортировки и поиска. Также с их помощью можно эффективно реализовать такие абстрактные типы данных, как множество и ассоциативный массив.

Начиная с 1960-х годов, были предложены различные способы балансировки двоичного дерева поиска, и сегодня нам известны такие структуры данных, как АВЛ-дерево (1962), B-дерево (1970), Красно-чёрное дерево (1978), Splay-дерево (1985) и так далее. Также были предложены рандомизированные способы балансировки двоичного дерева поиска, и самым известным из них является Декартово дерево (1989).

При этом в 1989 году появилась вероятностная структура данных Skip List, в основе которой лежит определенная иерархия односвязных списков с дополнительными связями. Эта структура данных не является двоичным деревом поиска, но позволяет выполнять те же задачи. Преимуществами Skip List являются простота реализации и возможность параллельной работы с ключами.

Естественно, возникает вопрос, дает ли Skip List принципиально новые возможности в сравнении с самобалансирующимися деревьями поиска. Ответ на этот вопрос позже был получен. В 2007 году было построено отображение, преобразующее Skip List в двоичное дерево поиска. А затем в 2021 году было предложено новое вероятностное двоичное дерево поиска Zip-дерево, которое обладает естественным изоморфизмом со структурой данных Skip List.

На семинаре мы пройдем весь путь от Skip List до Zip-дерева, посмотрим на изоморфизм между ними, а также проведем сравнение Zip-дерева с Декартовым деревом.

Место проведения: Покровский бульвар 11, аудитория D108