Treap с неявными ключами
Есть структура данных, называемая treap: это рандомизированное двоичное дерево поиска, которое также представляет собой кучу случайно сгенерированных так называемых «приоритетов».
Есть вариант этой структуры, где ключи неявны, они не хранятся в дереве, но мы рассматриваем упорядоченный индекс узла в дереве как ключ этого узла. Нам нужно хранить размер поддерева в каждом узле вместо ключа. Этот метод позволяет нам думать о treap как о неком массиве, который поддерживает множество операций за время O (log N): вставку, удаление, реверсирование подмассива, изменение в интервале и так далее.
Я немного знаю об этой структуре, но не так много. Я попытался погуглить, но нашел только много статей о самом treap, но ничего об этом "неявном treap" / "индексированном списке". Я даже не знаю его названия, потому что мой родной язык не английский, а в лекции, которую я слушал, использовался родной термин структуры, а не исходный английский. Этот родной термин можно напрямую перевести на английский как «Treap по неявным ключам» или «Декартово дерево по неявным ключам».
Кто-нибудь может указать мне на статью об этой структуре или назвать ее первоначальное название? Спасибо.
P.S.Извините, если мой английский был недостаточно понятным.
UPD: Некоторые дополнительные пояснения к структуре, которую я ищу.
Рассмотрим обычный treap со случайно выбранными приоритетами и ключами, которые представляют собой фактические данные пользователя, хранящиеся в дереве. Затем представим, что в каждом узле хранится какая-то другая информация о пользователе, а ключи - это не что иное, как ключи поиска. Следующим шагом является вычисление и поддержание размера поддерева в каждом узле: мы должны обновлять этот параметр после каждого слияния / разделения / добавления / удаления, но он позволяет нам найти, например, K-й элемент дерева в O (log N) время.
Когда у нас есть размеры поддерева в каждом узле, мы можем отбросить ключи и представить себе, что treap представляет собой массив пользовательских данных в обходе по порядку. Индекс массива каждого элемента может быть легко вычислен по размерам поддерева. Теперь мы можем добавить / удалить элемент в середине массива или разделить этот массив - и все это за время O (log N).
Мы также можем выполнить «множественную» операцию - например, добавить постоянное значение ко всем элементам нашего «массива». Чтобы реализовать это, мы должны сделать эту операцию отложенной, добавить параметр в каждый узел, который представляет задержанную константу, которая должна быть «позже» добавлена ко всем элементам подмассива этого узла, и «подтолкнуть» изменения вверх вниз, как необходимо. Добавление константы к подмассиву или рисование (маркировка) подмассива может быть отложено таким образом, как реверсирование подмассива (здесь задержанная информация в узле в битовом «подмассиве должна быть перевернута») и так далее.
UPD2: Вот фрагмент кода - часть небольшого количества информации, которую я нашел.Не обращайте внимания на кириллицу :) Слова «с неявным ключом» в прямом переводе означают «с неявным ключом».
2 ответа
Ключевая идея (не каламбур!) В treaps заключается в использовании ключей, которые рандомизированы. Если вы удалите ключи, я не понимаю, как вы можете получить травму: так что, возможно, я неправильно понял ваш вопрос. Или, возможно, вы имеете в виду альтернативу treaps рандомизированное двоичное дерево поиска . Обе структуры данных используют ту же идею, что вы можете достичь средней сложности, убедившись, что ваше дерево выглядит как среднее дерево (вместо патологического случая).
С помощью treaps вы делаете это, используя случайные приоритеты и балансировку.
В случае рандомизированных двоичных деревьев случайность учитывается исключительно во время построения: то есть, когда вы вставляете узел в дерево T, он имеет вероятность 1 / (size (T) + 1) оказаться в корне, где size (T) - количество узлов T; и, конечно, если узел не вставлен в корень, вы продолжаете рекурсивно, пока он не будет добавлен. (См. Статьи моей C. Martinez для подробного изучения этих деревьев.)
Эта структура данных ведет себя точно так же, как treap, но использует другой механизм, который не требует ключей.
Если это не то, что вы искали, возможно, вы могли бы поделиться некоторой дополнительной информацией: упоминал ли ваш лектор кого-нибудь, кто мог бы работать над этой структурой, где вы здесь этот лектор и какой он / вы национальности.Может показаться, что это не так, но знание вашего родного языка может быть важным ключом к разгадке, поскольку вы обычно можете привязать алгоритмы / структуры данных к конкретной стране, в которой они созданы.
Я не думаю, что у этой структуры данных есть название, поскольку это просто комбинация двух ортогональных концепций. Такие неявные ключи можно использовать практически с любой самобалансирующейся древовидной структурой.
Возможно, вы захотите взглянуть на деревья козлов отпущения, поскольку они уже используют размер поддерева для перебалансировки и не требуют дополнительных затрат на каждый узел.