Треп

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

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

Описание [ править ]

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

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

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

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

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

Массовые операции [ править ]

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

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

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

функция  join(L, k, R) 
      if  Prior(k, k(L)) и Prior(k, k(R))  возвращают  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 = ноль)  вернуть  (ноль, ложь, ноль) 
      (L, (m, c), R) = выставлять (T) 
      если  (k = m)  вернуть  (L, true, R) 
      если  (к < м)  
          (L', b, R') = расщепление(L, k) 
          return  (L', b, join(R', m, R)) 
      если  (к > м)  
          (L', b, R') = расщепление(R, k) 
          return  (join(L, m, L'), b, R'))

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

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

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

Алгоритм пересечения аналогичен, но требует вспомогательной процедуры соединения . Сложность каждого объединения, пересечения и разности равна $O ( m log .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n / m )$ для лотков размеров $m$ и $n$ , где $m \leq n$ . Более того, поскольку рекурсивные вызовы объединения независимы друг от друга, они могут выполняться параллельно . ^[4]

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

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

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

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

Неявное нарушение [ править ]

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

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

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

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

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

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

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

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

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  );    // неявный ключ 
     if   (  key   <=   cur_key  ) 
         Split   (  t  ->  l  ,   l  ,   t  ->  l  ,   key  ,   add  ),    r   =   t  ; 
      else 
         разделить   (  t  ->  r  ,   t  ->  r  ,   r  ,   key  ,   add   +   1   +   cnt  (  t  ->  l  )),    l   =   t  ; 
      upd_cnt   (  т  ); 
  }

^[8]

Операции [ править ]

Вставить элемент [ править ]

Чтобы вставить элемент в позицию 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 для всех них.

См. также [ править ]

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

Ссылки [ править ]

^ Арагон, Сесилия Р.; Зайдель, Раймунд (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 (неактивно 18 апреля 2024 г.) {{citation}}: CS1 maint: DOI неактивен по состоянию на апрель 2024 г. ( ссылка )
^ Наор, М .; Ниссим, К. (апрель 2000 г.), «Отзыв сертификата и обновление сертификата» (PDF) , Журнал IEEE по выбранным областям связи , 18 (4): 561–570, doi : 10.1109/49.839932 , S2CID 13833836 ^{[ постоянная мертвая ссылка ]}.
^ Блеллок, Гай Э.; Рейд-Миллер, Маргарет (1998), «Быстрые операции над множествами с использованием трепов», Труды десятого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам - SPAA '98 , Нью-Йорк, Нью-Йорк, США: ACM, стр. 16–26, doi : 10.1145/277651.277660 , ISBN 0-89791-989-0 , S2CID 7342709 .
^ Лильензин, Олле (2013). «Слитно устойчивые множества и карты». arXiv : 1301.3388 . Бибкод : 2013arXiv1301.3388L . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Слитные наборы и карты на GitHub
^ Мартинес, Конрадо; Роура, Сальвадор (1997), «Рандомизированные двоичные деревья поиска» , Журнал ACM , 45 (2): 288–323, doi : 10.1145/274787.274812 , S2CID 714621
^ Перейти обратно: ^а ^б ^с «Treep — Алгоритмы конкурентного программирования» . cp-algorithms.com . Проверено 21 ноября 2021 г.

Внешние ссылки [ править ]

Сборник ссылок и информации о трэпах от Сесилии Арагон.
Структуры открытых данных. Раздел 7.2. Treap: рандомизированное двоичное дерево поиска , Пэт Морин
Анимированная сокровищница
Рандомизированные бинарные деревья поиска . Конспекты лекций из курса Джеффа Эриксона в UIUC. Несмотря на название, речь идет в первую очередь о ловушках и списках пропуска ; рандомизированные двоичные деревья поиска упоминаются лишь вкратце.
Высокопроизводительный магазин «ключ-значение», основанный на Treap от Juni Sun.
Реализация ловушек в VB6 . Реализация трепов в Visual Basic 6 как COM-объекта.
Реализация ловушки в ActionScript3
Обработка и дублирование в памяти на чистом Python и Cython
Трепы в C# . Рой Клеммонс
Неизменяемые трепы в памяти Pure Go
Библиотека хранения значений ключей и значений 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 (неактивно 18 апреля 2024 г.) {{citation}}: CS1 maint: DOI неактивен по состоянию на апрель 2024 г. ( ссылка )

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

[4] Блеллок, Гай Э.; Рейд-Миллер, Маргарет (1998), «Быстрые операции над множествами с использованием трепов», Труды десятого ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам - SPAA '98 , Нью-Йорк, Нью-Йорк, США: ACM, стр. 16–26, doi : 10.1145/277651.277660 , ISBN 0-89791-989-0 , S2CID 7342709 .

[5] Лильензин, Олле (2013). «Слитно устойчивые множества и карты». arXiv : 1301.3388 . Бибкод : 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] Перейти обратно: ^а ^б ^с «Treep — Алгоритмы конкурентного программирования» . cp-algorithms.com . Проверено 21 ноября 2021 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v т Это Древовидные структуры данных
Поиск деревьев ( динамические наборы / ассоциативные массивы )	2–3 2–3–4 АА (а, б) АВЛ Б B+ Б* Б ^Икс ( Оптимально ) Бинарный поиск Танцы HTree Интервал Статистика заказов ( Наклон влево ) Красно-черный козел отпущения Распространение Т Треп УБ Сбалансированный по весу
Кучи	Двоичный Биномиальный Мостовая долина д -и Фибоначчи Левый Сопряжение Наклонный бином Перекос от Эмде Боас Слабый
Пытается	Cтрие C-trie (сжатый ADT) Хэш Радикс Суффикс Троичный поиск X-быстрый Y-быстро
пространственных данных Деревья разделения	Мяч БК БСП декартовский Гильберт Р. k -d ( неявный k -d ) М Метрика MVP Октри PH Приоритет Р Четырехместный р Р+ Р* Сегмент вице-президент Икс
Другие деревья	Крышка Экспоненциальный Фенвик Палец Индекс фрактального дерева Слияние Хэш-календарь iDistance К-и Левый ребенок, правый брат Связать/вырезать Лог-структурированное слияние Меркле ПК Диапазон SPQR Вершина