Splay-дерево: подтягивай то, чем пользуешься

Если ты понимаешь, что splay подтягивает узел в корень после каждого обращения, что это даёт амортизированный (а не гарантированный) O(log n) и эффект «горячих» данных у корня, листай до «Теперь сам».

Как думаешь, что если вообще не следить за балансом

АВЛ и красно-чёрное следят за формой метками; декартово - случайными приоритетами. А можно ли НИЧЕГО не хранить и всё равно быть быстрым? Идея дерзкая: пусть дерево живёт как попало, но каждый раз, когда мы к узлу обратились, будем ПОДТЯГИВАТЬ его наверх, к корню. Зачем? Во-первых, к чему обращаются часто, окажется близко (быстрый повторный доступ). Во-вторых - и это неочевидно - само подтягивание, если делать его особыми ПАРНЫМИ вращениями, распрямляет длинную ветку, по которой мы шли, вдвое укорачивая её. То есть каждая дорогая операция «в глубину» сама себя чинит на будущее. По отдельности операция может быть медленной (O(n)), но в среднем по серии - дешёвой. Это ставка на амортизацию вместо гарантии.

На что это похоже

Стол с бумагами, где действует правило: любую бумагу, которую ты достал, кладёшь СВЕРХУ. Не сортируешь, не раскладываешь по папкам - просто последняя использованная всегда на виду. Со временем то, чем пользуешься часто, само собирается наверху, а забытое тонет вниз. Иногда за редкой бумагой придётся перерыть всю стопку (дорогая операция), но зато частые - под рукой, и в среднем ты тратишь мало. Splay-дерево - такой стол: «достал - положи наверх» вместо аккуратной картотеки. Порядок поддерживается лениво, самой работой.

Механизм: операция splay

Ключевая операция - splay(x): поднять узел x в корень серией вращений. Но не по одному вращению за раз, а ПАРАМИ, по взаимному расположению узла, родителя и деда:

zig    - x - ребёнок корня: одно вращение (крайний случай)
zig-zig - x и родитель с ОДНОЙ стороны (оба левые или оба правые):
          сперва повернуть ДЕДА, потом родителя (два одинаковых поворота)
zig-zag - x и родитель с РАЗНЫХ сторон:
          два разнонаправленных поворота (как двойной поворот АВЛ)

Каждая операция дерева использует splay:

поиск(x):   спуститься к x (или к месту, где он был бы), затем splay(x) - поднять в корень
вставка(x): вставить как в BST, затем splay(x)
удаление(x): splay(x) в корень, убрать корень; склеить два поддерева: splay максимума
             ЛЕВОГО поддерева (у него не будет правого ребёнка) и подвесить к нему правое

Отличие zig-zig от «просто поднять узел по одному» и есть секрет: именно парные повороты в правильном порядке примерно ВДВОЕ сокращают глубину узлов на пройденном пути, а не просто двигают x. Поэтому длинные пути после обращения становятся вдвое короче - дерево само себя выравнивает в процессе работы.

Правило

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

Разбор: почему амортизированно O(log n), хотя одна операция может быть O(n)

Здесь работает та же идея амортизации, что у растущего массива и хеш-таблицы (разделы про списки и хеширование): смотрим не на одну операцию, а на СЕРИЮ. Дорогая операция - спуск по длинной ветке (O(n)) - кажется провалом, но splay попутно РАСПРЯМЛЯЕТ эту ветку: парные повороты zig-zig укорачивают глубину всех пройденных узлов примерно вдвое. Значит после дорогой операции дерево стало заметно ровнее, и следующие операции - дешевле. Дорогая операция «оплачивает» своё разорение тем, что улучшает дерево на будущее. Строгий анализ (метод потенциала) показывает: сумма цен любой серии из m операций - O(m·log n), то есть в среднем O(log n) на операцию. Это НЕ означает, что каждая операция быстрая: конкретный поиск может быть O(n). Гарантия - на серию, а не на штуку. Для большинства применений этого достаточно, но там, где важна предсказуемость КАЖДОЙ операции (реального времени), splay не годится - как и хеш-таблица с её рехешированием.

Разбор: почему splay сам ускоряет «горячие» данные

Побочный эффект правила «поднимай в корень» - бесплатный кеш. Раз обратился к ключу - он у корня; обратился к нему снова через пару операций - он всё ещё близко к верху, поиск почти мгновенный. Если запросы НЕРАВНОМЕРНЫ (небольшой набор ключей запрашивают часто, остальные редко - а так почти всегда в реальных данных), splay-дерево само собирает «горячие» ключи у корня и обслуживает их быстрее, чем любое сбалансированное дерево с фиксированной формой. Более того, есть теорема: на любой последовательности запросов splay-дерево работает не намного хуже, чем ЛУЧШЕЕ возможное статическое дерево под эту последовательность (свойство статической оптимальности). То есть оно подстраивается под шаблон доступа без всякого знания о нём заранее. Это уникально: АВЛ и красно-чёрное держат форму независимо от того, что и как часто спрашивают, а splay - лениво адаптируется под нагрузку. Цена адаптации - перестройка при каждом чтении.

Что ломается без этого

Первая ошибка - поднимать узел «по одному вращению» вместо парных splay-шагов: тогда амортизация ломается - без zig-zig путь не распрямляется вдвое, и дерево может остаться вытянутым (известный контрпример для наивного «поднятия к корню»). Правильны именно парные повороты. Вторая - считать, что splay даёт O(log n) на КАЖДУЮ операцию: нет, только амортизированно; отдельная может быть O(n). Третья - применять splay там, где важна предсказуемая задержка каждой операции (реальное время, параллельный доступ): перестройка при чтении и разброс цен операций этому мешают. Четвёртая - забыть, что ПОИСК меняет дерево: два потока, читающие splay-дерево одновременно, конфликтуют (оба его пишут) - для конкурентного доступа он неудобен.

Зачем это в работе

Splay-деревья применяют там, где доступ НЕРАВНОМЕРЕН и хочется автоматической подстройки под «горячие» данные без ручной настройки: кеши, аллокаторы памяти, некоторые сетевые таблицы, представление изменяемых последовательностей (splay поверх «дерева по позиции»). Их любят за предельную ПРОСТОТУ - никаких меток, вся логика в одной операции splay - и за уникальное свойство самоадаптации под шаблон запросов. Но понимать надо и границы: амортизированная (не гарантированная) оценка и перестройка-при-чтении делают splay плохим выбором для реального времени и конкурентного доступа - там берут АВЛ/красно-чёрное. Для курса splay - третий облик одной идеи «баланс без явного контроля формы»: декартово дерево доверяет случайности, splay - амортизации и адаптации, а списки с пропусками (следующий урок) - снова случайности, но уже без дерева вовсе. Все они показывают, что «держать O(log n)» можно очень разными средствами, и выбор - вопрос того, что важнее: гарантия, простота или адаптивность.

Теперь сам

К splay-дереву обратились с поиском ключа, лежавшего глубоко в листе. Что произойдёт с этим ключом и с деревом сразу после поиска, и почему следующий поиск ТОГО ЖЕ ключа будет очень быстрым?