Estructura de datos Treap: árbol binario y montón

Fuentes: Treap (Cartesian tree) data structure overview

La Treap, o árbol cartesiano, es una estructura de datos que combina las propiedades de un árbol binario de búsqueda y un montón binario. Su diseño permite almacenar pares de valores (X, Y) en un árbol binario donde las claves X siguen el orden de búsqueda y las prioridades Y cumplen la propiedad de montón. Esta organización garantiza que, para cualquier nodo, todos los elementos en su subárbol izquierdo tengan X menor o igual y Y menor, mientras que en el derecho se invierte la relación de X. La estructura fue propuesta por Raimund Siedel y Cecilia Aragon en 1989.

El principal beneficio de la Treap es la complejidad de las operaciones. Al asignar prioridades aleatorias, se evita la degeneración del árbol, asegurando un tiempo de ejecución logarítmico O(log N) para insertar, buscar y eliminar elementos. Sin prioridades, el árbol podría degradarse a una lista enlazada, lo que haría las operaciones lineales. La implementación se basa en dos operaciones auxiliares: Split y Merge. Split divide el árbol en dos según una clave, mientras que Merge combina dos árboles ordenados respetando las prioridades. Estas operaciones permiten realizar insertiones, búsquedas y eliminaciones de forma eficiente. Además, la Treap soporta operaciones de construcción en tiempo lineal si los datos están ordenados, y permite la unión e intersección de árboles con complejidad O(M log(N/M)). El código de ejemplo muestra la estructura de nodo con claves, prioridades y punteros, utilizando un generador de números aleatorios para las prioridades, lo que garantiza un rendimiento predecible en la práctica.