Splay-дерево

TL;DR

Splay-дерево (splay tree; «расширяющееся дерево») — саморегулирующееся (self-adjusting) двоичное дерево поиска, которое не хранит никакой информации о балансе. После каждого обращения к узлу он переносится в корень операцией splay (последовательностью поворотов zig, zig-zig, zig-zag). Дерево самоподстраивается: часто запрашиваемые узлы оказываются вверху. Все операции — поиск, вставка, удаление, а также Split и Join — амортизированно выполняются за [math]\displaystyle{ O(\log n) }[/math], при этом гарантируется только амортизированная оценка: отдельная операция может стоить [math]\displaystyle{ O(n) }[/math]. Splay-дерево обладает свойствами адаптивности (лемма о доступе, рабочее множество, статический палец; динамический палец доказан отдельно, в 2000 году) и лежит в основе link-cut trees. Изобретено Слейтором и Тарджаном в 1985 году.

Инфобокс

Свойство	Значение
Класс	Саморегулирующееся двоичное дерево поиска (BST)
Изобретение	Слейтор и Тарджан, 1985 [2]
Отличительная черта	Нет полей баланса; узел переносится в корень при каждом доступе
Поиск (амортизированный)	[math]\displaystyle{ O(\log n) }[/math]; отдельная операция — до [math]\displaystyle{ O(n) }[/math]
Вставка / удаление	[math]\displaystyle{ O(\log n) }[/math] амортизированно
Split / Join	[math]\displaystyle{ O(\log n) }[/math] амортизированно
Min / Max, соседние	[math]\displaystyle{ O(\log n) }[/math] амортизированно (если найденный узел сплайнится)
Память	[math]\displaystyle{ O(n) }[/math]; на узел — key, left, right, parent
Адаптивность	Да: лемма о доступе, рабочее множество, статический палец; динамический палец — отдельная теорема [7]
Наихудшая гарантия	Амортизированная, а не на отдельную операцию (не для реального времени)
Альтернативы	АВЛ-дерево (план), красно-чёрное дерево (план), treap, link-cut trees
Где встречается	link-cut trees, модели кэша с локальностью, динамическая связность, структуры последовательностей

Определения

Splay-дерево — двоичное дерево поиска (BST), в котором после каждого доступа к узлу [math]\displaystyle{ x }[/math] выполняется операция splay([math]\displaystyle{ x }[/math]), переносящая [math]\displaystyle{ x }[/math] в корень последовательностью поворотов вдоль пути доступа [2]. Никаких полей высоты/баланса/цвета дерево не хранит.

Операция splay([math]\displaystyle{ x }[/math]). Пока [math]\displaystyle{ x }[/math] не корень, применяется один из трёх случаев (через [math]\displaystyle{ p }[/math] — родителя, [math]\displaystyle{ g }[/math] — деда [math]\displaystyle{ x }[/math]):

• zig — [math]\displaystyle{ p }[/math] является корнем: одиночный поворот, поднимающий [math]\displaystyle{ x }[/math].
• zig-zig — [math]\displaystyle{ x }[/math] и [math]\displaystyle{ p }[/math] оба левые (или оба правые) дети: сначала поворот вокруг [math]\displaystyle{ p }[/math], затем вокруг [math]\displaystyle{ x }[/math].
• zig-zag — [math]\displaystyle{ x }[/math] — правый ребёнок левого [math]\displaystyle{ p }[/math] (или наоборот): два поворота вокруг [math]\displaystyle{ x }[/math] подряд (это двойной поворот, как в АВЛ-дереве).

Поворот (rotation) — локальная перестройка, поднимающая узел над его родителем за [math]\displaystyle{ O(1) }[/math] с сохранением порядка ключей (см. авл-дерево (план)).

Саморегулирующееся дерево (self-adjusting tree) — двоичное дерево поиска, форма которого определяется историей обращений, а не поддерживаемым инвариантом баланса. Формально: структура саморегулирующаяся, если последовательность операций над ней имеет оценку, зависящую от потока запросов (например, от рабочего множества), при том что высота в отдельный момент не ограничена.

Ключевое свойство. Splay-дерево — пример саморегулирующейся структуры: его форма зависит не только от множества ключей, но и от порядка обращений к ним. Частые обращения «всплывают» узлы наверх, ускоряя последующие к ним доступы.

Обозначения. [math]\displaystyle{ n }[/math] — число узлов, [math]\displaystyle{ m }[/math] — число операций; [math]\displaystyle{ h }[/math] — текущая высота дерева; [math]\displaystyle{ \log }[/math] — двоичный; size(v) — число узлов в поддереве с корнем [math]\displaystyle{ v }[/math]; веса [math]\displaystyle{ w(v) \gt 0 }[/math] и [math]\displaystyle{ W = \sum_v w(v) }[/math] — для анализа адаптивности.

Рис. 1. Доступ к x = 10: после splay узел x становится корнем, а прежние предки образуют правую ветвь; множество ключей не меняется.

Мотивация и интуиция

Сбалансированные деревья (АВЛ (план), КЧ (план)) держат высоту [math]\displaystyle{ O(\log n) }[/math] и дают гарантию на каждую операцию, но платят за это хранением баланса и постоянной перебалансировкой. Однако во многих реальных нагрузках обращения неравномерны: одни ключи запрашиваются часто, другие почти никогда («горячие» и «холодные»). Для таких нагрузок полезна структура, которая меняет форму под поток запросов.

Splay-дерево делает это радикально просто: любой доступ «подтягивает» нужный узел к корню. Часто используемые элементы постепенно оказываются вверху и ищутся быстро. При этом не хранится ни баланс, ни приоритеты — вся адаптация встроена в операцию splay.

Интуиция «почему это не разваливается»: повороты сжимают длинные пути. Хотя один доступ к глубокому узлу дорог, серия обращений в сумме не может часто обращаться к глубоким узлам — каждый дорогой splay выпрямляет путь и облегчает будущие обращения. Формализует это метод потенциала: потенциал [math]\displaystyle{ \Phi = \sum_v \log_2 \text{size}(v) }[/math], где [math]\displaystyle{ \text{size}(v) }[/math] — число узлов в поддереве с корнем [math]\displaystyle{ v }[/math]. Дорогая операция оплачивается потенциалом, накопленным ранее; для каждого поворота амортизированная стоимость ограничена изменением потенциала поддерева с корнем [math]\displaystyle{ x }[/math]. Отсюда амортизированное [math]\displaystyle{ O(\log n) }[/math] и более сильные адаптивные оценки.

Устройство

Splay-дерево — это обычное BST с тремя ссылками на узел (left, right, parent), но без полей баланса. Вся механика — в операции splay, которая вызывается после каждого доступа (см. рис. 1). Ссылка на родителя нужна, чтобы подниматься по пути доступа.

Три случая splay реализуют разную геометрию:

• zig (родитель у корня) — один поворот;
• zig-zig (оба ребёнка в одну сторону) — два поворота, сначала вокруг родителя;
• zig-zag (зигзаг) — двойной поворот вокруг [math]\displaystyle{ x }[/math].

Порядок поворотов в zig-zig важен: наивное «покорное» вращение [math]\displaystyle{ x }[/math] к корню даёт худшую амортизированную оценку; именно комбинация zig-zig/zig-zag обеспечивает сжатие путей и все адаптивные свойства.

Операции и алгоритмы

Операция: splay

Идея. Поднимать [math]\displaystyle{ x }[/math] к корню, разбирая случаи zig, zig-zig, zig-zag.

Пошаговое описание.

1. Пока у [math]\displaystyle{ x }[/math] есть родитель [math]\displaystyle{ p }[/math]:
2. если [math]\displaystyle{ p }[/math] — корень: один поворот (zig).
3. иначе если [math]\displaystyle{ x }[/math] и [math]\displaystyle{ p }[/math] — дети в одну сторону: повернуть [math]\displaystyle{ p }[/math], затем [math]\displaystyle{ x }[/math] (zig-zig).
4. иначе: два поворота вокруг [math]\displaystyle{ x }[/math] (zig-zag).

Инвариант. Перед каждой итерацией путь от [math]\displaystyle{ x }[/math] до корня — корректный список предков, а BST-свойство выполнено. После каждого поворота BST-свойство сохраняется, ссылки parent согласованы с left/right, и глубина [math]\displaystyle{ x }[/math] уменьшается минимум на 1. По завершении [math]\displaystyle{ x }[/math] — корень.

Псевдокод.

Алгоритм Splay(T, x)
Вход:  BST T; x — существующий узел дерева T (x ≠ NIL)
Выход: x — корень T; порядок ключей и ссылки parent сохранены
Инвариант: путь x → parent[x] → … → корень корректен; после каждой итерации
           глубина x уменьшается минимум на 1

1  while parent[x] ≠ NIL
2      p ← parent[x]
3      g ← parent[p]
4      if g = NIL
5          Rotate(x)                       # zig
6      else if (left[g] = p) = (left[p] = x)
7          Rotate(p)                       # zig-zig: сначала родитель
8          Rotate(x)
9      else
10         Rotate(x)                       # zig-zag: дважды x
11         Rotate(x)

Сложность: O(h) в худшем случае, O(log n) амортизированно; память O(1).
Корректность: каждый поворот сохраняет порядок ключей; цикл поднимает x на
каждой итерации минимум на один уровень, поэтому завершается у корня.

Разбор. Пусть [math]\displaystyle{ x }[/math] — левый ребёнок [math]\displaystyle{ p }[/math], а [math]\displaystyle{ p }[/math] — левый ребёнок [math]\displaystyle{ g }[/math] (zig-zig). Первый поворот (Rotate(p)) поднимает [math]\displaystyle{ p }[/math] над [math]\displaystyle{ g }[/math]: [math]\displaystyle{ x }[/math] остаётся левым ребёнком [math]\displaystyle{ p }[/math]. Второй поворот (Rotate(x)) поднимает [math]\displaystyle{ x }[/math] над [math]\displaystyle{ p }[/math]. В итоге [math]\displaystyle{ x }[/math] — корень поддерева, содержащего [math]\displaystyle{ x }[/math], [math]\displaystyle{ p }[/math] и [math]\displaystyle{ g }[/math] (вместе с их поддеревьями), а [math]\displaystyle{ g }[/math] и [math]\displaystyle{ p }[/math] образуют правую ветвь.

Сложность. Время: [math]\displaystyle{ O(h) }[/math] в худшем случае, [math]\displaystyle{ O(\log n) }[/math] амортизированно. Память: [math]\displaystyle{ O(1) }[/math]. Обоснование: каждый поворот стоит [math]\displaystyle{ O(1) }[/math], поворотов не больше [math]\displaystyle{ h }[/math]; амортизированная оценка следует из теоремы 2 (см. «Корректность и оценка сложности»).

Крайние случаи. [math]\displaystyle{ x }[/math] уже корень — цикл не выполняется. У [math]\displaystyle{ x }[/math] нет деда — один поворот zig. [math]\displaystyle{ x }[/math] = NIL — операция не определена: вызывающий обязан передать существующий узел.

Рисунок. См. рис. 2 (zig-zig) и рис. 3 (zig-zag).

Рис. 2. Zig-zig: x и p — левые дети. Поворот вокруг p, затем вокруг x; x поднимается над дедом g.

Рис. 3. Zig-zag: x — правый ребёнок левого p. Два поворота вокруг x поднимают его над дедом g.

Операция: поиск (Search)

Идея. Спуск как в BST; нашедший узел сплайнится к корню. Если ключа нет, к корню поднимается последний посещённый узел (это важно для адаптивности).

Пошаговое описание.

1. Начать с корня; запоминать каждый посещённый узел в last.
2. Спускаться влево или вправо по сравнению [math]\displaystyle{ k }[/math] с key[cur].
3. При совпадении — Splay(cur) и вернуть узел.
4. При достижении NIL — Splay(last), если дерево непусто, и вернуть NIL.

Инвариант. На каждом шаге в поддереве с корнем cur ключ [math]\displaystyle{ k }[/math] ищется по BST-свойству: все ключи слева меньше key[cur], все ключи справа — не меньше. last — последний посещённый узел (NIL только для пустого дерева).

Псевдокод.

Алгоритм Search(T, k)
Вход:  BST T (возможно пустое); ключ k
Выход: узел с ключом k (он же — корень T) либо NIL
Инвариант: в поддереве с корнем cur ключ k ищется по BST-свойству;
           last — последний посещённый узел (NIL только если T пусто)

1  cur ← root[T];  last ← NIL
2  while cur ≠ NIL
3      last ← cur
4      if k = key[cur]
5          Splay(T, cur)
6          return cur
7      else if k < key[cur]
8          cur ← left[cur]
9      else
10         cur ← right[cur]
11 if last ≠ NIL
12     Splay(T, last)                     # ключа нет: в корень — последний посещённый
13 return NIL

Сложность: O(h) в худшем случае, O(log n) амортизированно; память O(1).
Корректность: спуск находит узел по BST-свойству; splay сохраняет множество и
порядок ключей, поэтому после вызова найденный (или последний посещённый) узел
стоит в корне.

Разбор. Поиск 15 в дереве 20(10(5, ·), 30(25, 35)): [math]\displaystyle{ 15 }[/math] меньше [math]\displaystyle{ 20 }[/math] — влево к 10; [math]\displaystyle{ 15 }[/math] больше [math]\displaystyle{ 10 }[/math] — вправо, right[10] = NIL. Ключа нет, Splay(10) делает 10 корнем: 10(5, 20(·, 30(25, 35))). Повторный поиск 15 снова дойдёт до 10 за два сравнения — спуск не удлинился.

Сложность. Время: [math]\displaystyle{ O(h) }[/math] в худшем случае, [math]\displaystyle{ O(\log n) }[/math] амортизированно. Память: [math]\displaystyle{ O(1) }[/math]. Обоснование: спуск стоит [math]\displaystyle{ O(h) }[/math], splay — амортизированно [math]\displaystyle{ O(\log n) }[/math] (теорема 2).

Крайние случаи. Пустое дерево — цикл не выполняется, last = NIL, splay не вызывается. Ключ отсутствует — splay последнего посещённого узла, возврат NIL. Ключ в корне — один вызов splay без поворотов.

Операция: вставка (Insert)

Идея. Спуск до места вставки, подключение листа и splay нового узла к корню.

Пошаговое описание.

1. Спускаться от корня, запоминая родителя par.
2. При совпадении ключа — Splay(cur) и выход: дубликат не добавляется.
3. Создать узел [math]\displaystyle{ x }[/math], подключить его к par (или сделать корнем, если дерево пусто).
4. Splay(x) — новый узел становится корнем.

Инвариант. До подключения par — родитель будущего узла, а спуск сохраняет BST-свойство. После подключения ссылки left/right/parent согласованы; после splay [math]\displaystyle{ x }[/math] — корень.

Псевдокод.

Алгоритм Insert(T, k)
Вход:  BST T (возможно пустое); ключ k
Выход: T с ключом k; узел с ключом k — корень T
Инвариант: par — родитель будущего узла; спуск сохраняет BST-свойство;
           после подключения x ссылки left/right/parent согласованы

1  cur ← root[T];  par ← NIL
2  while cur ≠ NIL
3      par ← cur
4      if k = key[cur]
5          Splay(T, cur);  return           # дубликат: ключ уже есть
6      else if k < key[cur]  cur ← left[cur]
7      else                  cur ← right[cur]
8  x ← новый узел с ключом k
9  parent[x] ← par
10 if par = NIL            root[T] ← x      # T было пустым
11 else if k < key[par]    left[par] ← x
12 else                    right[par] ← x
13 Splay(T, x)

Сложность: O(h) в худшем случае, O(log n) амортизированно; память O(1)
плюс O(1) на новый узел.
Корректность: x подключён на место пустого указателя, поэтому BST-свойство
сохранено; splay переносит x в корень и не меняет порядок ключей.

Разбор. Вставка 15 в 10(·, 20(·, 30)). Спуск: [math]\displaystyle{ 15 }[/math] больше [math]\displaystyle{ 10 }[/math] — вправо к 20; [math]\displaystyle{ 15 }[/math] меньше [math]\displaystyle{ 20 }[/math] — влево, left[20] = NIL. Узел 15 подключён слева от 20; 15 — левый ребёнок 20, а 20 — правый ребёнок 10, то есть направления разные, поэтому выполняется zig-zag: два поворота вокруг 15. Итог — 15(10, 20(·, 30)); порядок ключей сохранён.

Сложность. Время: [math]\displaystyle{ O(h) }[/math] в худшем случае, [math]\displaystyle{ O(\log n) }[/math] амортизированно; память [math]\displaystyle{ O(1) }[/math] плюс узел. Обоснование: спуск [math]\displaystyle{ O(h) }[/math], один splay, амортизированно [math]\displaystyle{ O(\log n) }[/math].

Крайние случаи. Пустое дерево — новый узел сразу корень, splay не нужен. Дубликат — ключ не добавляется, но существующий узел сплайнится. Вставка в лист вырожденного дерева — [math]\displaystyle{ O(n) }[/math] на отдельной операции, амортизированно [math]\displaystyle{ O(\log n) }[/math].

Операция: удаление (Delete)

Идея. Сплайнить удаляемый ключ к корню, отсоединить левое и правое поддеревья, сшить их, подняв максимум левого поддерева.

Пошаговое описание.

1. Если дерево пусто или ключа нет — выйти.
2. Search(T, k) сплайнит [math]\displaystyle{ k }[/math] в корень.
3. Запомнить левое поддерево [math]\displaystyle{ L }[/math] и правое [math]\displaystyle{ R }[/math], обнулив у них ссылки parent.
4. Удалить корень; если [math]\displaystyle{ L }[/math] пусто — корнем становится [math]\displaystyle{ R }[/math].
5. Иначе корень — [math]\displaystyle{ L }[/math], найти в нём максимум [math]\displaystyle{ m }[/math], Splay(m) и прицепить [math]\displaystyle{ R }[/math] справа.

Инвариант. После шага 2 ключ [math]\displaystyle{ k }[/math] — в корне, поэтому все ключи [math]\displaystyle{ L }[/math] меньше [math]\displaystyle{ k }[/math], а все ключи [math]\displaystyle{ R }[/math] больше. В [math]\displaystyle{ L }[/math] максимум [math]\displaystyle{ m }[/math] — наибольший ключ, поэтому после splay у него нет правого ребёнка и место справа свободно.

Псевдокод.

Алгоритм Delete(T, k)
Вход:  BST T (возможно пустое); ключ k
Выход: T без узла с ключом k (если он был); корень — NIL или узел T
Инвариант: после Search ключ k — в корне; все ключи L < k < всех ключей R;
           m — максимум L, поэтому right[m] = NIL

1  if root[T] = NIL
2      return                              # пустое дерево
3  if Search(T, k) = NIL
4      return                              # ключа нет
5  L ← left[root[T]];  R ← right[root[T]]  # k теперь в корне
6  if L ≠ NIL  parent[L] ← NIL
7  if R ≠ NIL  parent[R] ← NIL
8  удалить корень
9  if L = NIL   root[T] ← R;  return
10 root[T] ← L
11 m ← максимум поддерева L               # правый спуск
12 Splay(T, m)                            # m — корень левого поддерева
13 right[m] ← R
14 if R ≠ NIL  parent[R] ← m

Сложность: O(h) в худшем случае, O(log n) амортизированно; память O(1).
Корректность: в L все ключи < k < ключей R, а m — максимум L, поэтому
right[m] = NIL и прицепление R справа сохраняет BST-свойство.

Разбор. Удаление 20 из 20(10(5, 15), 30). Search(20) не делает поворотов: 20 уже корень. [math]\displaystyle{ L = 10(5, 15) }[/math], [math]\displaystyle{ R = 30 }[/math]. Максимум [math]\displaystyle{ L }[/math] — 15; Splay(15) в [math]\displaystyle{ L }[/math] даёт 15(10(5), ·). Прицепляем [math]\displaystyle{ R }[/math] справа: 15(10(5, ·), 30). Порядок ключей сохранён.

Сложность. Время: [math]\displaystyle{ O(h) }[/math] в худшем случае, [math]\displaystyle{ O(\log n) }[/math] амортизированно. Память: [math]\displaystyle{ O(1) }[/math]. Обоснование: один поиск и один splay, каждый амортизированно [math]\displaystyle{ O(\log n) }[/math]; спуск к максимуму оплачивается тем же splay.

Крайние случаи. Пустое дерево — выход по шагу 1. Ключа нет — выход по шагу 3 (но splay последнего посещённого уже выполнен). У корня нет левого поддерева — корнем становится [math]\displaystyle{ R }[/math]. У корня нет правого поддерева — корнем становится максимум [math]\displaystyle{ L }[/math]: Splay поднимает его, и он остаётся корнем. Единственный узел — дерево становится пустым.

Операции: разделение и слияние (Split и Join)

Идея. Splay делает эти операции естественными, потому что корень делит ключи на «меньше» и «не меньше».

• Split([math]\displaystyle{ T, k }[/math]): Search(T, k) сплайнит к корню ключ [math]\displaystyle{ k }[/math], а если его нет — последний посещённый узел; затем дерево разрезается по сравнению key[root] с [math]\displaystyle{ k }[/math]: левое поддерево — ключи меньше [math]\displaystyle{ k }[/math], правое — ключи не меньше [math]\displaystyle{ k }[/math].
• Join([math]\displaystyle{ T_1, T_2 }[/math]) (все ключи [math]\displaystyle{ T_1 }[/math] меньше ключей [math]\displaystyle{ T_2 }[/math]): Splay максимум [math]\displaystyle{ T_1 }[/math] к корню, прицепить [math]\displaystyle{ T_2 }[/math] правым ребёнком.

Разрез нельзя делать безусловно по левому поддереву корня: при отсутствующем [math]\displaystyle{ k }[/math] Search сплайнит последний посещённый узел [math]\displaystyle{ r }[/math], и он может быть как меньше, так и больше [math]\displaystyle{ k }[/math]. Если key[r] меньше [math]\displaystyle{ k }[/math], то [math]\displaystyle{ r }[/math] и его левое поддерево целиком уходят в [math]\displaystyle{ L }[/math], а в [math]\displaystyle{ R }[/math] — только right[r]; если key[r] не меньше [math]\displaystyle{ k }[/math] — наоборот. Пример: ключи 10, 20, 30, [math]\displaystyle{ k = 15 }[/math]. Search(15) не находит ключ и сплайнит 10, после чего дерево имеет вид 10(·, 20(·, 30)). Так как key[r] = 10 меньше 15, получаем [math]\displaystyle{ L = \{10\} }[/math] и [math]\displaystyle{ R = \{20, 30\} }[/math].

Алгоритм Split(T, k)                      # возвращает (L, R): ключи L < k ≤ ключи R
Вход:  BST T (возможно пустое); ключ k (может отсутствовать в T)
Выход: (L, R) — два BST; все ключи L < k, все ключи R ≥ k
Инвариант: после Search в корне r стоит либо k, либо последний посещённый узел;
           left[r] содержит только ключи < key[r], right[r] — только ≥ key[r]

1  if root[T] = NIL
2      return (NIL, NIL)
3  Search(T, k)                            # в корне — k или последний посещённый
4  r ← root[T]
5  if key[r] < k
6      L ← r;  R ← right[r]
7      right[r] ← NIL
8  else
9      R ← r;  L ← left[r]
10     left[r] ← NIL
11 if L ≠ NIL  parent[L] ← NIL
12 if R ≠ NIL  parent[R] ← NIL
13 return (L, R)

Алгоритм Join(T1, T2)
Вход:  два BST T1, T2; все ключи T1 < всех ключей T2 (любое из деревьев может быть пустым)
Выход: BST из всех ключей T1 и T2
Инвариант: m — максимум T1, поэтому right[m] = NIL и место справа свободно

1  if T1 = NIL  return T2
2  m ← максимум T1                        # правый спуск
3  Splay(T1, m)                           # m — корень T1
4  right[m] ← T2
5  if T2 ≠ NIL  parent[T2] ← m
6  return T1

Сложность: O(log n) амортизированно для Split и для Join; память O(1).
Корректность: после Search в корне стоит либо k, либо последний посещённый узел;
в первом случае разрез по корню точен, во втором все ключи по другую сторону от k
уже отделены splay-поворотами, поэтому L и R не пересекаются и покрывают T.

Разбор. Join для [math]\displaystyle{ T_1 = \{5, 10, 15\} }[/math] и [math]\displaystyle{ T_2 = \{20, 30\} }[/math]: максимум [math]\displaystyle{ T_1 }[/math] — 15, после splay(15) он корень, правого ребёнка у него нет, а слева — поддерево из [math]\displaystyle{ \{5, 10\} }[/math]; прицепляем [math]\displaystyle{ T_2 }[/math] справа. Split результата по [math]\displaystyle{ k = 10 }[/math]: Search(10) поднимает 10 в корень, key[r] = 10 не меньше 10, поэтому [math]\displaystyle{ R = r }[/math] (с правым поддеревом [math]\displaystyle{ \{15, 20, 30\} }[/math]), а [math]\displaystyle{ L = \{5\} }[/math].

Сложность. Время: [math]\displaystyle{ O(\log n) }[/math] амортизированно для обеих операций; память [math]\displaystyle{ O(1) }[/math]. Обоснование: одна операция Search/Splay плюс [math]\displaystyle{ O(1) }[/math] перестановок указателей.

Крайние случаи. Пустое дерево — Split возвращает (NIL, NIL). Если [math]\displaystyle{ k }[/math] меньше всех ключей, то [math]\displaystyle{ L }[/math] пусто, а [math]\displaystyle{ R = T }[/math]. Если [math]\displaystyle{ k }[/math] больше всех ключей, то [math]\displaystyle{ L = T }[/math], а [math]\displaystyle{ R }[/math] пусто. Join с пустым [math]\displaystyle{ T_1 }[/math] возвращает [math]\displaystyle{ T_2 }[/math], а при пустом [math]\displaystyle{ T_2 }[/math] результат — [math]\displaystyle{ T_1 }[/math]; предусловие «все ключи [math]\displaystyle{ T_1 }[/math] меньше ключей [math]\displaystyle{ T_2 }[/math]» обязательно проверить у вызывающего. См. рис. 4.

Min/Max и соседние элементы находятся спуском влево/вправо; чтобы оценка была амортизированной, найденный узел нужно сплайнить (в C++-реализации ниже так и сделано). Тогда операция стоит [math]\displaystyle{ O(\log n) }[/math] амортизированно; без splay это лишь [math]\displaystyle{ O(h) }[/math], то есть [math]\displaystyle{ O(n) }[/math] в худшем случае.

Рис. 4. Split сплайнит k в корень и разрезает дерево по нему; Join поднимает максимум левой части и прицепляет правую.

Реализация на C++ (приложение)

Splay-дерево с операциями find, insert, erase и проверкой инвариантов validate. Операции Split и Join в коде не реализованы — они вынесены в задачи для практики. Раздел носит характер приложения: для lecture достаточно псевдокода, код приведён для проверки утверждений.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

template <typename T>
class SplayTree {
    struct Node {
        T key;
        Node *left = nullptr, *right = nullptr, *parent = nullptr;
        explicit Node(const T& k) : key(k) {}
    };
    Node* root_ = nullptr;

    void rotate(Node* x) {                     // поднять x над его родителем
        Node* p = x->parent;
        if (!p) return;
        Node* g = p->parent;
        if (p->left == x) {
            p->left = x->right;
            if (x->right) x->right->parent = p;
            x->right = p;
        } else {
            p->right = x->left;
            if (x->left) x->left->parent = p;
            x->left = p;
        }
        p->parent = x;
        x->parent = g;
        if (g) { if (g->left == p) g->left = x; else g->right = x; }
        else   { root_ = x; }
    }

    void splay(Node* x) {
        while (x->parent) {
            Node* p = x->parent;
            Node* g = p->parent;
            if (!g) {                          // zig
                rotate(x);
            } else if ((g->left == p) == (p->left == x)) {   // zig-zig
                rotate(p);
                rotate(x);
            } else {                            // zig-zag
                rotate(x);
                rotate(x);
            }
        }
    }

    static void destroy(Node* n) {
        if (!n) return;
        destroy(n->left);
        destroy(n->right);
        delete n;
    }

    static bool check(Node* n, const T* lo, const T* hi) {
        if (!n) return true;
        if (lo && n->key < *lo) return false;
        if (hi && *hi < n->key) return false;
        if (n->left  && n->left->parent  != n) return false;
        if (n->right && n->right->parent != n) return false;
        return check(n->left, lo, &n->key) && check(n->right, &n->key, hi);
    }

    void inorder(Node* n, std::vector<T>& out) const {
        if (!n) return;
        inorder(n->left, out);
        out.push_back(n->key);
        inorder(n->right, out);
    }

public:
    SplayTree() = default;
    ~SplayTree() { destroy(root_); }
    SplayTree(const SplayTree&) = delete;
    SplayTree& operator=(const SplayTree&) = delete;

    bool empty() const { return root_ == nullptr; }

    bool find(const T& k) {
        Node* cur = root_;
        Node* last = nullptr;
        while (cur) {
            last = cur;
            if (k < cur->key)      cur = cur->left;
            else if (cur->key < k) cur = cur->right;
            else { splay(cur); return true; }
        }
        if (last) splay(last);
        return false;
    }

    void insert(const T& k) {
        if (!root_) { root_ = new Node(k); return; }
        Node* cur = root_;
        Node* par = nullptr;
        while (cur) {
            par = cur;
            if (k < cur->key)      cur = cur->left;
            else if (cur->key < k) cur = cur->right;
            else { splay(cur); return; }        // дубликат
        }
        Node* x = new Node(k);
        x->parent = par;
        if (k < par->key) par->left = x; else par->right = x;
        splay(x);
    }

    bool erase(const T& k) {
        if (!find(k)) return false;             // k — в корне
        Node* L = root_->left;
        Node* R = root_->right;
        if (L) L->parent = nullptr;
        if (R) R->parent = nullptr;
        delete root_;
        if (!L) { root_ = R; return true; }
        root_ = L;
        Node* m = L;                            // максимум левого поддерева
        while (m->right) m = m->right;
        splay(m);
        m->right = R;
        if (R) R->parent = m;
        return true;
    }

    // предусловие: дерево непусто; найденный узел сплайнится в корень,
    // поэтому повторные вызовы стоят O(log n) амортизированно
    T minimum() {
        assert(root_);
        Node* m = root_;
        while (m->left) m = m->left;
        splay(m);
        return m->key;
    }

    T maximum() {
        assert(root_);
        Node* m = root_;
        while (m->right) m = m->right;
        splay(m);
        return m->key;
    }

    std::vector<T> sorted() const {
        std::vector<T> v;
        inorder(root_, v);
        return v;
    }

    bool validate() const { return check(root_, nullptr, nullptr); }
};

int main() {
    SplayTree<int> t;
    for (int v : {20, 10, 30, 5, 15, 25, 35}) t.insert(v);
    assert(t.validate());

    assert(t.find(15));
    assert(!t.find(99));
    assert(t.validate());
    std::vector<int> s = t.sorted();                 // временный вектор сохраняем в переменную
    assert(std::is_sorted(s.begin(), s.end()));

    assert(t.minimum() == 5);
    assert(t.maximum() == 35);
    assert(t.validate());

    assert(t.erase(20));
    assert(!t.find(20));
    assert(t.validate());
    s = t.sorted();
    assert(std::is_sorted(s.begin(), s.end()));

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

• Ссылка parent обязательна — по ней splay поднимается к корню.
• find при неудаче сплайнит последний посещённый узел: это поддерживает адаптивность.
• minimum/maximum сплайнят найденный узел, поэтому их амортизированная оценка [math]\displaystyle{ O(\log n) }[/math] согласована с таблицей сложности. Предусловие — дерево непусто (assert(root_)).
• Рекурсивный destroy/check безопасны при разумной высоте; для гарантии используйте итеративные обходы (splay не даёт границы высоты на отдельной операции).

Сводная таблица сложности

Операция	Худший случай	Амортизированный	Память
Search	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Insert	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Delete	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Min / Max (со splay)	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Predecessor / Successor (со splay)	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Split / Join	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Обход по возрастанию	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(h) }[/math]; в худшем [math]\displaystyle{ O(n) }[/math] стека
Память структуры	—	—	[math]\displaystyle{ O(n) }[/math] (3 указателя на узел, без баланса)

Примечание. Все оценки, кроме обхода, амортизированные: отдельная операция может стоить [math]\displaystyle{ O(n) }[/math] (например, доступ к самому глубокому узлу вырожденного на время дерева). Поэтому splay-дерево не подходит для систем жёсткого реального времени, где нужна гарантия на каждую операцию; там лучше авл-дерево (план) или красно-чёрное-дерево (план). Обход требует стека глубины [math]\displaystyle{ h }[/math]: высота splay-дерева ничем не ограничена, и в худший момент [math]\displaystyle{ h = n }[/math], поэтому рекурсивный обход занимает [math]\displaystyle{ O(n) }[/math] памяти.

Трассировка примера

Вставим [math]\displaystyle{ 20, 10, 30, 5, 15, 25, 35 }[/math]; затем выполним find(5), find(99) и erase(20).

Шаг	Операция	Результат (in-order)	Что произошло
1	insert(20)	20	дерево пусто, 20 — корень
2	insert(10)	10, 20	10 подключён слева, один поворот zig — 10 корень
3	insert(30)	10, 20, 30	30 подключён справа от 20; zig-zig — корень 30
4	insert(5)	5, 10, 20, 30	5 подключён слева от 10; zig-zig, затем zig — корень 5
5	insert(15)	5, 10, 15, 20, 30	15 подключён слева от 20; два zig-zag — корень 15
6	insert(25)	5, 10, 15, 20, 25, 30	25 подключён справа от 20; splay — корень 25
7	insert(35)	5, 10, 15, 20, 25, 30, 35	35 подключён справа от 30; splay — корень 35
8	find(5)	5, 10, 15, 20, 25, 30, 35	ключ найден; 5 поднят в корень
9	find(99)	5, 10, 15, 20, 25, 30, 35	ключа нет; в корень поднят последний посещённый (35)
10	erase(20)	5, 10, 15, 25, 30, 35	20 сплайнится в корень; [math]\displaystyle{ L = 5(\cdot, 15(10)) }[/math], [math]\displaystyle{ R = 35(30(25)) }[/math]; максимум [math]\displaystyle{ L }[/math] — 15, после Splay(15) левая часть [math]\displaystyle{ 15(5(\cdot, 10)) }[/math], [math]\displaystyle{ R }[/math] прицеплен справа

In-order остаётся отсортированным на каждом шаге, validate() подтверждает BST-свойство и корректность ссылок на родителей.

Корректность и оценка сложности

Лемма 1 (splay сохраняет BST). Каждый поворот сохраняет порядок ключей, поэтому splay не меняет множество ключей; после splay узел [math]\displaystyle{ x }[/math] — корень.

Доказательство. Поворот переставляет два узла и перевешивает среднее поддерево, сохраняя неравенство left < node < right (см. авл-дерево (план)). Цикл поднимает [math]\displaystyle{ x }[/math] на каждом шаге, пока у него есть родитель, поэтому завершается, когда [math]\displaystyle{ x }[/math] — корень. [math]\displaystyle{ \blacksquare }[/math]

Теорема 2 (амортизированная оценка). Любая последовательность из [math]\displaystyle{ m }[/math] операций над splay-деревом с [math]\displaystyle{ n }[/math] узлами выполняется за [math]\displaystyle{ O((n + m)\log n) }[/math], то есть амортизированно [math]\displaystyle{ O(\log n) }[/math] на операцию.

Эскиз доказательства (метод потенциала, см. рис. 5). Положим

[math]\displaystyle{ \Phi(T) = \sum_{v \in T} \log_2 \text{size}(v). }[/math]

Для каждого поворота в точке [math]\displaystyle{ x }[/math] амортизированная стоимость ограничена утроенным приращением потенциала поддерева с корнем [math]\displaystyle{ x }[/math]:

[math]\displaystyle{ \hat c \le 3\big(\Phi'(x) - \Phi(x)\big), }[/math]

где [math]\displaystyle{ \Phi(x) = \log_2 \text{size}(x) }[/math]. Складывая вдоль пути доступа, получаем [math]\displaystyle{ O(\log n) }[/math]: вклад корня [math]\displaystyle{ \log_2 n }[/math], а телескопирование оставляет только разность потенциалов корня. Общий потенциал [math]\displaystyle{ \Phi(T) }[/math] при этом не обязан убывать — важен локальный потенциал узлов на пути. [math]\displaystyle{ \blacksquare }[/math]

Оговорка к оценке: [math]\displaystyle{ O(\log n) }[/math] на операцию получается при [math]\displaystyle{ m = \Omega(n) }[/math]. При малом [math]\displaystyle{ m }[/math] в оценке остаётся начальный потенциал порядка [math]\displaystyle{ O(n\log n) }[/math], и на одну операцию приходится [math]\displaystyle{ O\big((n/m + 1)\log n\big) }[/math].

Лемма о доступе (адаптивность). При весах [math]\displaystyle{ w(v) }[/math] амортизированная стоимость splay([math]\displaystyle{ x }[/math]) есть [math]\displaystyle{ O\!\big(\log(W/w(x))\big) }[/math], где [math]\displaystyle{ W = \sum_v w(v) }[/math]. При единичных весах это [math]\displaystyle{ O(\log n) }[/math], но для «горячих» (тяжёлых) узлов — существенно меньше.

Следствия. Из леммы о доступе выводятся:

• Статическая оптимальность: если доступы независимы с частотами [math]\displaystyle{ p(v) }[/math], суммарное время работы не хуже оптимального статического BST с точностью до константы.
• Статический палец: при фиксированном ключе [math]\displaystyle{ f }[/math] доступ к ключу [math]\displaystyle{ x }[/math] стоит амортизированно [math]\displaystyle{ O\big(\log(|x - f| + 1)\big) }[/math] — при весах, убывающих с расстоянием от [math]\displaystyle{ f }[/math] [2].
• Свойство рабочего множества: работа за период, в котором запрашивались [math]\displaystyle{ w }[/math] различных ключей, есть [math]\displaystyle{ O\big((w + \#\text{запросов})\log(w+1)\big) }[/math].

Теорема (динамический палец). Если доступ к [math]\displaystyle{ y }[/math] следует за доступом к [math]\displaystyle{ x }[/math], амортизированная стоимость доступа к [math]\displaystyle{ y }[/math] есть [math]\displaystyle{ O(\log d(x,y) + 1) }[/math], где [math]\displaystyle{ d }[/math] — число ключей между [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] [7]. Это не следствие леммы о доступе: теорему доказали Коул, Мишра, Шмидт и Сигел в 2000 году, через 15 лет после появления splay-деревьев.

Гипотеза динамической оптимальности. Тарджан и Слейтор предположили, что splay-дерево асимптотически не хуже любого BST (в том числе «офлайн-оптимального») с точностью до константы. Гипотеза открыта ⚠️ — это одна из центральных открытых проблем теории алгоритмов.

Рис. 5. Потенциал Φ = Σ log₂ size(v): у корня size = n, поэтому вклад корня log₂ n; лемма о доступе ограничивает splay(x) величиной O(log(W/w(x))).

Сравнение с альтернативами

Сводка различий — в таблице ниже и на рис. 6.

Критерий	Splay	АВЛ (план)	КЧ (план)	Treap
Хранит баланс	нет	высота / BF	цвет	случайный приоритет
Худший поиск	[math]\displaystyle{ O(n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math] (ожидаемо)
Амортизированный	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math] (следствие худшего)	[math]\displaystyle{ O(\log n) }[/math] (следствие худшего)	[math]\displaystyle{ O(\log n) }[/math] (следствие ожидаемого)
Адаптивность	да (рабочее множество)	нет	нет	нет
Split / Join	[math]\displaystyle{ O(\log n) }[/math]	сложно	сложно	[math]\displaystyle{ O(\log n) }[/math]
Локальность доступа	отличная	слабая	слабая	слабая
Гарантия на операцию	только амортизированная	да	да	вероятностная

Вердикт. Splay выбирают, когда обращения неравномерны (кэши, горячие ключи, частые Split/Join) и когда допустима амортизированная (а не пооперационная) гарантия. Если нужна жёсткая гарантия худшего случая или предсказуемость, берут красно-чёрное-дерево (план) или авл-дерево (план); если нужна простота и рандомизация — treap.

Рис. 6. Splay не хранит баланс и адаптивен, но гарантирует только амортизированное O(log n); АВЛ и КЧ дают O(log n) на каждую операцию.

Где применяется

1. Link-cut trees (Слейтор — Тарджан, 1983) [4]. Лес динамических деревьев хранится как набор «предпочитаемых путей», каждый путь — в splay-дереве. Splay выбран потому, что access перестраивает путь локально и оплачивается амортизированно, без хранения баланса: получаются операции со связностью и путями за [math]\displaystyle{ O(\log n) }[/math] амортизированно.
2. Динамическая связность и максимальный поток (Голдберг — Тарджан, 1986). Алгоритм максимального потока Голдберга — Тарджана использует динамические деревья [4] для операций над путями в остаточной сети: дерево меняет структуру путей по ходу вычисления, а splay позволяет делать это без полной перебалансировки.
3. Модель кэша с вытеснением по недавности [2]. Свойство рабочего множества объясняет, почему splay-дерево работает как модель кэша: стоимость работы на отрезке, где запрашивалось [math]\displaystyle{ w }[/math] различных ключей, ограничена [math]\displaystyle{ O\big((w + \#\text{запросов})\log(w+1)\big) }[/math], то есть зависит от размера рабочего множества, а не от [math]\displaystyle{ n }[/math]. Это модель поведения, а не конкретный продукт.
4. Структуры последовательностей (Split/Join). В «верёвках» (ropes) и редакторах текст хранят в листьях дерева, а вставку и удаление фрагмента выражают через Split по позиции и Join. Splay удобен тем, что обе операции — это один splay и [math]\displaystyle{ O(1) }[/math] перестановок указателей, без полей баланса.
5. Упорядоченные таблицы с «горячими» ключами. Как модель: если поток запросов имеет локальность (недавние ключи запрашиваются снова), адаптивность даёт выигрыш относительно структур с гарантией на каждую операцию; при равномерно случайном потоке выигрыша нет.

Историческая справка

• 1983. Д. Слейтор и Р. Тарджан предложили динамические деревья (link-cut trees) — структуру на основе splay-подобных путей [4].
• 1985. Д. Слейтор и Р. Тарджан опубликовали «Self-Adjusting Binary Search Trees» [2]: описаны splay-деревья, лемма о доступе, рабочее множество и статическая оптимальность. Это одна из первых структур с доказанными адаптивными оценками.
• 1986. Те же авторы предложили саморегулирующиеся кучи (self-adjusting heaps) [3] — ещё один пример амортизационного анализа без хранения баланса.
• 2000. Р. Коул, Б. Мишра, Ж.-П. Шмидт и А. Сигел доказали гипотезу динамического пальца [7] — через 15 лет после появления структуры.
• 1985–. Гипотеза динамической оптимальности splay-деревьев сформулирована Тарджаном и Слейтором и до сих пор открыта ⚠️.
• Название «splay» (расширять, разворачивать) отражает разворачивание пути доступа.

Типичные ошибки и подводные камни

• Забыть splay после доступа. Без сплайна дерево теряет адаптивность и амортизированные гарантии (и может выродиться).
• Неверный порядок в zig-zig. Сначала поворот вокруг родителя, затем вокруг [math]\displaystyle{ x }[/math]; перестановка ломает анализ и часть свойств.
• Путаница zig-zig и zig-zag. Направление детей у [math]\displaystyle{ x }[/math] и [math]\displaystyle{ p }[/math] одинаковое (zig-zig) — двойной поворот «снизу вверх»; разное (zig-zag) — два поворота вокруг [math]\displaystyle{ x }[/math].
• Использование как реального времени. [math]\displaystyle{ O(\log n) }[/math] — только амортизированное; отдельная операция может стоить [math]\displaystyle{ O(n) }[/math].
• Опора на validate с рекурсией при вырождении. Глубина может быть велика; для надёжности делайте итеративные обходы.
• Потеря ссылки parent. splay поднимается по родителям; ошибка в parent ломает всю операцию.
• Ожидание стабильности/детерминированности формы. Форма зависит от истории обращений; одинаковые множества, полученные разными доступами, выглядят по-разному.
• Split без splay. Деление «на месте» без сплайна корня легко нарушает BST-свойство.
• Разрез не по тому сравнению. При отсутствующем [math]\displaystyle{ k }[/math] нельзя безусловно брать left[root] в [math]\displaystyle{ L }[/math]: последний посещённый узел может быть меньше [math]\displaystyle{ k }[/math], и тогда он сам уходит в [math]\displaystyle{ L }[/math], а в [math]\displaystyle{ R }[/math] — только right[root].
• Запись в parent[NIL]. Строки вида parent[L] ← NIL без проверки L ≠ NIL пишут в несуществующий узел; в C++ это разыменование nullptr.
• Крайние случаи Delete. Отсутствие одного из поддеревьев или отсутствие ключа — частые источники ошибок.
• Ожидание, что splay всегда даёт баланс. В худший момент высота может быть большой; баланс — в среднем по последовательности.

Задачи для практики

1. Реализация splay. Реализуйте поворот и splay со всеми тремя случаями; проверьте BST-инвариант после случайных операций. Подсказка: parent обязателен. Ответ. Достаточно rotate + разбора трёх случаев; validate вызывайте после каждой случайной операции. Суммарное время [math]\displaystyle{ O((n+m)\log n) }[/math] при [math]\displaystyle{ m }[/math] операциях.
2. Амортизированная цена. Измерьте суммарное время [math]\displaystyle{ m }[/math] случайных поисков; сравните с [math]\displaystyle{ m\log n }[/math]. Подсказка: отдельные операции могут быть дорогими, сумма — нет. Ответ. Суммарное время есть [math]\displaystyle{ O(m\log n) }[/math] (при [math]\displaystyle{ m = \Omega(n) }[/math]), тогда как отдельный вызов может стоить до [math]\displaystyle{ O(n) }[/math]; отношение «сумма / [math]\displaystyle{ m }[/math]» и должно вести себя как [math]\displaystyle{ O(\log n) }[/math].
3. Локальность. Сравните последовательные и случайные доступы: во сколько раз splay быстрее при повторах? Подсказка: свойства рабочего множества. Ответ. При повторах splay быстрее за счёт свойства рабочего множества; выигрыш растёт с долей повторных запросов и падает с ростом числа различных ключей [math]\displaystyle{ w }[/math] в периоде.
4. Split/Join. Реализуйте Split(T, k) и Join(T1, T2); проверьте их на наборе ключей. Подсказка: splay разделяющего узла. Ответ. Split — Search(k) и разрез по сравнению key[root] с [math]\displaystyle{ k }[/math]; Join — splay максимума [math]\displaystyle{ T_1 }[/math] и прицепление [math]\displaystyle{ T_2 }[/math]. Обе операции [math]\displaystyle{ O(\log n) }[/math] амортизированно.
5. Диапазонный вывод и порядковая статистика. Добавьте rank/select, поддерживая размеры поддеревьев. Подсказка: пересчитывайте размеры при поворотах. Ответ. rank/select идут по size поддеревьев; при каждом повороте пересчитываются два узла, поэтому оценка остаётся [math]\displaystyle{ O(\log n) }[/math] амортизированно.
6. Link-cut tree (набросок). Постройте динамическое дерево на splay для связности/путей. Подсказка: «предпочитаемые пути» и access. Ответ. access реализуется через splay предпочитаемых путей (смена предпочитаемого ребёнка — это Split/Join), что даёт [math]\displaystyle{ O(\log n) }[/math] амортизированно на операцию.
7. Свойство рабочего множества. Сгенерируйте поток запросов из [math]\displaystyle{ w }[/math] различных ключей и проверьте оценку [math]\displaystyle{ O((w + q)\log(w+1)) }[/math]. Подсказка: считайте число поворотов. Ответ. Число поворотов за поток из [math]\displaystyle{ q }[/math] запросов есть [math]\displaystyle{ O\big((q + w)\log(w+1)\big) }[/math]; счётчик поворотов в реализации — прямой способ проверить оценку экспериментально.
8. Сравнение с КЧ. На неравномерной нагрузке сравните splay и красно-чёрное дерево. Подсказка: где обращения локальны, splay выигрывает. Ответ. На локальных нагрузках splay выигрывает; на равномерно случайных красно-чёрное дерево стабильнее, так как не платит за перестройку формы.

Связанные темы

• двоичное-дерево-поиска (план) — базовая структура.
• авл-дерево (план) и красно-чёрное-дерево (план) — строгие гарантии худшего случая.
• фибоначчиева-куча (план) — другой пример амортизационного анализа.
• асимптотическая-сложность — амортизированные оценки.
• графы (план) — link-cut trees для динамических графов.

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 12 «Binary Search Trees», гл. 13 (повороты) (проверено).
2. Sleator D. D., Tarjan R. E. Self-Adjusting Binary Search Trees // Journal of the ACM. — 1985. — Vol. 32, No. 3. — P. 652–686 (проверено).
3. Sleator D. D., Tarjan R. E. Self-Adjusting Heaps // SIAM Journal on Computing. — 1986. — Vol. 15, No. 1 (проверено).
4. Sleator D. D., Tarjan R. E. A Data Structure for Dynamic Trees // Journal of Computer and System Sciences. — 1983. — Vol. 26, No. 3. — P. 362–391 (link-cut trees) (проверено).
5. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 3 (двоичные деревья поиска, красно-чёрные деревья) — общий справочник по сбалансированным деревьям (проверено).
6. Wikipedia: Splay tree. URL: https://en.wikipedia.org/wiki/Splay_tree (проверено).
7. Cole R., Mishra B., Schmidt J., Siegel A. On the Dynamic Finger Conjecture for Splay Trees // SIAM Journal on Computing. — 2000. — Vol. 30, No. 1 (проверено).