El treap: el árbol que combina búsqueda binaria y montículo para evitar la degeneración

Treap (Cartesian Tree)

Un treap es una estructura de datos que fusiona un árbol binario de búsqueda con un montículo binario, almacenando pares clave-prioridad. Las prioridades, asignadas aleatoriamente, garantizan que el árbol resultante sea único y equilibrado en promedio, evitando la degeneración en listas enlazadas. Con operaciones como split y merge, permite inserción, búsqueda, borrado, construcción lineal y unión en tiempo logarítmico esperado. Propuesto por Raimund Seidel y Cecilia Aragon en 1989, también se conoce como árbol cartesiano o árbol de búsqueda binaria aleatorizado.