Treap с неявными ключами
Существует структура данных, называемая treap: это рандомизированное дерево двоичного поиска, которое также является кучей случайно генерируемых так называемых "приоритетов".
Существует вариант этой структуры, где ключи неявные, они не хранятся в дереве, но мы рассматриваем упорядоченный индекс узла в дереве как ключ этого узла. Нам нужно хранить размер поддерева в каждом узле вместо ключа. Этот метод позволяет нам думать о treap как о неком массиве, который поддерживает множество операций за O(log N): вставка, удаление, реверсирование подмассива, изменение интервала и так далее.
Я немного знаю об этой структуре, но не так много. Я пытался найти его в Google, но я нашел только много статей о самом Treap, но ничего об этом "неявном Treap" / "Индексированном списке". Я даже не знаю его названия, потому что мой родной язык не является английским, и лекция, которую я слушал, использовала родной термин структуры, а не английский первоначальный термин. Этот родной термин может быть непосредственно переведен на английский как "Treap на неявных ключах" или "Декартово дерево на неявных ключах".
Кто-нибудь может указать мне на статью об этой структуре или сказать мне ее первоначальное название? Спасибо.
PS Извините, если мой английский не был достаточно понятен.
UPD: какое-то дополнительное объяснение о структуре, которую я ищу.
Рассмотрим обычный трэп со случайно выбранными приоритетами и ключами, которые являются фактическими пользовательскими данными, хранящимися в дереве. Тогда давайте представим, что в каждом узле хранится некоторая другая пользовательская информация, а ключи - это не что иное, как ключи поиска. Следующим шагом является вычисление и поддержание размера поддерева в каждом узле: мы должны обновлять этот параметр после каждого слияния / разделения / добавления / удаления, но это позволяет нам найти, например, K-й элемент дерева в O(log N) время.
Когда у нас есть размеры поддеревьев в каждом узле, мы можем выбросить ключи и представить, что treap представляет массив пользовательских данных при прохождении по порядку. Индекс массива каждого элемента может быть легко рассчитан из размеров поддерева. Теперь мы можем добавить / удалить элемент в середине массива или разбить этот массив - все за O(log N) времени.
Мы также можем выполнить "множественную" операцию - например, добавить постоянное значение для всех элементов нашего "массива". Чтобы реализовать это, мы должны сделать эту операцию отложенной, добавить параметр в каждом узле, который представляет задержанную константу, которую необходимо "позже" добавить ко всем элементам подмассива этого узла, и "подтолкнуть" изменения вверх вниз вниз как необходимо. Добавление константы к подмассиву или окраске (маркировке) можно сделать таким образом, чтобы подрешетка была задержана, например, чтобы поменять местами подрешетку (здесь задержанная информация в узле в бите "подрешетка должна быть обращена"), и так далее.
UPD2: Вот фрагмент кода - часть небольшого количества информации, которую я нашел. Не замечайте кириллицы:) Слова "с неявным ключом" означают в прямом переводе "с неявным ключом".
4 ответа
Вы можете найти эту структуру данных в статье Каплана и Вербина о сортировке подписанных перестановок по обращениям (стр. 7, раздел 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf.
Ключевая идея (не каламбур!) В трепах заключается в использовании ключей, которые рандомизированы. Если вы уберете ключи, я не понимаю, как вы можете получить треп: так что, возможно, я неправильно понял ваш вопрос. Или, возможно, вы имеете в виду альтернативу трепам, рандомизированное бинарное дерево поиска. Обе структуры данных используют ту же идею, что вы можете достичь сложности среднего случая, убедившись, что ваше дерево выглядит как среднее дерево (а не патологический случай).
С трепами вы делаете это, используя случайные приоритеты и балансировку.
В рандомизированных бинарных деревьях случайность включается исключительно во время построения: то есть, когда вы вставляете узел в дерево T, он имеет вероятность 1/(размер (T) + 1) оказаться в корне, где размер (T) число узлов Т; и, конечно, если узел не вставлен в корень, вы продолжите рекурсивно, пока он не будет добавлен. (См. Статьи моего К. Мартинеса для детального изучения этих деревьев.)
Эта структура данных ведет себя точно так же, как и Treap, но использует другой механизм, который не требует ключей.
Если это не то, что вы искали, возможно, вы могли бы поделиться некоторой дополнительной информацией: упомянул ли ваш лектор кого-либо, кто мог бы работать над этой структурой, где вы здесь этот лектор и какова его / ваша национальность. Может показаться, что это не так, но знание вашего родного языка может быть важной подсказкой, поскольку вы обычно можете привязать алгоритмы / структуры данных к конкретной стране, которая его создала.
Возможно, вы ищете веревку (сложную форму строки), модифицированную для ваших потребностей в отложенных операциях. Интересно, что прямо сейчас здесь есть открытый вопрос о веревках.
Я не думаю, что есть название для этой структуры данных, поскольку это просто комбинация двух ортогональных концепций. Вы можете использовать такие неявные ключи практически с любой самобалансирующейся структурой данных дерева.
Возможно, вы захотите взглянуть на деревья козла отпущения, так как они уже используют размер поддерева для перебалансировки и не требуют никаких накладных расходов для каждого узла.