Когда полезен трепан?
В какой ситуации Treap является оптимальной структурой данных для использования? Я искал ответы на этот вопрос, но на самом деле не нашел ничего конкретного.
Есть другой stackru вопрос о том, когда использовать треп, но там нет примеров из реальной жизни.
Наиболее распространенным преимуществом, по-видимому, является то, что их гораздо проще реализовать, чем, например, красно-черное дерево, но в любом случае почти все используют заранее написанные реализации, так что это не кажется уместным.
3 ответа
Это оптимальная структура данных для использования в качестве примера в классах рандомизированных алгоритмов.
Хорошо, не обращая внимания, узкие преимущества, предложенные Арагоном и Зайделем, включают следующее.
Они просты. Да, в вашей стандартной библиотеке может быть доступно красно-черное дерево, но вполне вероятно, что оно не предоставляет достаточно хуков для выполнения некоторых интересных вещей, которые можно сделать с помощью бинарных деревьев поиска (например, статистики заказов). Разделить и объединить также намного проще.
Они занимают немного меньше места, чем красно-черные деревья, предполагая, что приоритеты вычисляются путем хеширования ключей. На практике это не имеет значения, могут ли красно-черные деревья украсть указатель на цвет.
Они могут быть быстрее, чем красно-черные деревья. Я не искал доказательств в любом случае.
Большим недостатком является то, что гарантии исполнения ожидаются. С помощью хеш-таблиц люди узнали, что забывчивый противник, предполагаемый при анализе рандомизированных алгоритмов, обычно не так уж и не замечает в реальном мире.
Я думаю, будет справедливо сказать, что трэпы были интересной идеей, но оказалось, что она не оказала большого практического воздействия. Это исследование. Что происходит.
Одно очень необычное свойство Treaps заключается в том, что они не чувствительны к порядку вставок / удалений.
Поскольку вставка / удаление происходит на основе случайного приоритета, если $ n $ элементов добавляются к пустому трепу, независимо от порядка, в котором происходит вставка, треап будет выглядеть точно так же.
Таким образом, злоумышленник не может посмотреть на треап и выяснить порядок, в котором были вставлены элементы.
В реальном примере,treapиспользуется вLFU Cacheвыполнение. Для кэша LFU используются хеш-карта и треап.
Политики кэширования называются на основе политики вытеснения. В кэше LFU мы очищаем наименее часто используемый элемент. Для этого каждый элемент содержит переменную count, которая показывает, сколько раз они использовались.
Но мы должны быть осторожны. Мы хотим убедиться, что среди элементов с минимальным количеством записей первым удаляется самый старый; в противном случае мы могли бы в конечном итоге удалять последнюю запись снова и снова, не давая ей возможности увеличить свой счетчик. Итак, мы должны следить за двумя вещами:counterиtime of insertion.