Treap

Un treap con llaves alfabéticas y prioridades numéricas en un heap de máximo.

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.[1][2] Es un Árbol Cartesiano en el cual cada llave es un número escogido aleatoriamente. Como cualquier árbol binario de búsqueda el recorrido in-orden es el mismo que las llaves ordenadas. La estructura del árbol está determinada por el orden de un heap máximo: esto es, el número de prioridad para cualquier nodo interno es mayor o igual que la prioridad de sus hijos.

Una manera equivalente de describir el treap, es insertando los nodos con mayor prioridad primero en un árbol binario de búsqueda sin balancear. Por tanto, si las prioridades son números aleatorios independientes (de una distribución sobre un espacio suficientemente grande como para asegurar que dos nodos no compartan la misma prioridad con una alta probabilidad) entonces la forma de un treap tiene la misma distribución de probabilidad que un árbol binario de búsqueda aleatorio, un árbol de búsqueda formado por insertar las llaves de forma aleatoria sin realizar balanceo. 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.

Naor y Nissim describen una aplicación del treap para mantener certificados de autorización y criptosistemas de llave pública.[3]

El treap soporta las siguientes operaciones básicas:

• Para buscar un valor de una llave dada, se aplica el algoritmo de búsqueda estándar sobre un árbol binario de búsqueda ignorando las prioridades.
• Para insertar una nueva llave x al treap, se genera una prioridad aleatoria y para x. Luego se inserta x aplicando el algoritmo estándar de inserción sobre un árbol binario de búsqueda. Luego, mientras x no sea la raíz del árbol y tenga prioridad mayor que su padre z, realizar una rotación que intercambie la relación padre-hijo entre x y z.
• Para eliminar un nodo x del treap, si x es una hoja del árbol, sencillamente lo borramos. Si x tiene solamente un hijo z, borramos x del árbol y hacemos z hijo del padre de x (o establecemos z como raíz del árbol si x no tiene padre). Finalmente, si x tiene dos hijos, intercambio su posición en el árbol con la posición de su sucesor inmediato z cuando las llaves son ordenadas, resultando en uno de los casos anteriores. En este caso final, el intercambio puede violar la propiedad de heap para z, así que rotaciones adicionales serán necesarias para restaurar dicha propiedad.

function union(t1, t2):
    if t1 = nil:
        return t2
    if t2 = nil:
        return t1
    if priority(t1) < priority(t2):
        swap t1 and t2
    t<, t> ← split t2 on key(t1)
    return new node(key(t1),
                    union(left(t1), t<),
                    union(right(t1), t>))

El árbol binario de búsqueda aleatorio introducido por Martínez y Roura posteriormente al trabajo de Aragón y Seidel en treaps, almacena los mismos nodos con la misma distribución aleatoria de la forma del árbol, pero mantiene información diferente dentro de los nodos del árbol para mantener su estructura aleatoria.[5]

En lugar de almacenar prioridades aleatorias en cada nodo, el árbol binario de búsqueda aleatorio almacena un entero en cada nodo, representando la cantidad de descendientes (contándose a él mismo); estos números pueden ser mantenidos durante las operaciones de rotación con costo adicional O(1) por rotación. Cuando una llave x es insertada en un árbol de n nodos, el algoritmo de inserción escoge con probabilidad 1/(n + 1) colocar a x como raíz del árbol, de otra forma llama al procedimiento de inserción recursivamente en el subárbol correcto (dependiendo de si su llave es menor o mayor que la llave en la raíz). El número de descendientes es usada por el algoritmo para calcular la probabilidad necesaria en cada paso. Para ubicar a x como raíz de un subárbol, se puede proceder como en el treap: insertando x como una hoja y luego rotándola "hacia arriba" hasta convertir x en la raíz. Un algoritmo alternativo descrito por Martínez y Roura divide el subárbol en dos árboles, usados como hijo izquierdo y derecho del nuevo nodo.

La operación de borrado para un árbol binario de búsqueda aleatorio utiliza la misma información por nodo que el algoritmo de inserción, y de igual forma, realiza una secuencia de O(logn) decisiones aleatorias con el objetivo de unir los dos subárboles del nodo eliminado en solo árbol. 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.

La información almacenada por nodo en el árbol binario de búsqueda aleatorio es más simple que la almacenada en el treap (un entero simple en lugar de un número aleatorio), pero realiza un número más grande de llamadas al generador de números aleatorios (O(log n) llamados por inserción y borrado en lugar de un llamado por operación). El procedimiento de inserción en el árbol binario de búsqueda aleatorio es ligeramente más complicado que en el treap debido a la necesidad de actualizar la cantidad de descendientes en cada nodo afectado. Una diferencia técnica menor es que, en un treap, hay una probabilidad pequeña de colisión (dos llaves que consiguen la misma prioridad), y en ambos casos existirán diferencias estadísticas entre un verdadero generador de números aleatorios y un pseudo-generador de números aleatorios utilizado ordenadores digitales. No obstante, en cualquier caso, la diferencia entre la elección de un generador perfecto en la teoría y un generador de números en la práctica no aportan cambios sustanciales en el desempeño de los algoritmos.

A pesar de que el treap y el árbol binario de búsqueda aleatorio ambos tienen la misma distribución aleatoria en la forma del árbol después de cada actualización, el historial de las modificaciones a los árboles sobre una secuencia de inserciones y borrados pueden variar.

• Collection of treap references and info by Cecilia Aragon
• Open Data Structures - Section 7.2 - Treap: A Randomized Binary Search Tree
• Treap Applet by Kubo Kovac
• Animated treap
• Randomized binary search trees. Lecture notes from a course by Jeff Erickson at UIUC. Despite the title, this is primarily about treaps and skip lists; randomized binary search trees are mentioned only briefly.
• A high performance key-value store based on treap by Junyi Sun
• VB6 implementation of treaps. Visual basic 6 implementation of treaps as a COM object.
• ActionScript3 implementation of a treap
• Pure Python and Cython in-memory treap and duptreap
• Treaps in C#. By Roy Clemmons
• Pure Go in-memory, immutable treaps
• Pure Go persistent treap key-value storage library