data structures - Cuándo usar una trampa

data-structures treap

Question

¿Alguien puede dar ejemplos reales de cuándo es la mejor manera de almacenar sus datos?

Quiero entender en qué situaciones el tratamiento será mejor que montones y estructuras de árbol.

Si es posible, proporcione algunos ejemplos de situaciones reales.

Intenté buscar casos de uso de engaños aquí y buscando en Google, pero no encontré nada.

Gracias.

Answer 1

Los Treaps son una variante asombrosa del árbol de búsqueda binaria equilibrado. Existen muchos algoritmos para equilibrar árboles binarios, pero la mayoría de ellos son cosas horribles con toneladas de casos especiales para manejar. Por otro lado, es muy fácil codificar Treaps. Al hacer uso de la aleatoriedad, tenemos un BBT que se espera que tenga una altura logarítmica. Algunos buenos problemas para resolver usando treaps son: http://www.spoj.com/problems/QMAX3VN/ (nivel fácil) http://www.spoj.com/problems/GSS6/ (nivel moderado)

Answer 2

No puedo proporcionarle ningún ejemplo del mundo real. Pero utilizo los treaps para resolver algunos problemas en los concursos de programación:

• http://poj.org/problem?id=2761
• http://poj.org/problem?id=3481

Estos no son realmente problemas reales , pero tienen sentido.

Answer 3

Puede usarlo como una implementación de mapa basada en árbol. Dependiendo de la aplicación, podría ser más rápido . Hace un par de años implementé una Treap y una lista de omisiones (en Java) solo por diversión e hice algunos benchmarking básicos comparándolos con TreeMap, y el Treap fue el más rápido. Puedes ver los resultados aquí .

Una de sus mayores ventajas es que es muy fácil de implementar, en comparación con los árboles rojo-negro, por ejemplo. Sin embargo, por lo que recuerdo, no tiene un costo garantizado en sus operaciones (la búsqueda es O (log n) con high probabilidad), en comparación con los árboles Rojo-Negros, lo que significa que no sería capaz de Úselo en aplicaciones de seguridad crítica donde un límite de tiempo específico es un requisito.

Answer 4

Si los valores hash se usan como prioridades, los tramposos proporcionan una representación única del contenido.

Considere un conjunto de pedidos de elementos implementados como árbol AVL o árbol rb. Insertar elementos en diferentes órdenes normalmente terminará en árboles con diferentes formas (aunque todos ellos están equilibrados). Para un contenido dado, un fraude siempre tendrá la misma forma independientemente de la historia.

He visto dos razones por las que la representación única podría ser útil:

1. Razones de seguridad. Una trampa no puede contener información sobre el historial.
2. Compartimiento de subárboles eficiente. Los algoritmos más rápidos para las operaciones de conjunto que he visto usan ataques.