Треп

Треп
Треп
Тип	Рандомизированное двоичное дерево поиска
Операция
Временная сложность в нотации «большое О»
Операция	Средний
Поиск	О (лог n )
Вставлять	О (лог n )
Удалить	О (лог n )
Сложность пространства
Космос	На )

Структура данных случайного дерева поиска

В информатике treap и рандомизированное бинарное дерево поиска — это две тесно связанные формы структур данных бинарного дерева поиска , которые поддерживают динамический набор упорядоченных ключей и позволяют выполнять бинарный поиск среди ключей. После любой последовательности вставок и удалений ключей форма дерева представляет собой случайную величину с тем же распределением вероятностей, что и случайное бинарное дерево; в частности, с высокой вероятностью его высота пропорциональна логарифму числа ключей, так что каждая операция поиска, вставки или удаления занимает логарифмическое время.

Описание

Древовидная структура с буквенным ключом и числовым максимальным порядком кучи

Дерево было впервые описано Раймундом Зайделем и Сесилией Р. Арагон в 1989 году; ^[1]^[2] его название является гибридом слов tree и heap . Это декартово дерево , в котором каждому ключу присваивается (случайно выбранный) числовой приоритет. Как и в любом бинарном дереве поиска, порядок обхода узлов в симметричном порядке совпадает с порядком сортировки ключей. Структура дерева определяется требованием, чтобы оно было упорядочено в куче: то есть номер приоритета для любого нелистового узла должен быть больше или равен приоритету его дочерних узлов. Таким образом, как и в случае декартовых деревьев в более общем смысле, корневой узел является узлом с максимальным приоритетом, а его левое и правое поддеревья формируются таким же образом из подпоследовательностей отсортированного порядка слева и справа от этого узла.

Эквивалентный способ описания дерева заключается в том, что оно может быть сформировано путем вставки узлов с наивысшим приоритетом в двоичное дерево поиска без выполнения какой-либо перебалансировки. Следовательно, если приоритеты являются независимыми случайными числами (из распределения по достаточно большому пространству возможных приоритетов, чтобы гарантировать, что два узла вряд ли будут иметь одинаковый приоритет), то форма дерева имеет то же распределение вероятностей, что и форма случайного двоичного дерева поиска , дерева поиска, сформированного путем вставки узлов без перебалансировки в случайно выбранном порядке вставки. Поскольку известно, что случайные двоичные деревья поиска имеют логарифмическую высоту с высокой вероятностью, то же самое верно и для деревьев. Это отражает аргумент двоичного дерева поиска о том, что быстрая сортировка выполняется за ожидаемое время. Если двоичные деревья поиска являются решениями для версии динамической задачи сортировки, то деревья соответствуют именно динамической быстрой сортировке, где приоритеты определяют выбор опорных точек. $O(n\log n)$

Арагон и Сайдель также предлагают назначать более высокие приоритеты часто используемым узлам, например, с помощью процесса, который при каждом доступе выбирает случайное число и заменяет приоритет узла этим числом, если он выше предыдущего приоритета. Эта модификация приведет к тому, что дерево потеряет свою случайную форму; вместо этого часто используемые узлы с большей вероятностью будут находиться вблизи корня дерева, что приведет к ускорению их поиска.

Наор и Ниссим ^[3] описывают приложение для поддержания сертификатов авторизации в криптосистемах с открытым ключом .

Операции

Основные операции

Treaps поддерживают следующие основные операции:

Для поиска заданного значения ключа примените стандартный алгоритм двоичного поиска в двоичном дереве поиска, игнорируя приоритеты.
Чтобы вставить новый ключ x в дерево, сгенерируйте случайный приоритет y для x . Двоичный поиск x в дереве и создайте новый узел в позиции листа, где бинарный поиск определяет, что узел для x должен существовать. Затем, пока x не является корнем дерева и имеет большее число приоритета, чем его родитель z , выполните поворот дерева , который меняет отношение родитель-потомок между x и z .
Чтобы удалить узел x из дерева, если x является листом дерева, просто удалите его. Если x имеет одного потомка z , удалите x из дерева и сделайте z потомком родителя x (или сделайте z корнем дерева, если у x нет родителя). Наконец, если x имеет двух потомков, поменяйте его положение в дереве с положением его непосредственного преемника z в отсортированном порядке, что приведет к одному из предыдущих случаев. В этом последнем случае обмен может нарушить свойство упорядочения кучи для z , поэтому для восстановления этого свойства могут потребоваться дополнительные вращения.

Строительство дерева

Чтобы построить дерево, мы можем просто вставить n значений в дерево, каждое из которых занимает время. Таким образом, дерево может быть построено за время из списка значений. $O(\log n)$ $O(n\log n)$

Массовые операции

В дополнение к операциям вставки, удаления и поиска отдельных элементов, для деревьев определены несколько быстрых «объемных» операций: union , crossing и set difference . Они опираются на две вспомогательные операции: split и join .

Чтобы разделить дерево на два меньших дерева, те, что меньше ключа x , и те, что больше ключа x , вставьте x в дерево с максимальным приоритетом — большим, чем приоритет любого узла в дереве. После этой вставки x будет корневым узлом дерева, все значения меньше x будут найдены в левом поддереве, а все значения больше x будут найдены в правом поддереве. Это стоит столько же, сколько и одна вставка в дерево.
Объединяя два дерева, которые являются продуктом предыдущего разделения, можно с уверенностью предположить, что наибольшее значение в первом дереве меньше наименьшего значения во втором дереве. Создайте новый узел со значением x , таким образом, чтобы x был больше этого максимального значения в первом дереве и меньше минимального значения во втором дереве, назначьте ему минимальный приоритет, затем установите его левого потомка в первую кучу, а его правого потомка во вторую кучу. Поверните по мере необходимости, чтобы исправить порядок кучи. После этого он станет листовым узлом и может быть легко удален. Результатом будет один дерево, объединенный из двух исходных деревьев. Это фактически «отменяет» разделение и стоит столько же. В более общем смысле, операция объединения может работать с двумя деревьями и ключом с произвольным приоритетом (т. е. не обязательно самым высоким).

{\displaystyle T_{1}} — Соединение выполняется на древовидных элементах и . Правый потомок после соединения определяется как соединение его бывшего правого потомка и . $T_{1}$ $T_{2}$ $T_{1}$ $T_{2}$

Алгоритм объединения следующий:

функция join(L, k, R) если prior(k, k(L)) и prior(k, k(R)) возвращает Node(L, k, R) если prior(k(L), k(R)) возвращает Node(left(L), k(L), join(right(L), k, R)) возвращает Node(join(L, k, left(R)), k(R), right(R))

{\displaystyle Т} — Для разделения по выполняется рекурсивный вызов split либо для левого, либо для правого дочернего элемента . $Т$ $x$ $Т$

Алгоритм разделения следующий:

функция split(T, k) если (T = nil) возвращает (nil, false, nil) (L, (m, c), R) = выставить(T) если (k = m) вернуть (L, true, R) если (k < m) (L', b, R') = разделить(L, k) вернуть (L', b, join(R', m, R)) если (k > m) (L', b, R') = разделить(R, k) возврат (join(L, m, L'), b, R'))

Объединение двух деревьев $t 1$ и $t 2$ , представляющих множества $A$ и $B$ , является деревом $t$ , представляющим $A \cup B.$ Следующий рекурсивный алгоритм вычисляет объединение:

функция union(t ₁ , t ₂ ): если t ₁ = nil: вернуть t ₂ если t ₂ = nil: вернуть t ₁ если priority(t ₁ ) < priority(t ₂ ): поменять местами t ₁ и t ₂ t _< , t _> ← разделить t ₂ по key(t ₁ ) вернуть join(union(left(t ₁ ), t _< ), key(t ₁ ), объединение(право(t ₁ ), t _> ))

Здесь предполагается , что split возвращает два дерева: одно, содержащее ключи, меньшие входного ключа, и одно, содержащее большие ключи. (Алгоритм является неразрушающим , но существует также и разрушающая версия на месте.)

Алгоритм для пересечения похож, но требует вспомогательной процедуры join . Сложность каждого из объединения, пересечения и разности составляет $O (m log ⁠ н / м ⁠)$ для деревьев размеров $m$ и $n$ , где $m \leq n$ . Более того, поскольку рекурсивные вызовы union независимы друг от друга, они могут выполняться параллельно .^[4]

Разделение и объединение вызывают объединение, но не имеют дела с критериями балансировки деревьев напрямую, такая реализация обычно называется реализацией «на основе объединения» .

Обратите внимание, что если хэш-значения ключей используются в качестве приоритетов, а структурно равные узлы объединяются уже на этапе построения, то каждый объединенный узел будет уникальным представлением набора ключей. При условии, что может быть только один одновременный корневой узел, представляющий данный набор ключей, два набора могут быть проверены на равенство путем сравнения указателей, что является постоянным во времени.

Этот метод можно использовать для улучшения алгоритмов слияния, чтобы они работали быстро, даже когда разница между двумя наборами невелика. Если входные наборы равны, функции объединения и пересечения могут немедленно прерваться, вернув один из входных наборов в качестве результата, в то время как функция разности должна возвращать пустой набор.

Пусть $d$ будет размером симметричной разности. Модифицированные алгоритмы слияния тогда также будут ограничены $O (d log ⁠ н / г ⁠)$ .^[5]^[6]

Рандомизированное двоичное дерево поиска

Рандомизированное двоичное дерево поиска, представленное Мартинесом и Роурой после работы Арагона и Зайделя по деревьям, ^[7] хранит те же узлы с тем же случайным распределением формы дерева, но поддерживает различную информацию в узлах дерева, чтобы сохранить его рандомизированную структуру.

Вместо того, чтобы хранить случайные приоритеты на каждом узле, рандомизированное двоичное дерево поиска хранит небольшое целое число на каждом узле, количество его потомков (считая себя за единицу); эти числа могут поддерживаться во время операций вращения дерева только за постоянное дополнительное количество времени на оборот. Когда ключ x должен быть вставлен в дерево, которое уже имеет n узлов, алгоритм вставки выбирает с вероятностью 1/( n + 1) поместить x в качестве нового корня дерева, а в противном случае он вызывает процедуру вставки рекурсивно, чтобы вставить x в левое или правое поддерево (в зависимости от того, меньше или больше его ключ корня). Количество потомков используется алгоритмом для вычисления необходимых вероятностей для случайного выбора на каждом шаге. Размещение x в корне поддерева может быть выполнено либо как в дереве, путем вставки его в лист и последующего вращения вверх, либо с помощью альтернативного алгоритма, описанного Мартинесом и Роурой, который разбивает поддерево на две части, которые будут использоваться в качестве левого и правого потомков нового узла.

Процедура удаления для рандомизированного бинарного дерева поиска использует ту же информацию на узел, что и процедура вставки, но в отличие от процедуры вставки, ей требуется в среднем только O(1) случайных решений для объединения двух поддеревьев, нисходящих от левого и правого потомков удаленного узла в одно дерево. Это связано с тем, что поддеревья, которые нужно объединить, в среднем находятся на глубине Θ(log n); объединение двух деревьев размером n и m требует в среднем Θ(log(n+m)) случайных выборов. Если левое или правое поддерево удаляемого узла пусто, операция объединения тривиальна; в противном случае левый или правый потомок удаленного узла выбирается в качестве нового корня поддерева с вероятностью, пропорциональной количеству его потомков, и объединение выполняется рекурсивно.

Сравнение

Информация, хранящаяся на каждом узле в рандомизированном двоичном дереве, проще, чем в дереве (небольшое целое число, а не случайное число высокой точности), но оно делает большее количество вызовов генератора случайных чисел (O(log n ) вызовов на вставку или удаление, а не один вызов на вставку), а процедура вставки немного сложнее из-за необходимости обновления количества потомков на узел. Небольшое техническое отличие состоит в том, что в дереве существует небольшая вероятность коллизии (два ключа получают одинаковый приоритет), и в обоих случаях будут статистические различия между истинным генератором случайных чисел и генератором псевдослучайных чисел, обычно используемым на цифровых компьютерах. Однако в любом случае различия между теоретической моделью идеального случайного выбора, используемой для разработки алгоритма, и возможностями реальных генераторов случайных чисел исчезающе малы.

Хотя дерево и рандомизированное бинарное дерево поиска имеют одинаковое случайное распределение форм деревьев после каждого обновления, история изменений деревьев, выполненных этими двумя структурами данных в ходе последовательности операций вставки и удаления, может различаться. Например, если в дереве три числа 1, 2 и 3 вставляются в порядке 1, 3, 2, а затем число 2 удаляется, оставшиеся два узла будут иметь те же родительско-дочерние отношения, что и до вставки среднего числа. В рандомизированном бинарном дереве поиска дерево после удаления с равной вероятностью будет любым из двух возможных деревьев на своих двух узлах, независимо от того, как выглядело дерево до вставки среднего числа.

Неявный treap

Неявный древовидный массив ^[8]^{[ ненадежный источник? ]} — это простая вариация обычного древовидного массива, которую можно рассматривать как динамический массив, поддерживающий следующие операции : $O(\log n)$

Вставка элемента в любую позицию
Удаление элемента из любой позиции
Нахождение суммы, минимального или максимального элемента в заданном диапазоне.
Сложение, покраска в заданном диапазоне
Реверсирование элементов в заданном диапазоне

Идея неявного дерева заключается в использовании индекса массива в качестве ключа, но не в его явном хранении. В противном случае обновление (вставка/удаление) приведет к изменению ключей в узлах дерева. $O(n)$

Значение ключа ( неявный ключ) узла T — это количество узлов, меньших этого узла, плюс один. Обратите внимание, что такие узлы могут присутствовать не только в его левом поддереве, но и в левых поддеревьях его предков P, если T находится в правом поддереве P.

Поэтому мы можем быстро вычислить неявный ключ текущего узла, выполняя операцию, накапливая сумму всех узлов по мере спуска по дереву. Обратите внимание, что эта сумма не меняется, когда мы посещаем левое поддерево, но она увеличится на , когда мы посещаем правое поддерево. $cnt(T\rightarrow L)+1$

Алгоритм соединения для неявного дерева выглядит следующим образом:

void join ( питем & т , питем л , питем р ) {          если ( ! л || ! р )    т = л ? л : г ;       иначе если ( l -> предыдущий > r -> предыдущий )     присоединиться ( l -> r , l -> r , r ), t = l ;       еще присоединиться ( r -> l , l , r -> l ), t = r ;       upd_cnt ( т ); }

^[8] Алгоритм разделения для неявного дерева выглядит следующим образом:

void split ( pitem t , pitem & l , pitem & r , int key , int add = 0 ) {                 если ( ! т )  вернуть пустоту ( l = r = 0 );        int cur_key = add + cnt ( t -> l ); // неявный ключ       если ( ключ <= cur_key )    разделить ( t -> l , l , t -> l , ключ , добавить ), r = t ;         еще разделить ( t -> r , t -> r , r , key , add + 1 + cnt ( t -> l )), l = t ;             upd_cnt ( т ); }

^[8]

Операции

Вставить элемент

Чтобы вставить элемент в позицию pos, мы делим массив на две подсекции [0...pos-1] и [pos..sz], вызывая функцию split , и получаем два дерева и . Затем мы объединяем с новым узлом, вызывая функцию join . Наконец, мы вызываем функцию join для объединения и . $T1$ $T2$ $T1$ $T1$ $T2$

Удалить элемент

Мы находим элемент, который необходимо удалить, и выполняем соединение его дочерних элементов L и R. Затем мы заменяем элемент, который необходимо удалить, деревом, полученным в результате операции соединения.

Найти сумму, минимум или максимум в заданном диапазоне

Для выполнения этого расчета мы поступим следующим образом:

Сначала мы создадим дополнительное поле F для хранения значения целевой функции для диапазона, представленного этим узлом. Мы создадим функцию, которая вычисляет значение F на основе значений дочерних элементов L и R узла. Мы будем вызывать эту целевую функцию в конце всех функций, которые изменяют дерево, т. е . split и join.
Во-вторых, нам нужно обработать запрос для заданного диапазона [A..B]: мы дважды вызовем функцию s split и разделим дерево на , которое содержит , которое содержит и которое содержит . После ответа на запрос мы дважды вызовем функцию join, чтобы восстановить исходное дерево. $T1$ $\{1..A-1\}$ $T2$ $\{A..B\}$ $T3$ $\{B+1..n\}$

Сложение/окрашивание в заданном диапазоне

Для выполнения этой операции мы поступим следующим образом:

Мы создадим дополнительное поле D, которое будет содержать добавленное значение для поддерева. Мы создадим функцию push , которая будет использоваться для распространения этого изменения от узла к его потомкам. Мы будем вызывать эту функцию в начале всех функций, которые изменяют дерево, т. е . split и join, чтобы после любых изменений, внесенных в дерево, информация не терялась.

Реверс в заданном диапазоне

Чтобы показать, что поддерево данного узла необходимо перевернуть для каждого узла, мы создадим дополнительное логическое поле R и установим его значение в true. Чтобы распространить это изменение, мы поменяем местами дочерние элементы узла и установим R в true для всех них.

Смотрите также

Дерево сегментов для суммы, минимума или максимума. Дерево сегментов Википедии посвящено вычислительной геометрии, а запросы типа суммы описаны в дереве Фенвика , которое является неявным деревом и не совместимо со вставкой и удалением в середине. Если неявное дерево невозможно, используется явное дерево, называемое деревом сегментов , но в Википедии нет подходящей страницы
Дерево статистики порядка для индексации. Это как сегментное дерево, предназначенное для суммирования "1" в каждом узле

Смотрите также

Поиск пальцем

Ссылки

^ Арагон, Сесилия Р.; Зайдель, Раймунд (1989), «Рандомизированные деревья поиска» (PDF) , 30-й ежегодный симпозиум по основам компьютерной науки , Вашингтон, округ Колумбия: IEEE Computer Society Press, стр. 540–545 , doi :10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1
^ Зайдель, Раймунд; Арагон, Сесилия Р. (1996), «Случайные деревья поиска», Algorithmica , 16 (4/5): 464– 497, doi :10.1007/s004539900061 (неактивен 1 ноября 2024 г.){{citation}}: CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )
^ Наор, М.; Ниссим, К. (апрель 2000 г.), «Отзыв сертификата и обновление сертификата» (PDF) , Журнал IEEE по избранным областям в коммуникациях , 18 (4): 561– 570, doi :10.1109/49.839932, S2CID 13833836 ^{[ постоянная неработающая ссылка ‍ ]} .
^ Blelloch, Guy E.; Reid-Miller, Margaret (1998), "Быстрые операции над множествами с использованием treaps", Труды десятого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам - SPAA '98 , Нью-Йорк, США: ACM, стр. 16–26 , doi :10.1145/277651.277660, ISBN 0-89791-989-0, S2CID 7342709.
^ Лильензин, Олле (2013). «Конфлюэнтно персистентные множества и отображения». arXiv : 1301.3388 . Bibcode :2013arXiv1301.3388L. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
^ Конфлюэнтные множества и карты на GitHub
^ Мартинес, Конрадо; Роура, Сальвадор (1997), «Рандомизированные бинарные деревья поиска», Журнал ACM , 45 (2): 288–323 , doi : 10.1145/274787.274812 , S2CID 714621
^ abc "Treap - Competitive Programming Algorithms". cp-algorithms.com . Получено 21.11.2021 .

Внешние ссылки

Сборник ссылок и информации по теме «Treap» от Сесилии Арагон
Открытые структуры данных - Раздел 7.2 - Treap: Рандомизированное двоичное дерево поиска, Пэт Морин
Анимированный треп
Рандомизированные бинарные деревья поиска. Конспект лекций с курса Джеффа Эриксона в UIUC. Несмотря на название, речь идет в первую очередь о treaps и skip lists ; рандомизированные бинарные деревья поиска упоминаются лишь вкратце.
Высокопроизводительное хранилище ключей и значений на основе treap от Junyi Sun
Реализация treaps на VB6. Реализация treaps на Visual Basic 6 как COM-объекта.
Реализация ActionScript3 дерева
Чистый Python и Cython in-memory treap и duptreap
Treaps в C#. Рой Клеммонс
Чистый Go в памяти, неизменяемые treaps
Библиотека хранения пар «ключ-значение» Pure Go с постоянными трепами

[paper89-1] Арагон, Сесилия Р.; Зайдель, Раймунд (1989), «Рандомизированные деревья поиска» (PDF) , 30-й ежегодный симпозиум по основам компьютерной науки , Вашингтон, округ Колумбия: IEEE Computer Society Press, стр. 540–545 , doi :10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1

[paper96-2] Зайдель, Раймунд; Арагон, Сесилия Р. (1996), «Случайные деревья поиска», Algorithmica , 16 (4/5): 464– 497, doi :10.1007/s004539900061 (неактивен 1 ноября 2024 г.){{citation}}: CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )

[3] Наор, М.; Ниссим, К. (апрель 2000 г.), «Отзыв сертификата и обновление сертификата» (PDF) , Журнал IEEE по избранным областям в коммуникациях , 18 (4): 561– 570, doi :10.1109/49.839932, S2CID 13833836 ^{[ постоянная неработающая ссылка ‍ ]} .

[4] Blelloch, Guy E.; Reid-Miller, Margaret (1998), "Быстрые операции над множествами с использованием treaps", Труды десятого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам - SPAA '98 , Нью-Йорк, США: ACM, стр. 16–26 , doi :10.1145/277651.277660, ISBN 0-89791-989-0, S2CID 7342709.

[5] Лильензин, Олле (2013). «Конфлюэнтно персистентные множества и отображения». arXiv : 1301.3388 . Bibcode :2013arXiv1301.3388L. {{cite journal}}: Цитировать журнал требует |journal=( помощь )

[Confluent_Sets_and_Maps-6] Конфлюэнтные множества и карты на GitHub

[7] Мартинес, Конрадо; Роура, Сальвадор (1997), «Рандомизированные бинарные деревья поиска», Журнал ACM , 45 (2): 288–323 , doi : 10.1145/274787.274812 , S2CID 714621

[:0-8] "Treap - Competitive Programming Algorithms". cp-algorithms.com . Получено 21.11.2021 .