Treap

El treap fue descrito por primera vez por Cecilia R. Aragón y Raimund Seidel en 1989; su nombre se debe a la composición de tree (árbol) con heap.

Debido a que los árboles de búsqueda aleatorios tienen altura logarítmica con alta probabilidad, igual ocurre para el treap.

Aragon y Seidel sugieren asignar prioridades más altas a los nodos con mayor frecuencia de accesos, como ejemplo, en cada acceso, se escoge un número aleatorio y se reemplaza la prioridad del nodo con dicho número si este es mayor que la prioridad del nodo.

Esta modificación provoca que el árbol pierda su forma aleatoria; en cambio, los nodos accedidos más frecuentemente estarán con mayor probabilidad cerca de la raíz, provocando búsquedas más rápidas.

Todas estas operaciones se basan en la implementación de otras dos rutinas: split (dividir) y merge (mezclar).

Si el hijo izquierdo o derecho del nodo a ser eliminado está vacío, la operación de unión es trivial; en otro caso, el hijo izquierdo o derecho del nodo eliminado es seleccionado como raíz del nuevo subárbol con probabilidad proporcionar al número de descendientes, y la unión procede recursivamente.