DS Структуры данных Структура данных
Косое дерево
Также: Splay tree · расширяющееся дерево · самонастраивающееся дерево поиска · self-adjusting binary search tree · splay · zig-zig · zig-zag · лемма о доступе · access lemma · динамическая оптимальность · dynamic optimality
Дерево поиска, которое не хранит ни высот, ни цветов, а после каждого запроса поднимает найденный ключ в корень — парами поворотов. На журнале веб-сервера 1995 года популярные адреса сами собираются наверху: 7,1 сравнения на запрос против 10,3 у сбалансированного дерева при энтропии запросов 6,9. Почему подъём именно парами превращает худший путь в хороший, и откуда берутся амортизированные log n.
В журнале веб-сервера Космического центра Кеннеди за 13 июля 1995 года — 128 932 успешных запроса к 2230 адресам. Запросы распределены очень неровно: логотипы стоят на каждой странице сайта и запрашиваются тысячами, а большинство адресов спрашивали считанные разы. Сбалансированное дерево поиска не знает об этом и тратит на любой адрес около десяти сравнений. Косое дерево узнаёт само: после каждого запроса оно поднимает найденный адрес в корень. Ниже — весь день журнала, сыгранный в такое дерево.
Каждая точка — адрес: по горизонтали его место по алфавиту, по вертикали глубина. Через пару тысяч запросов вершина дерева заселена популярными адресами, а редкие опускаются вниз. На всём дне косое дерево тратит 7,11 сравнения на запрос, сбалансированное — 10,25, а энтропия запросов, нижняя граница для любого кода адресов, — 6,87 бита. Дерево, которое ничего не знало о частотах заранее, почти сравнялось с ней.
Идея
Косое дерево — обычное дерево поиска без высот, цветов и приоритетов. Единственное правило: найденный узел x — или только что вставленный — поднимается в корень. Поднимается он парами поворотов, и пара зависит от того, как x висит относительно деда. Это действие называют splay, отсюда английское имя; по-русски дерево называют косым или расширяющимся.
Повороты парами
Поворот поднимает узел на уровень выше, не нарушая порядка ключей, — он знаком по АВЛ-деревьям. Пусть p — родитель x, g — дед.
- zig: p — корень. Один поворот x вокруг p.
- zig-zig: x и p — оба левые дети или оба правые. Сначала поворот p вокруг g, потом x вокруг p.
- zig-zag: один левый, другой правый. Два поворота x подряд — вокруг p, потом вокруг g.
Самое простое правило — поднимать x одиночными поворотами, «в корень». Оно отличается только в случае zig-zig, и как раз этот случай решает всё. Посмотрите на худшую форму дерева — путь из пятнадцати ключей.
Одиночные повороты поднимают самый глубокий ключ наверх, но путь остаётся путём: следующий по глубине ключ лишь на уровень выше прежнего. Пары поворотов поднимают тот же ключ и заодно складывают путь вдвое — каждый пройденный узел оказывается примерно вдвое ближе к корню. Пройдите все ключи по порядку: косому дереву это обойдётся в 63 сравнения, «в корень» — в 134. На журнале из сцены выше разница видна ещё резче: прочитать после дневного журнала все 2230 адресов по алфавиту дважды косое дерево может за 4,5 сравнения на адрес, а одиночные повороты — за 564.
Почему log n
Один запрос к косому дереву может стоить n: путь из сцены — честный вход. Но за дорогой запрос дерево расплачивается тем, что становится короче, и амортизационный анализ это доказывает. Дадим каждому узлу вес w(x) > 0. Пусть s(x) — сумма весов в поддереве x, а r(x) = log₂ s(x) — его ранг. Потенциал дерева — сумма рангов всех узлов. Амортизированная стоимость шага — число поворотов плюс изменение потенциала.
Подъём x в корень t имеет амортизированную стоимость не больше 3(r(t) − r(x)) + 1, если считать каждый поворот за единицу.
Пусть r — ранги до шага, r′ — после. Покажем, что шаг zig-zig или zig-zag стоит не больше 3(r′(x) − r(x)), а zig — не больше 3(r′(x) − r(x)) + 1. Тогда суммы по шагам складываются в цепочку: ранг x после одного шага — его ранг до следующего, в конце x — корень с рангом r(t), а zig бывает только последним шагом.
Нам понадобятся два факта. Во-первых, ранги меняются только у узлов, участвующих в шаге. Во-вторых, если a + b ≤ c для положительных a, b, то log₂ a + log₂ b ≤ 2 log₂ c − 2: произведение ab при заданной сумме наибольшее, когда a = b = c/2.
zig. Поворот один. После него x стоит на месте p, поэтому r′(x) = r(p), а r′(p) ≤ r′(x). Изменение потенциала r′(p) − r(x) ≤ r′(x) − r(x), и стоимость не больше 1 + (r′(x) − r(x)).
zig-zig. Поворотов два. x встаёт на место g: r′(x) = r(g). Изменение потенциала r′(p) + r′(g) − r(p) − r(x) ≤ r′(x) + r′(g) − 2r(x), потому что r′(p) ≤ r′(x) и r(p) ≥ r(x). Поддерево x до шага и поддерево g после не пересекаются и лежат в поддереве x после шага, поэтому s(x) + s′(g) ≤ s′(x) и по второму факту r(x) + r′(g) ≤ 2r′(x) − 2. Отсюда r′(g) ≤ 2r′(x) − r(x) − 2, и стоимость не больше 2 + r′(x) + 2r′(x) − r(x) − 2 − 2r(x) = 3(r′(x) − r(x)).
zig-zag. Поворотов два, r′(x) = r(g). Изменение потенциала r′(p) + r′(g) − r(p) − r(x) ≤ r′(p) + r′(g) − 2r(x). После шага p и g — два ребёнка x, их поддеревья не пересекаются, и r′(p) + r′(g) ≤ 2r′(x) − 2. Стоимость не больше 2 + 2r′(x) − 2 − 2r(x) ≤ 3(r′(x) − r(x)).
Обратите внимание на случай zig-zig. Именно в нём нужно, чтобы сначала поднялся p: тогда после шага g висит под p, и поддеревья x до шага и g после не пересекаются. При двух поворотах самого x такой оценки не получается, и сцена с путём показывает, что не случайно: путь не складывается.
Любые m обращений к косому дереву с n ключами делают O((m + n) log n) поворотов и сравнений.
Дадим каждому узлу вес 1. Тогда s(t) = n, s(x) ≥ 1, и по лемме каждое обращение амортизированно стоит не больше 3 log₂ n + 1 поворотов. Настоящая стоимость m обращений равна сумме амортизированных минус прирост потенциала. Потенциал всегда между 0 и n log₂ n, поэтому прирост не меньше −n log₂ n, и поворотов всего не больше m(3 log₂ n + 1) + n log₂ n. Сравнений при поиске на одно больше, чем поворотов при подъёме: глубина x плюс сравнение с ним самим.
Частые ключи — у корня
Та же лемма с другими весами объясняет, почему на журнале сервера косое дерево почти догнало энтропию.
Пусть каждый из n ключей спрашивают f(x) ≥ 1 раз, всего m запросов, и H = Σ (f(x)/m) log₂ (m/f(x)) — энтропия запросов. Тогда косое дерево, в котором все ключи уже есть, сделает на них не больше 3mH + 2m + Σ log₂(m/f(x)) сравнений.
Дадим ключу вес q(x) = f(x)/m. Сумма весов — 1, поэтому s(t) = 1, а s(x) ≥ q(x). По лемме обращение к x стоит амортизированно не больше 3 log₂ (1/q(x)) + 1 поворотов, а все f(x) обращений к нему — 3f(x) log₂ (m/f(x)) + f(x). Сумма по ключам — 3mH + m. Ранг узла лежит между log₂ q(x) и 0, поэтому потенциал может упасть за всё время не больше чем на Σ log₂(m/f(x)) — это и есть добавка. Сравнений на одно больше, чем поворотов, на каждый запрос — ещё m.
А лучше, чем mH с точностью до множителя, не может никакое неподвижное дерево поиска, даже построенное заранее по известным частотам.
Любое неподвижное дерево поиска тратит на такие запросы в среднем не меньше H / log₂ 3 ≈ 0,63H сравнений.
Поиск ключа x на глубине d — это d − 1 ответов «меньше» или «больше» и один ответ «равно»: слово длины d из трёх букв. Слова разных ключей разные, и ни одно не начало другого — «равно» стоит только в конце. Для таких слов верно неравенство Крафта с основанием 3: Σ 3−d(x) ≤ 1. Логарифм — вогнутая функция, поэтому среднее логарифмов не больше логарифма среднего: Σ q(x) log₃ (3−d(x)/q(x)) ≤ log₃ Σ 3−d(x) ≤ 0. Раскрыв логарифм, получаем Σ q(x) d(x) ≥ Σ q(x) log₃ (1/q(x)) = H / log₂ 3 — та же граница, что для кодов Хаффмана, только в троичных цифрах.
Значит, косое дерево, ничего не зная о частотах, проигрывает лучшему неподвижному дереву не больше чем в постоянное число раз. Оценка 3H грубая: на журнале сервера вышло 7,11 сравнения при H = 6,87.
Код
Листинг играет журнал за 13 июля 1995 года в три дерева: сбалансированное, построенное заранее по всем адресам, косое и «в корень». Потом, не перестраивая деревья, читает все адреса по алфавиту дважды.
NASA server log, 13 July 1995: 128932 requests to 2230 paths tree comparisons per request balanced, built in advance 10.25 splay 7.11 move to root 7.04 entropy of the requests, bits 6.87 then all 2230 paths in order, twice splay 4.49 move to root 564.23
На самом журнале «в корень» даже чуть лучше косого дерева: 7,04 против 7,11. Запросы к серверу почти случайны, длинных путей в них не бывает, и складывать нечего. Но у «в корень» нет гарантии, и последовательный проход по адресам это показывает — 564 сравнения на адрес, в 125 раз больше. Косое дерево платит за гарантию сотыми долями сравнения.
Сколько это стоит
| Свойство | Оценка | Статус |
|---|---|---|
| поиск, вставка, удаление | O(log n) амортизированно, одна операция — до O(n) | доказано выше |
| статическая оптимальность | не хуже лучшего неподвижного дерева с точностью до множителя | доказано выше |
| рабочее множество | O(log t) за обращение, где t — сколько разных ключей спрашивали с прошлого раза | Слитор и Тарьян, 1985 |
| последовательный доступ | все n ключей по порядку — O(n) | Тарьян, 1985 |
| динамическая оптимальность | не хуже любого дерева поиска с поворотами, даже знающего запросы заранее | гипотеза с 1985 года |
Памяти косое дерево берёт меньше всех сбалансированных: в узле только ключ и ссылки. Зато каждый поиск переставляет узлы. Это плохо для многопоточности — читатели становятся писателями, — и для кэша процессора: изменённые узлы приходится записывать. Поэтому стандартные библиотеки обычно берут красно-чёрные деревья, а косые остаются там, где обращения неравномерны и один поток.
Где работает
- Карта памяти процесса. В FreeBSD записи карты виртуальной памяти процесса ищутся по адресу в косом дереве, а обращения к одним и тем же областям памяти идут сериями — как раз то, на чём косое дерево выигрывает.
- Компиляторы. В библиотеке libiberty, общей для GCC и binutils, есть готовый тип
splay_tree. - Деревья по неявному ключу. Если ключом считать позицию в последовательности, косое дерево умеет вырезать, вставлять и разворачивать куски строки или массива за амортизированные O(log n): нужный кусок поднимают двумя подъёмами в одно поддерево.
- Динамические деревья. Структура link-cut тех же Слитора и Тарьяна, на которой строят быстрые алгоритмы потоков, хранит пути в косых деревьях.
История
Дэниел Слитор и Роберт Тарьян представили косые деревья в 1983 году, а полную статью «Самонастраивающиеся двоичные деревья поиска» опубликовали в 1985-м. В ней лемма о доступе, статическая оптимальность, рабочее множество и гипотеза о динамической оптимальности: косое дерево не хуже любого дерева поиска с поворотами, даже того, которое заранее знает все запросы, с точностью до постоянного множителя. Гипотеза открыта уже сорок лет. Долго было известно только, что косое дерево не более чем в O(log n) раз хуже идеального — это следует из сбалансированности. В июле 2026 года восемь авторов, среди них сам Тарьян, выложили препринт с оценкой O(log log n · (log log log n)²) — почти постоянный множитель; рецензирование ещё впереди.
Задачи
В задаче нужно реализовать косое дерево точно по правилам и сосчитать сравнения на настоящем журнале сервера и на входах, где одиночные повороты проваливаются.
Цена журналаДанные: Журнал веб-сервера Космического центра Кеннеди, 13 июля 1995: NASA-HTTP, Internet Traffic Archive, свободно распространяется