Treap с неявными ключами

Question

Существует структура данных, называемая treap: это рандомизированное дерево двоичного поиска, которое также является кучей случайно генерируемых так называемых «приоритетов».

Существует вариант этой структуры, где ключи неявные, они не хранятся в дереве, но мы рассматриваем упорядоченный индекс узла в дереве как ключ этого узла. Нам нужно хранить размер поддерева в каждом узле вместо ключа. Этот метод позволяет нам думать о treap как о некоем массиве, который поддерживает множество операций за O (log N): вставка, удаление, возврат подмассива, изменение интервала и т. Д.

Я немного знаю об этой структуре, но не так много. Я пытался найти его в Google, но я нашел только много статей о самом Treap, но ничего об этом «неявном Treap» / «Индексированном списке». Я даже не знаю его названия, потому что мой родной язык не является английским, и лекция, которую я слушал, использовала родной термин структуры, а не английский первоначальный термин. Этот родной термин может быть непосредственно переведен на английский как «Treap на неявных ключах» или «Декартово дерево на неявных ключах».

Кто-нибудь может указать мне на статью об этой структуре или сказать мне ее первоначальное название? Спасибо.

P.S. Извините, если мой английский не был достаточно понятен.

UPD: Некоторое дополнительное объяснение о структуре, которую я ищу.

Рассмотрим обычный треп со случайно выбранными приоритетами и ключами, которые являются фактическими пользовательскими данными, хранящимися в дереве. Тогда давайте представим, что в каждом узле хранится некоторая другая пользовательская информация, а ключи - это не что иное, как ключи поиска. Следующим шагом является вычисление и поддержание размера поддерева в каждом узле: мы должны обновлять этот параметр после каждого слияния / разделения / добавления / удаления, но это позволяет нам найти, например, K-й элемент дерева в O (log N) время.

Когда у нас есть размеры поддеревьев в каждом узле, мы можем выбросить ключи и представить, что treap представляет массив пользовательских данных при прохождении по порядку. Индекс массива каждого элемента может быть легко рассчитан из размеров поддерева. Теперь мы можем добавить / удалить элемент в середине массива или разбить этот массив - все за O (log N).

Мы также можем выполнить «множественную» операцию - например, добавить постоянное значение для всех элементов нашего «массива». Чтобы реализовать это, мы должны сделать эту операцию отложенной, добавить параметр в каждом узле, который представляет задержанную константу, которую необходимо «позже» добавить ко всем элементам подмассива этого узла, и «протолкнуть» изменения вверх вниз вниз как необходимо. Добавление константы к подмассиву или окраске (маркировке) можно сделать таким образом, чтобы подрешетка была задержана, например, чтобы поменять местами подрешетку (здесь задержанная информация в узле в бите «подрешетка должна быть обращена») и т. *

UPD2: Вот фрагмент кода - часть небольшого количества информации, которую я нашел. Не замечайте кириллицу :) Слова "с неявным ключом" в прямом переводе означают "с неявным ключом".

Answer 1

Вы можете найти эту структуру данных в статье Каплана и Вербина о сортировке подписанных перестановок по обращениям (стр. 7, раздел 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf.

Answer 2

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

Answer 3

Ключевая идея (без каламбура!) В трепах заключается в использовании ключей, которые рандомизированы. Если вы удалите ключи, я не понимаю, как вы можете получить треп: так что, возможно, я неправильно понял ваш вопрос. Или, возможно, вы имеете в виду альтернативу трепам, рандомизированное двоичное дерево поиска . Обе структуры данных используют ту же идею, что вы можете достичь сложности среднего случая, убедившись, что ваше дерево выглядит как среднее дерево (а не патологический случай).

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

В рандомизированных бинарных деревьях случайность включается исключительно во время построения: то есть, когда вы вставляете узел в дерево T, он имеет вероятность 1 / (размер (T) + 1) оказаться в корне, где размер (T) - количество узлов T; и, конечно, если узел не вставлен в корень, вы продолжите рекурсивно, пока он не будет добавлен. (См. Статьи моего К. Мартинеса для детального изучения этих деревьев.)

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

Если это не то, что вы искали, возможно, вы могли бы поделиться некоторой дополнительной информацией: упомянул ли ваш лектор кого-либо, кто мог бы работать над этой структурой, где вы здесь этот лектор и какова его / ваша национальность. Может показаться, что это не так, но знание родного языка может быть важной подсказкой, поскольку вы обычно можете привязать алгоритмы / структуры данных к конкретной стране, которая его создала.

Answer 4

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

Возможно, вы захотите взглянуть на деревья козла отпущения, так как они уже используют размер поддерева для перебалансировки и не требуют никаких накладных расходов для каждого узла.