Треап с неявными ключами

Question

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

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

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

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

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

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

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

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

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

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

Answer 1

Вы можете найти эту структуру данных в документе Kaplan и Verbin на сортировке подписанных перестановок по разворам (стр. 7, раздел 3.1): http://www.math.jussieu.fr/~fouquet/seignement/projets/kaplan.pdf..

Answer 2

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

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

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

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

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

Answer 3

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

Answer 4

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

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