Когда использовать трейп

Может ли кто-нибудь представить реальные примеры того, когда лучший способ хранить ваши данные - это treap?

Я хочу понять, в каких ситуациях treap будет лучше, чем кучи и древовидные структуры.

Если возможно, предоставьте несколько примеров из реальных ситуаций.

Я попытался найти случаи использования treaps здесь и при помощи googling, но ничего не нашел.

Спасибо.

Ответы

Ответ 1

Если хеш-значения используются в качестве приоритетов, treaps предоставляют уникальное представление содержимого.

Рассмотрим набор заказов, реализованный как дерево AVL или rb-дерево. Вставка элементов в разные заказы обычно заканчивается деревьями с разными формами (хотя все они сбалансированы). Для данного контента treap всегда будет иметь одинаковую форму независимо от истории.

Я видел две причины, почему уникальное представление может быть полезно:

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

Ответ 2

Я не могу представить вам какие-либо реальные примеры. Но я использую treaps для решения некоторых проблем в конкурсах программирования:

Это не настоящие реальные проблемы, но они имеют смысл.

Ответ 3

Treaps - это отличный вариант сбалансированного дерева двоичного поиска. Существует множество алгоритмов для балансировки бинарных деревьев, но большинство из них - ужасные вещи, с которыми обрабатываются тонны особых случаев. С другой стороны, очень легко закодировать Treaps. Пользуясь случайностью, у нас есть BBT, который, как ожидается, будет иметь логарифмическую высоту. Некоторые хорошие проблемы для решения проблемы использования - http://www.spoj.com/problems/QMAX3VN/ (простой уровень) http://www.spoj.com/problems/GSS6/ (умеренный уровень)

Ответ 4

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

Одно из самых больших преимуществ заключается в том, что его очень легко реализовать, например, по сравнению с красно-черными деревьями. Однако, насколько я помню, у него нет гарантированных затрат на его операции (поиск O (log n) с вероятностью high) по сравнению с красно-черными деревьями, что означает, что вы не были бы способный использовать его в критичных для безопасности приложениях, где требуется конкретная временная привязка.