Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Treap
ТипРандомизированное двоичное дерево поиска
Сложность времени в большой нотации O
АлгоритмСреднийХудший случай
КосмосО ( п )О ( п )
ПоискO (журнал n )О ( п )
ВставлятьO (журнал n )О ( п )
УдалитьO (журнал n )О ( п )
Часть серии по
Вероятностные структуры данных
Случайные деревья
Связанный

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

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

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

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

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

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

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

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

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

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

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

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

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

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

функция join (L, k, R), если предыдущий (k, k (L)) и предыдущий (k, k (R)) возвращают Node (L, k, R), если предыдущий (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)). )

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

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

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

function union (t 1 , t 2 ): если t 1 = nil: вернуть t 2,  если t 2 = nil: вернуть t 1,  если приоритет (t 1 ) <priority (t 2 ): поменять местами t 1 и t 2 t < , t > ← разделить t 2 на ключ (t 1 ) return join (union (left (t 1 ), t < ), key (t 1 ), объединение (право (t 1 ), t > ))

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

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

Split и Union вызывают Join, но не имеют прямого отношения к критериям балансировки treaps, такая реализация обычно называется реализацией на основе соединения .

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

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

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

Рандомизированное двоичное дерево поиска [ править ]

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

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

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

Сравнение [ править ]

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

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

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

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

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

  1. ^ Арагон, Сесилия Р .; Зайдель, Раймунд (1989), "Рандомизированные деревья поиска" (PDF) , Proc. 30-й симпозиум Основы информатики и вычислительной техники (FOCS 1989) , Вашингтон, округ Колумбия: IEEE Computer Society Press, стр 540-545,. DOI : 10,1109 / SFCS.1989.63531 , ISBN 0-8186-1982-1
  2. ^ Зайдель, Раймунд; Арагон, Сесилия Р. (1996), "рандомизированное Поиск Деревья" , Algorithmica , 16 (4/5): 464-497, DOI : 10.1007 / s004539900061
  3. ^ Наор, М .; Ниссим, К. (апрель 2000 г.), «Отзыв сертификата и обновление сертификата» (PDF) , Журнал IEEE по отдельным областям коммуникаций , 18 (4): 561–570, doi : 10.1109 / 49.839932 [ постоянная мертвая ссылка ] .
  4. ^ Blelloch, Guy E .; Рейд-Миллер, Маргарет (1998), «Операции быстрого набора с использованием treaps», Proc. 10-й симпозиум ACM. Параллельные алгоритмы и Архитектуры (SPAA 1998) , Нью - Йорк, Нью - Йорк, США:. ACM, стр 16-26, DOI : 10.1145 / 277651.277660 , ISBN 0-89791-989-0.
  5. ^ Liljenzin, Олл (2013). «Конфлюентно постоянные множества и карты». arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L . Цитировать журнал требует |journal=( помощь )
  6. ^ Конфлюэнтные наборы и карты на GitHub
  7. ^ Мартинес, Конрадо; Roura, Сальвадор (1997), "рандомизированные бинарное дерево поиска" , Журнал ACM , 45 (2): 288-323, DOI : 10,1145 / 274787,274812

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

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