Треп

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

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

Описание

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

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

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

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

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

Операции

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

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)$ время из значений списка.

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

В дополнение к операциям вставки, удаления и поиска отдельных элементов, для трепов определены несколько быстрых «массовых» операций: объединение , пересечение и установка разности . Они полагаются на две вспомогательные операции: Split и Join .

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

Присоединяйтесь в исполнении на трепе $T_{1}$ и $T_{2}$. Правый ребенок $T_{1}$ после того, как объединение определено как объединение его бывшего правого дочернего элемента и $T_{2}$.

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

function join(L, k, R)    if prior(k, k(L)) and prior(k, k(R)) return Node(L, k, R)    if prior(k(L), k(R)) return Node(left(L), k(L), join(right(L), k, R))    return Node(join(L, k, left(R)), k(R), right(R))

Разделить $T$ к $x$рекурсивный вызов разделения выполняется либо для левого, либо для правого дочернего элемента $T$.

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

function split(T, k)    if (T = nil) return (nil, false, nil)    (L, (m, c), R) = expose(T)    if (k = m) return (L, true, R)    if (k < m)         (L', b, R') = split(L, k)        return (L', b, join(R', m, R))    if (k > m)         (L', b, R') = split(R, k)        return (join(L, m, L'), b, R'))

Объединение двух трепов t ₁ и t ₂ , представляющих множества A и B, представляет собой треп t , представляющий A ∪ B . Следующий рекурсивный алгоритм вычисляет объединение:

function union(t1, t2):    if t1 = nil:        return t2    if t2 = nil:        return t1    if priority(t1) < priority(t2):        swap t1 and t2    t<, t> ← split t2 on key(t1)    return join(union(left(t1), t<), key(t1),                    union(right(t1), t>))

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

Алгоритм пересечения аналогичен, но требует вспомогательной процедуры соединения . Сложность каждого объединения, пересечения и разности равна O ( m log ⁠ n / m ⁠ ) для лотков размеров m и n , где m ≤ n . Более того, поскольку рекурсивные вызовы объединения независимы друг от друга, они могут выполняться параллельно .

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

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

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

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

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

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

Вместо того, чтобы хранить случайные приоритеты на каждом узле, рандомизированное двоичное дерево поиска хранит небольшое целое число в каждом узле - количество его потомков (считая себя за одно); эти числа могут поддерживаться во время операций ротации дерева только с постоянным дополнительным количеством времени на каждый оборот. Когда ключ 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 удалено, оставшиеся два узла будут иметь те же отношения родитель-потомок, что и они. сделал до вставки среднего числа. В рандомизированном бинарном дереве поиска дерево после удаления с равной вероятностью будет любым из двух возможных деревьев в двух его узлах, независимо от того, как дерево выглядело до вставки среднего числа.

По умолчанию я иду

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

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

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

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

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

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

void join (pitem & t, pitem l, pitem r) {    if (!l || !r)        t = l ? l : r;    else if (l->prior > r->prior)        join (l->r, l->r, r),  t = l;    else        join (r->l, l, r->l),  t = r;    upd_cnt (t);}

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

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {    if (!t)        return void( l = r = 0 );    int cur_key = add + cnt(t->l); //implicit key    if (key <= cur_key)        split (t->l, l, t->l, key, add),  r = t;    else        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;    upd_cnt (t);}

Операции

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

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

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

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

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

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

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

Дополнение/покраска в заданном диапазоне

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

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

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

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

См. также

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

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

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