DS Структуры данных Структура данных
Декартово дерево
Также: Treap · дерамида · Cartesian tree · randomized search tree · декартово дерево по неявному ключу · implicit treap · split и merge
Дерево поиска, в котором у каждого ключа есть ещё случайный приоритет, и по приоритетам дерево устроено как куча. Форма тогда такая, будто ключи вставили в случайном порядке, и средняя глубина логарифмическая на любых данных. Две операции — разрезать по ключу и склеить — заменяют все повороты, а если ключом считать место в последовательности, дерево становится массивом, в котором кусок можно развернуть или перенести за O(log n).
В справочнике GeoNames 45 227 городов с населением от 10 тысяч. Отсортируем их по долготе, с запада на восток, и сложим в дерево поиска с ключом-долготой — получится палка в 45 227 этажей. Теперь дадим каждому городу вдобавок случайное число — приоритет — и потребуем, чтобы у каждого узла приоритет был больше, чем у его детей. Такое дерево существует, и оно одно; его высота — 36, а средняя глубина — 19,79, почти столько, сколько предсказывает теория для случайного порядка вставки. Вместо случайного числа можно взять настоящее: население, широту. Иногда это работает, иногда нет. Ниже это дерево нарисовано целиком: каждый город — точка, по горизонтали его ключ, по вертикали приоритет. Проведите ножом по меридиану.
Нож по нулевому меридиану делит дерево на два — 15 661 город к западу и 29 566 к востоку, — и для этого достаточно пройти 18 узлов из 45 227: те, что стоят на пути разреза, меняют по одной ссылке, остальные даже не замечают. Приоритет-население почти не уступает случайному: корнем становится Шанхай, высота та же — 36. Приоритет-широта превращает картинку в карту мира, но дерево вырастает до 102 этажей: соседние по долготе города часто и по широте рядом. Если приоритет растёт вместе с долготой, дерево — снова палка. Случайность работает, потому что ничего не знает о ключах.
Идея
У каждого узла два числа: ключ и приоритет. По ключам дерево — дерево поиска, по приоритетам — куча: у родителя приоритет больше, чем у детей. Если приоритеты выбраны случайно, дерево выглядит так, будто ключи вставили в случайном порядке, — каким бы ни был настоящий порядок. А менять его удобно двумя операциями: разрезать по ключу на два дерева и склеить два дерева в одно.
Сначала — почему такое дерево вообще одно.
Если все ключи различны и все приоритеты различны, существует ровно одно декартово дерево из этих пар.
В корне может стоять только узел с наибольшим приоритетом: любой другой был бы ниже его в куче. Раз корень определён, по правилу дерева поиска все ключи меньше корневого обязаны лежать в левом поддереве, а большие — в правом. Каждое поддерево — снова декартово дерево из своих пар, и для него рассуждение повторяется. Индукцией по числу узлов получаем, что дерево определено однозначно; построить его можно тем же рассуждением, так что оно существует.
Отсюда главное следствие. Вставим ключи в обычное дерево поиска в порядке убывания приоритетов. В получившемся дереве каждый узел вставлен позже всех своих предков, то есть приоритет у предков больше, — значит, это декартово дерево, а оно одно. Декартово дерево — это дерево поиска, в которое ключи вставили в порядке, заданном приоритетами. Если приоритеты случайные, порядок случайный, и всё, что известно о дереве поиска при случайном порядке вставки, верно и здесь — для любых данных.
Отсюда же название. Если нарисовать узел точкой с координатами (ключ, приоритет), дерево целиком определяется этими точками на плоскости, как в сцене выше. Жан Вюймен в 1980 году назвал такие деревья картезианскими — по декартовым координатам; по-русски их зовут декартовыми, а иногда дерамидами — от «дерево» и «пирамида». Раймунд Зайдель и Сесилия Арагон в 1989 году предложили давать узлам случайные приоритеты и назвали получившуюся структуру treap — от tree и heap.
Почему глубина логарифмическая
Пусть ключи упорядочены, k₁ < k₂ < … < kn, а приоритеты — независимые случайные числа, все разные. Глубина узла — это число его предков, считая сам узел, так что достаточно понять, когда один узел — предок другого.
Узел ki — предок узла kj (или он сам) тогда и только тогда, когда у ki наибольший приоритет среди всех ключей от ki до kj включительно. Поэтому это случается с вероятностью 1/(|i − j| + 1).
Обозначим через S ключи от ki до kj и пойдём от корня вниз. Пока ключ текущего узла вне S, весь отрезок S лежит по одну сторону от него — в одном поддереве, — и мы спускаемся туда. Первый встреченный узел m из S — предок всех остальных узлов S, поэтому по свойству кучи у него наибольший приоритет в S. Если m = ki, то ki — предок kj. Если m лежит строго между ними, то ki и kj расходятся в разные поддеревья m, и ни один не предок другого. Если m = kj, то, наоборот, kj выше. Итак, ki — предок kj ровно тогда, когда m = ki. В S |i − j| + 1 ключей, и при случайных приоритетах наибольший с равной вероятностью у любого из них.
Ожидаемая глубина узла kj равна Hj + Hn−j+1 − 1, где Hm = 1 + 1/2 + … + 1/m, а средняя по всем узлам — 2(1 + 1/n)Hn − 3 ≈ 2 ln n.
Глубина kj — сумма по всем i индикаторов «ki — предок kj или он сам». Математическое ожидание суммы — сумма вероятностей из леммы: Σi 1/(|i − j| + 1). Ключи левее kj вместе с ним дают 1/j + … + 1/2 + 1 = Hj, ключи правее вместе с ним — Hn−j+1, а сам kj посчитан дважды. Среднее по j получается из равенства H₁ + … + Hn = (n + 1)Hn − n.
Для 45 227 городов формула даёт 19,59; дерево со случайными приоритетами вышло со средней глубиной 19,79. В статье о дереве поиска та же сумма получена для случайного порядка вставки — это одно и то же утверждение, увиденное с двух сторон. Высота, то есть худший узел, больше: 36 при 2 ln n ≈ 21. Но и она с огромной вероятностью логарифмическая, а не линейная.
Условие теоремы — «приоритеты случайны и не зависят от ключей». Сцена показывает, что бывает, когда оно нарушено. Население с долготой почти не связано, и дерево почти как случайное: средняя глубина 20,63. Широта связана заметно — города одного побережья, одной долины стоят рядом и по долготе, и по широте, — и средняя глубина 30,17. А приоритет-долгота — это палка, худший случай дерева поиска. Перемешать данные заранее, как советуют для обычного дерева поиска, можно только если все ключи известны сразу; случайный приоритет делает то же самое на лету.
Ножницы и клей
Две операции заменяют всю балансировку.
Разрезать (split) дерево по ключу x — получить два дерева: в одном ключи меньше x, в другом остальные. Смотрим на корень. Если его ключ меньше x, корень вместе со своим левым поддеревом целиком уходит в левую часть, а режем дальше его правое поддерево; левая часть разреза станет новым правым ребёнком корня. Иначе зеркально. Ножницы идут одним путём от корня вниз — тем, которым шёл бы поиск x, — и на каждом узле переставляют одну ссылку. Стоит это столько, какова глубина пути: O(log n) в среднем.
Склеить (merge) два дерева, у которых все ключи первого меньше всех ключей второго. Корнем станет тот из двух корней, у кого приоритет больше. Если это корень первого дерева, его левое поддерево остаётся как есть, а правое склеиваем со вторым деревом; иначе зеркально. Склейка идёт вниз по правому краю первого дерева и левому краю второго — тоже O(log n).
Остальное собирается из этих двух. Вставка ключа x — разрезать по x и склеить три дерева: левое, узел x, правое. Удаление — найти узел и склеить два его поддерева. Вырезать все ключи из диапазона — два разреза. Объединить два множества, где все ключи одного меньше ключей другого, — одна склейка. В листинге вставка сделана чуть экономнее: узел спускается, пока у встречных узлов приоритет больше, а дальше ножницы делят то, что под ним, на две его ветки.
У вставки есть и классическая запись — поворотами: новый ключ становится листом и поднимается поворотами, пока его приоритет больше родительского. Узлы, через которые проходят ножницы при вставке, — ровно те, мимо которых узел поднимался бы поворотами, так что работа одна и та же. И её немного.
При вставке ключа в декартово дерево со случайными приоритетами ожидаемое число поворотов меньше двух.
После вставки узел x стоит на своём месте в итоговом дереве, а повороты, которые его туда подняли, — это узлы правого края его левого поддерева и левого края правого: каждый поворот переносит под x по одному такому узлу. Пусть x — t-й по порядку ключ. Узел y = ki левее x стоит на правом краю левого поддерева x тогда и только тогда, когда у x наибольший приоритет среди ключей от y до x (по лемме x — предок y), а у y — наибольший среди ключей от y до x без самого x: тогда y — предок всех ключей между ними, и путь от x к y поворачивает только направо; наоборот, если на этом пути есть узел с ключом между y и x, он предок y, а значит, у него приоритет больше. Вероятность того, что из d + 1 ключей отрезка наибольший приоритет у x, а второй по величине — у y, где d = t − i, равна 1/((d + 1)d). Сумма по d от 1 до t − 1 — это 1 − 1/t, потому что 1/((d + 1)d) = 1/d − 1/(d + 1). С другой стороны выходит 1 − 1/(n − t + 1), а вместе меньше двух.
Листинг проверяет это на 6283 городах от 100 тысяч жителей, вставленных по одному в порядке справочника: ножницы прошли в среднем 1,989 узла на вставку. Для сравнения: АВЛ-дерево на случайном порядке делало около половины перебалансировки на вставку, но на упорядоченных ключах — почти по одной на каждую, и ещё пересчитывало высоты на всём пути к корню. Декартову дереву порядок ключей безразличен: в среднем меньше двух поворотов на любых данных.
Если все ключи известны заранее и уже отсортированы, дерево строится вообще без поворотов, за O(n). Идём по ключам слева направо и держим в стеке правый край уже построенного дерева. Новый узел снимает со стека все узлы с меньшим приоритетом — последний снятый становится его левым ребёнком, — а сам становится правым ребёнком того, кто остался на вершине стека. Каждый узел попадает в стек и снимается не больше одного раза. Так листинг строит все четыре дерева из сцены.
Неявный ключ: массив, который режется
Уберём ключи совсем. Пусть узлы стоят в дереве в каком-то порядке, и этот порядок — порядок элементов последовательности: симметричный обход выдаёт её от начала до конца. Ключом узла тогда служит его место — сколько узлов левее. Хранить его нельзя, он меняется при каждой вставке в начало, но вычислить можно: если в каждом узле держать размер его поддерева, место — это размер левого поддерева плюс размеры левых поддеревьев и сами узлы там, где путь от корня поворачивал направо. Это декартово дерево по неявному ключу, и разрез по ключу превращается в разрез по месту: «первые k элементов и остальные».
Получается массив, у которого дешёвые операции другие. Взять k-й элемент — O(log n) вместо O(1). Зато вставить элемент в середину, вырезать кусок и вставить его в другое место — два-три разреза и склейки, O(log n) вместо сдвига хвоста. А чтобы развернуть кусок, достаточно вырезать его и пометить корень: «это поддерево перевёрнуто». Пометка ленивая: дети меняются местами и получают пометку, только когда в узел заходит следующая операция. Разворот стоит O(log n), сколько бы элементов ни было в куске.
Где нужен частый разворот кусков? Например, в задаче коммивояжёра. Правка 2-opt берёт два ребра маршрута и заменяет их двумя другими, и кусок маршрута между ними при этом разворачивается. Массив делает это за время, пропорциональное длине куска, — или меньшей из двух частей круга. На маршруте из сотен городов это мгновенно, на сотнях тысяч — заметно. Ниже маршрут через города мира правится 2-opt по восьми ближайшим соседям, а хранится в декартовом дереве по неявному ключу.
Счётчики честные к обеим сторонам. Массив платит за разворот меньшей частью круга, а за шаг «следующий город маршрута» — одной операцией. Дереву за тот же шаг надо найти место города и взять следующий элемент — два спуска по O(log n). Кто выигрывает, решает длина кусков. Если начать со случайного маршрута, 2-opt разворачивает огромные куски: на 573 городах от миллиона жителей массив ещё впереди — 139 957 шагов против 308 138 узлов дерева, — на 6283 городах дерево уже втрое экономнее, а на всех 45 227 — в 17,6 раза: 50 миллионов узлов против 886 миллионов шагов. Если же начать с маршрута вдоль кривой Гильберта, который сразу обходит соседние города подряд, куски получаются короткими, и массив выигрывает везде: на 573 городах в 12 раз, на всех 45 227 — в 3,4 раза, хотя разрыв с ростом n сокращается. А шаг дерева к тому же дороже шага массива — это переход по ссылке в другое место памяти. Майкл Фредман, Дэвид Джонсон и соавторы в 1995 году подробно сравнили такие структуры для 2-opt и правки Лина — Кернигана по настоящему времени. Дерево у них было расширяющееся, и на больших маршрутах оно обгоняло массив; а на маршрутах в десятки и сотни тысяч городов быстрее всех оказались двухуровневые списки — маршрут, разрезанный на куски примерно равной длины, каждый из которых — двусвязный список.
Код
Первый листинг — декартово дерево с ключами: разрез, склейка, вставка и удаление через них и построение стеком из отсортированных ключей. Все четыре дерева из первой сцены и разрез по нулевому меридиану — его вывод. Приоритеты — splitmix64: одинаковые в Python, Go и сцене, поэтому и деревья одинаковые.
45227 towns, the key is the longitude priority height avg depth random 36 19.79 population 36 20.63 latitude 102 30.17 longitude 45227 22614.00 random priorities, the average depth expected: 2(1 + 1/n)H_n - 3 = 19.59 the root by population: Shanghai, 24,874,500 people cut at longitude 0: 15661 towns west, 29566 east; the scissors passed 18 nodes glued back, the same tree as before: True
Второй — последовательность на неявном ключе: размеры поддеревьев, ленивый разворот, место элемента по ссылкам на родителя и 2-opt по городам от миллиона жителей с двух начальных маршрутов. Чтобы найти место элемента, сначала поднимаемся от него к корню, а потом проталкиваем пометки разворота сверху вниз по этому пути: иначе левое и правое у предков могут быть ещё не переставлены.
by population: Shanghai | Chongqing | Chengdu | Beijing | Guangzhou | Shenzhen | Kinshasa | Istanbul | Lagos | Ho Chi Minh City reverse 2..6: Shanghai | Chongqing | Kinshasa | Shenzhen | Guangzhou | Beijing | Chengdu | Istanbul | Lagos | Ho Chi Minh City move 0..2 to 5: Shenzhen | Guangzhou | Beijing | Chengdu | Istanbul | Shanghai | Chongqing | Kinshasa | Lagos | Ho Chi Minh City 573 towns of 1,000,000+, 2-opt from two starts random order: 45,718.6 -> 2,608.7 degrees, 1200 reversals; an array 139,957 steps, the treap 308,138 nodes Hilbert curve: 2,829.1 -> 1,934.3 degrees, 348 reversals; an array 12,391 steps, the treap 151,942 nodes
Сколько это стоит
| Операция | В среднем | Худший случай |
|---|---|---|
| поиск, вставка, удаление | O(log n), глубина около 2 ln n | O(n), с ничтожной вероятностью |
| разрез, склейка | O(log n) | O(n) |
| повороты при вставке | меньше 2 | O(n) |
| построение из отсортированных ключей | O(n) | O(n) |
| неявный ключ: k-й элемент, вставка в середину, разворот и перенос куска | O(log n) | O(n) |
«В среднем» здесь — по случайным приоритетам, а не по данным: гарантия держится на любом входе, если противник не видит приоритетов. Это важное условие. Если приоритеты получаются из предсказуемого генератора с известным зерном, а ключи выбирает злоумышленник, он может подобрать ключи под приоритеты и вырастить палку. Там, где данные приходят извне, зерно берут из системного источника случайности. Память — O(n): ключ, две ссылки и приоритет; неявному ключу нужны ещё размер поддерева и бит пометки.
Замер — разворот случайного куска: массив против декартова дерева по неявному ключу.
Массив разворачивает за время, пропорциональное длине куска, дерево — за логарифм, но с большим множителем. Точка пересечения — около 10–30 тысяч элементов в обоих языках, и после неё разрыв растёт: в Go на миллионе элементов дерево быстрее в 15 раз, в Python на ста тысячах — в 5. Срез списка в Python копирует память на скорости C, поэтому интерпретатору с его деревом из списков и рекурсией приходится догонять не меньше, чем в Go. Для небольших последовательностей массив разумнее; дерево нужно, когда последовательность длинная, а правок много.
Где работает
Олимпиады и собеседования. Декартово дерево по неявному ключу — главный инструмент для задач, где массив режут, склеивают и разворачивают кусками: его пишут по памяти, и одной структурой закрываются задачи, для которых иначе понадобились бы разные. Версия с ключами и версия с неявным ключом отличаются несколькими строками: условием разреза и пересчётом размеров.
Хранилища. В btcd — полном узле сети Биткойн, написанном на Go, — пакет database/internal/treap хранит упорядоченные пары ключ-значение для кода базы данных. В нём два варианта: изменяемый, который правит дерево на месте, и неизменяемый, где каждая правка создаёт новую версию дерева и делит с прежней все нетронутые узлы. Читатель держит указатель на свою версию как снимок — по словам документации, снимок стоит O(1). Изменение затрагивает только путь от корня, а у декартова дерева этот путь логарифмический без всякой балансировки, поэтому копировать при каждой правке приходится немного.
Минимум на отрезке. Декартово дерево Вюймена, где приоритет — само значение элемента и наверху стоит наименьшее, превращает вопрос «наименьший элемент между позициями i и j» в вопрос «наименьший общий предок двух узлов», потому что наименьший элемент отрезка — это узел, который по лемме выше лежит на пути между ними. Так задачу о минимуме на отрезке сводят к наименьшему общему предку и обратно; для неизменного массива обычно проще разреженная таблица.
Чем заменяют. Там, где нужна гарантия худшего случая, стоят красно-чёрные и АВЛ-деревья; там, где важна конкурентность, — списки с пропусками, у которых та же идея случайности, только записанная уровнями; для длинных текстов в редакторах — верёвки.
История
Жан Вюймен в 1980 году в статье «Единый взгляд на структуры данных» описал деревья, построенные по точкам плоскости, — картезианские, — и показал, как они связывают поиск, сортировку и задачи о минимуме. Раймунд Зайдель и Сесилия Арагон в 1989 году предложили брать приоритеты случайно, доказали, что ожидаемая глубина и число поворотов — меньше двух на вставку — не зависят от данных, показали, что разрез и склейка тоже стоят ожидаемый логарифм, и назвали структуру treap; полная версия статьи «Случайные деревья поиска» вышла в 1996 году. Неявный ключ — приём из олимпиадной практики, у которого нет одного автора: с ним декартово дерево стало одной из самых любимых структур в задачах на последовательности.
Задачи
В задаче нужно резать дерево городов по многим меридианам сразу и для каждого разреза узнать, сколько узлов пройдут ножницы, — не разрезая. Подвох в том, что дерево с неслучайными приоритетами бывает палкой, и честные разрезы тогда стоят O(n) каждый.
Разрез по меридиануДанные: Населённые пункты: GeoNames, CC BY 4.0