Конспект: декартово, splay и списки с пропусками

Понятия

Декартово дерево (treap) - BST по ключу + куча по СЛУЧАЙНОМУ приоритету (родитель выше детей). Пара свойств задаёт форму ОДНОЗНАЧНО (зависит только от приоритетов, не от порядка данных). Случайные приоритеты → форма как у случайного BST → высота O(log n) в ОЖИДАНИИ. Балансируют вращениями, но запускает их приоритет, не подсчёт высот. Прост, есть SPLIT/MERGE.

Splay-дерево - без меток; после КАЖДОГО обращения узел подтягивается в корень (splay - парные вращения zig-zig/zig-zag, распрямляющие путь вдвое). АМОРТИЗИРОВАННО O(log n) (на серию, не на операцию), плюс кеш: «горячие» ключи у корня, адаптация к нагрузке. Минус - пишет при чтении, нет гарантии на одну операцию.

Список с пропусками (skip list) - «дерево без дерева»: этажи отсортированных списков, нижний со всеми элементами, верхние - случайные разрежённые выборки. Уровень узла - по МОНЕТКЕ (на уровень k с вероятностью 1/2^k) → O(log n) этажей и операций в ОЖИДАНИИ. Прост, удобен для ПАРАЛЛЕЛИЗМА.

Дерево ван Эмде Боаса - для целых 0..U−1: √U кластеров-поддеревьев, сводка непустых кластеров, min и max в узле (min в кластер не кладётся). Поиск следующего и вставка - O(log log U).

Что унести

Три способа держать O(log n) БЕЗ явных правил баланса - через случайность или амортизацию.

Главная мысль: O(log n) достижимо многими непохожими средствами, и выбор диктуют ВТОРИЧНЫЕ требования: нужна ли гарантия худшего случая (тогда АВЛ/КЧ) или хватит ожидания/ амортизации (тогда проще - treap, skip list, splay); важна ли адаптация к «горячим» данным (splay); важен ли параллельный доступ (skip list); хочется ли минимум кода (treap, skip list). Это тот же приём «случайность вместо детерминированной машинерии», что в quickselect и универсальном хешировании, - но применённый к балансировке дерева.

Граница log n для поиска следующего - только для сравнений. Целые ключи из известного диапазона дают O(log log U): размер задачи падает с u до √u, и спуск на уровне один - в кластер или в сводку. Для 64-битных ключей - 6 уровней.

Ловушки джокера

Приоритеты treap не случайны (по порядку/по ключу) - защита пропадает, возможно вырождение.

Наивное «поднятие по одному» вместо парного splay - без zig-zig путь не распрямляется, амортизация ломается.

Считать splay/treap/skip list гарантией O(log n) на операцию - это ожидание (treap, skip list) или амортизация (splay). Гарантия - у АВЛ/КЧ.

Splay в реальном времени / при параллельном чтении - пишет при чтении, разброс цен операций.

Уровни skip list не случайны - дорого поддерживать при вставках, теряется простота.

Поиск в skip list не сверху - без спуска с разрежённых этажей это обычный проход O(n).

Положил min в кластер. Вставка в пустой кластер спускается дважды, и O(log log U) превращается в O(log U).

Проверь себя

Как декартово дерево использует случайные приоритеты и почему это даёт O(log n) в ожидании?

Что делает splay после обращения и какая у него гарантия (амортизация против гарантии)?

Как устроен список с пропусками и почему у него O(log n) этажей?

Что общего у всех трёх и чем они отличаются от АВЛ/красно-чёрного?

Когда какую структуру выбрать - по гарантии, простоте, адаптивности, параллелизму?

Почему дерево ван Эмде Боаса тратит log log U шагов и что для этого нужно хранить в узле отдельно?