¡Gracias Treaps!Leandro Rabindranath León |
Como muchos lo saben, los árboles binarios de búsqueda son muy simples de instrumentar y sus desempeño puede ser espectacular si el orden de inserción de claves es aleatorio. Lamentablemente no siempre se puede garantizar aleatoriedad en la inserción. Por esto, desde hace más de 50 años los investigadores en algoritmos han buscado y encontrado esquemas para equilibrar árboles binarios de búsqueda. Podemos clasificar los esquemas en tres tipos:
- Equilibrio aleatorizado: hacemos cosas al azar de modo tal que se “filtre” cualquier sesgo en las operaciones.Los principales exponentes de estos tipos de árbol son los árboles aleatorizados y los treaps.
- Equilibrio garantizado: imponemos sobre el árbol alguna condición que supedite el desequilibrio entre las ramas de los nodos de modo tal de tener una garantía. Ejemplos de estos árboles son lo AVL y los rojo-negro; ambos garantizan la altura máxima del árbol a O(lnn); donde n es el número de claves. Sin embargo, a pesar de esta garantía, los algoritmos son complejos y el coste constante para garantizar el equilibrio se recompensa cuando se tienen muchísimas claves.
- Equilibrio amortizado: hacemos algunas operaciones que a la larga deparan en un coste promedio de lgn. El exponente más popular de este tipo de estructura es el árbol splay. Es relativamente simple y rápido cuando hay localidad de referencia, pero el coste constante por la operaciones amortizadas es importante y se recompensa para aplicaciones que explotan la localidad de referencia.
Este post está estructurado en una introducción en la cual presentaré los árboles binarios de búsqueda, para aquellos que no lo recuerden bien, y el heap. Ambas estructuras son de interés para comprender el treap. Después presentaré el treap, la idea, los algoritmos, su análisis y otras consideraciones. Para que no me acusen de falta de rigor, al final pongo el análisis de los árboles binarios de búsqueda.
Contents
- 1 Introducción
- 2 Treap
- 3 Conclusión
- 4 Opcional: análisis de los ABB
1 Introducción
Para comprender el treap es necesario entender las dos estructuras de datos que lo fundamentan: árbol binario de búsqueda y heap.1.1 Árbol binario de búsqueda
Con base a que T = ∅ es un árbol binario de búsqueda (ABB), un árbol binario T = <LLINK(T), ni, RLINK(T)>, con raíz ni se le dice “de búsqueda” si y sólo si:
|
- El recorrido infijo (o preorden) del árbol es completamente ordenado. Para corroborarlo, proyecta perpendicularmente los nodos del árbol anterior sobre una línea horizontal situada debajo del árbol; verás que las claves están ordenadas.
- El menor elemento es el nodo más a la izquierda.
- El mayor elemento es el nodo más a la derecha
1.1.1 Búsqueda
Un ABB pretende emular la búsqueda binaria. La raíz divide el conjunto de claves; las menores a su izquierda, la mayores a su derecha. Una forma de aprehender el parecido con la búsqueda binaria es mirar el procedimiento de búsqueda sobre un ABB:Node * search(Node * root, const Key & key)
{
if (root == Node::NullPtr)
return Node::NullPtr; // key no se encuentra en el árbol
if (key < KEY(root))
return search(LLINK(root), key);
else if (KEY(root) < key)
return search(RLINK(root), key);
return root; // root contiene a key
}
Si key < KEY(root) entonces buscamos key en la rama
izquierda; si no, entonces comparamos KEY(root) < key, lo cual
es equivalente a efectuar key > KEY(root). De lo contrario,
concluimos key == KEY(root) y retornamos root.Si el ABB con raíz root contiene la clave key, entonces search(root, key) retorna un puntero al nodo contentivo de key ; de lo contrario, se retorna Node::NullPtr.
Para que la búsqueda sobre un ABB emule perfectamente a la búsqueda binaria, en necesario que la raíz de un ABB divida al conjunto de claves en dos partes equitativas y así recurrentemente para el resto de los nodos, tal como sucede con la búsqueda binaria sobre un arreglo.
El código anterior está extraído de ALEPH−ω ℵω, el cual puede descargarse de:
https://sourceforge.net/projects/aleph-w/
Hay algunas modificaciones respecto al código de
ALEPH−ω ℵω. En primer lugar los nombres; por ejemplo search() se
llama en ALEPH−ω ℵωsearchInBinTree(). También, ALEPH−ω ℵωmaneja una
comparación genérica la cual, si bien se omite del código anterior,
le brinda sentido a la estructura de decisión, la cual sólo usa el
operador <.Visualmente podemos tener una idea inmediata de que tanto un ABB emula a la búsqueda binaria. Simplemente miramos los nodos y que tanto se equilibran sus ramas. El árbol anterior no es perfecto, pero en el balance está equilibrado.
Si un árbol binario está equitativamente equilibrado, entonces la búsqueda es O(lgn), donde n es la cantidad de nodos que contiene el árbol.
1.1.2 Inserción
La inserción es ligeramente más complicada, pero aún muy simple:Node * insert(Node *& root, Node * p)
{
if (root == Node::NullPtr)
return root = p; // encontré árbol vacío donde insertar p
if (KEY(p) < KEY(root))
return insert(LLINK(root), p); // inserte en la rama izquierda
else if (KEY(root) > KEY(p))
return insert(RLINK(root), p); // inserta en la rama derecha
return Node::NullPtr; // clave repetida
}
insert() se parece a demasiado a search() porque en el
fondo es una búsqueda, pero fallida, para encontrar un árbol vacío en
el cual se colocaría el nuevo nodo. Por instancia, para el siguiente
ABB:
1.1.3 Unión exclusiva
Eliminar es más complicado que insertar, pero aún suficientemente simple si vamos por partes. La primera de ellas consiste en estudiar cómo se unen dos árboles con rangos disjuntos.Supongamos que tenemos dos árboles T< y T>. Cuando decimos que sus rangos son disjuntos queremos decir que la mayor clave de T< es menor que la menor de T>. Aclarado esto, y asumiendo que T<=tg y T>=tg, entonces T< ∪ T> se puede implementar del siguiente modo:
Node * join_exclusive(Node *& ts, Node *& tg)
{
if (ts == Node::NullPtr)
return tg;
if (tg == Node::NullPtr)
return ts;
LLINK(tg) = join_ex(RLINK(ts), LLINK(tg));
RLINK(ts) = tg;
Node * ret_val = ts;
ts = tg = Node::NullPtr; // deben quedar vacíos después del join
return ret_val;
}
La rutina se llama join_exclusive() para expresar
con el sufijo “exclusivo” que la unión (join) es
disjunta. join_exclusive() retorna la raíz de un nuevo ABB
conteniendo la unión; los árboles ts y tg devienen vacíos.En mi opinión, su sentido se explica mucho mejor pictóricamente. Supongamos que la operación se esquematiza del siguiente modo:
Habríamos podido escoger como raíz a T> en lugar de T<. La figura sería simétrica.
1.1.4 Eliminación
Ahora sí vayamos a la segunda parte de la eliminación. Si tenemos un ABB con raíz root y deseamos eliminar el nodo contentivo de la clave key, entonces podemos hacerlo de la siguiente manera:Node * remove(Node *& root, const Key & key)
{
if (root == Node::NullPtr)
return Node::NullPtr;
if (key < KEY(root))
return remove(LLINK(root), key);
else if (KEY(root) < key)
return remove(RLINK(root), key);
Node * ret_val = root; // respaldar root que se va a borrar
root = join_exclusive(LLINK(root), RLINK(root));
LLINK(ret_val) = RLINK(ret_val) = Node::NullPtr;
return ret_val;
}
De nuevo notemos es el parecido con la búsqueda, lo cual se explica
por el hecho de que para poder eliminar key primero debemos
buscarla (y encontrarla). Si key no está presente en el
árbol, entonces no hacemos nada y retornamos Node::NullPtr. De
lo contrario, la recursión en algún momento se detendrá en un nodo
root cuya clave es key. En este momento todo es
simplísimo: root será la unión exclusiva de sus ramas.1.1.5 Desempeño de los ABB
Los algoritmos sobre ABB son extraordinariamente simples, mas no su análisis, el cual, si bien no es excesivamente complicado, por estar fuera del propósito de este escrito yo lo te lo pondré como anexo al final de este escrito. Por ahora lo esencial a saber es:- Si la secuencia de inserción es aleatoria, entonces el promedio de nodos que se visitan en una búsqueda fallida al azar es O(lgn).
- Con base al resultado anterior (no demostrado; ver anexo), sabemos que una búsqueda, exitosa o fallida, tendrá un desempeño esperado de O(lgn).
- Una inserción paga una búsqueda fallida, lo demás es constante. Consecuentemente, una inserción también cuesta en promedio O(lg). Si inserciones sucesivas son aleatorias, entonces se siguen manteniendo las expectativas en torno a O(lgn),
- Las eliminaciones rompen las expectativas. Esto se intuye si se aprehende que la unión exclusiva ejecutada por la eliminación es asimétrica; en nuestro caso se escoge arbitrariamente la rama izquierda del nodo eliminado T<.
1.2 Heaps
Hace ya unos cuantos años CACM publicaba una bellísima columna llamada “Programing Pearls”, de Jon Bentley. Todas fueron excelentes, pero a la memoria de este escrito vale la pena recordar una, paráfrasis de este texto, llamada “Thanks Heaps”, la cual, por supuesto, trataba sobre el heap, una especie de árbol binario completo con las siguientes, Bentley dixit, dos propiedades fundamentales sobre un heap T_H:- Orden
- ∀ nk ∈ T_H ⇒ KEY(LLINK(ni)) > KEY(ni) ∧ KEY(RLINK(ni)) > KEY(ni), KEY(∅) = ∞. Es decir, para todo nodo nk, sus dos hijos tienen claves mayores que KEY(nk). Por simplicidad, asumimos KEY(∅) = ∞.
- Forma
- Un heap siempre tiene forma triangular; o sea:
Dicho de otro modo, un heap siempre está perfectamente equilibrado.
Puesto que la pretensión de este escrito trata sobre el treap, que no el heap, no nos enfrascaremos en analizar el heap. Basta con decir que el heap recupera el menor de todos los elementos de un conjunto en O(1) e inserta y elimina en O(lgn); las tres operaciones son deterministas; es decir, garantizadas. ¡Un desempeño espectacular pues!
En caso de que no conozcas sobre los heaps, pues nada mejor que la propia columna de Bentley:
“Programming pearls: thanks, heaps”. Jon Bentley. Communications of the ACM. Volume 28 Issue 3, March 1985. Págs 245-250
También se pueden encontrar en el siguiente compendio:
“Programming pearls”. Jon Bentley. Addison-Wesley. ISBN 0201657880.
2 Treap
El treap fue descubierto en 1980 por Jean Vuillemin y fue rigurosamente estudiado por Cecilia Aragon y Raimund Seidel. El nombre se debe a una combinación entre tree y heap; es decir, es un árbol binario de búsqueda pero con algo de heap, concretamente la propiedad de orden.Un treap es un árbol binario T en cual cada nodo ni tiene dos campos a saber:
- KEY(ni) ∈ K es la clave de búsqueda, donde K es un conjunto ordenable cualquiera.
- PRIO(ni) ∈ P es la prioridad del nodo, donde P es un conjunto ordenable cualquiera.
- Condición de orden: T es un árbol binario de búsqueda según las claves K. Dado un nodo ni, KEY(ni) refiere a su clave. Las claves K están ordenadas como en un árbol binario de búsqueda.
- Condición de prioridad: ∀ ni ∈ T, PRIO(ni) ≤ PRIO(LLINK(ni)) y PRIO(ni) ≤ PRIO(RLINK(ni)) . Dado un nodo ni, PRIO(ni) refiere a su “prioridad”. En este sentido, T es un heap: para cada nodo, las prioridades de sus hijos son mayores.
Como informalmente lo demostraremos más adelante, la enorme bondad de un treap es que si las prioridades son escogidas al azar, entonces no importa el orden en que aparezcan las claves, no importa si se intercalan eliminaciones, un treap siempre, ¡siempre!, será equivalente a un árbol binario de búsqueda construido a partir de una secuencia de inserción aleatoria.
Recordemos que un árbol binario de búsqueda construido al azar tiende a estar equitativamente equilibrado; consecuentemente, la búsqueda e inserción son O(lgn) esperado. En un treap, esta expectativa se extiende a la eliminación y a otras operaciones.
2.1 Operaciones sobre los treaps
2.1.1 Rotaciones
Para que un treap tienda a ser equilibrado como lo seria un árbol binario de búsqueda, es necesario que de vez en cuando se efectúen algunos ajustes. Hay diversos tipos de árboles de búsqueda que efectúan ajustes a efectos de equilibrar; prácticamente todos ellos emplean “rotaciones” para realizar estos ajustes.Una rotación se entiende rápidamente mediante la siguiente figura:
El recorrido infijo del árbol con raíz p es (α A β) B χ, mientras que el del árbol con raíz q es α A (β B χ ); o sea, son iguales, lo que demuestra que la rotación no afecta la propiedad de orden de un árbol binario de búsqueda.
Cuando se rota a la derecha el árbol con raíz p, el árbol resultante con raíz q pierde una unidad de altura por su rama izquierda, la cual se traduce en una ganancia de una unidad de altura por rama derecha. Simétricamente ocurre con la rotación hacia la izquierda. Esta es la característica que hace de la rotación la operación fundamental para equilibrar árboles.
La rotación hacia derecha se implanta del siguiente modo:
Node * rotate_to_right(Node * p)
{
Node * q = LLINK(p);
LLINK(p) = RLINK(q);
RLINK(q) = p;
return q;
}
La rotación hacia la izquierda es simétrica:
Node* rotate_to_left(Node * p)
{
Node * q = RLINK(p);
RLINK(p) = LLINK(q);
LLINK(q) = p;
return q;
}
Esencial notar que la rotación es O(1).2.1.2 Inserción
Dado un treap con raíz root el algoritmo general de inserción de un nodo p se puede resumir en:
- PRIO(p) = número al azar (la prioridad se escoge al azar)
- Insertar p exactamente como en un árbol binario de búsqueda.
- Rotar p de forma que éste suba de nivel hasta que su prioridad PRIO(p) sea mayor que la de su padre.
Supongamos el siguiente treap al cual recién se le acaba de insertar, como en un árbol binario de búsqueda, un nodo (38,26).
¿Y cómo se instrumenta este procedimiento? Básicamente de la misma manera en que el método genérico: inserte en un árbol binario de búsqueda y luego rote hasta restaurar la condición de prioridad:
Node * insert(Node * root, Node * p)
{
if (root == Node::NullPtr)
return p;
Node * ins_ret = NULL;
if (KEY(p) < KEY(root))
{
ins_ret = insert(LLINK(root), p);
if (ins_ret == Node::NullPtr)
return Node::NullPtr;
LLINK(root) = ins_ret;
if (PRIO(ins_ret) < PRIO(root))
return rotate_to_right(root);
else
return root;
}
else if (KEY(root) < KEY(p))
{
ins_ret = insert(RLINK(root), p);
if (ins_ret == Node::NullPtr)
return Node::NullPtr;
RLINK(root) = ins_ret;
if (PRIO(ins_ret) < PRIO(root))
return rotate_to_left(root);
else
return root;
}
return Node::NullPtr;
}
Para el análisis, es importante notar el parecido entre el algoritmo
de inserción de un árbol binario de búsqueda y éste que acabamos de presentar.2.1.3 Eliminación
La eliminación se puede plantear de dos maneras. La primera es estructuralmente idéntica a la eliminación que presentamos del árbol binario de búsqueda basada en la operación join(). La segunda, que desarrollaremos se basa en el siguiente algoritmo general:- Busque y encuentre la clave a eliminar. Sea p el nodo encontrado contentivo de la clave a eliminar (si no se encuentra la clave el algoritmo termina).
- Rote p para aumentarlo de nivel hasta que ésta devenga una hoja. En este paso no importa que p viole la propiedad de orden, pues éste será eliminado. Sin embargo, si para los puritanos, basta con asignarle a p prioridad ∞ para que las rotaciones restablezcan la condición de prioridad.
- Una vez que p devino hoja, la eliminación consiste simplemente en “cortarla” del árbol.
Un truco muy interesante
Una manera de simplificar la instrumentación del algoritmo de eliminación, la cual nos ahorra un if para verificar si alguno de los hijos es o no un nodo nulo (o árbol vacío) consiste en usar un nodo centinela para representar el árbol vacío. Así, la constante Node::NullPtr representará al nodo nulo y tendrá el mayor valor de prioridad posible. De este modo, la eliminación efectúa las rotaciones hacia los sentidos correctos sin percatarse si alguno de los hijos es o no el árbol vacío.Con este truco en mano estamos listos para presentar la instrumentación del algoritmo de eliminación:
Node * remove(Node *& root, const Key & key)
{ // 1ra parte: buscar y encontrar la clave
Node head; // cabecera auxiliar centinela
Node ** pp = &RLINK(head);
while (p != Node::NullPtr)
if (key < KEY(p))
{
pp = &LLINK(p);
p = LLINK(p);
}
else if (KEY(p) < key)
{
pp = &RLINK(p);
p = RLINK(p);
}
else
break; // clave encontrada!
if (p == Node::NullPtr)
return NULL; // clave encontrada
// 2da parte: rotar p hasta que devenga hoja
while (not (LLINK(p) == Node::NullPtr and RLINK(p) == Node::NullPtr))
if (PRIO(LLINK(p)) < PRIO(RLINK(p)))
{
*pp = rotate_to_right(p);
pp = &RLINK(*pp);
}
else
{
*pp = rotate_to_left(p);
pp = &LLINK(*pp);
}
*pp = Node::NullPtr;
p->reset();
return p;
}
La rutina retorna el nodo podado del treap si la clave key en
efecto se encuentra en árbol; o NULL en caso contrario.Notemos que la rutina es iterativa, lo que la hace más eficiente que su contraparte recursiva, pues nos ahorramos tiempo por el pase de parámetros, la instanciación de registros de activación y las llamadas recursivas.
Las dos partes usan un doble puntero pp que apunta a la celda de un nodo que contiene un puntero. Este truco nos evita volver a preguntar de que lado se encuentra el hijo.
Notemos que antes de la poda del nodo a eliminar, el estado del treap es exactamente el mismo que se habría tenido si el nodo a eliminar estuviese recién insertado.
2.1.4 Eliminación basada en el join
Podríamos basar la eliminación del treap tal como la hicimos para el árbol binario de búsqueda ; es decir, sobre la unión exclusiva. Pero para ello debemos diseñar una unión que preserve la condición de prioridad: Node * join_treaps (Node * t1, Node * t2)
{
if (t1 == Node::NullPtr)
return t2;
if (t2 == Node::NullPtr)
return t1;
if (PRIO (t1) < PRIO (t2) )
{
RLINK (t1) = join_treaps (RLINK (t1), t2);
return t1;
}
else
{
LLINK (t2) = join_treaps (t1, LLINK (t2) );
return t2;
}
}
Con este join, la eliminación del treap deviene estructuralmente
idéntica a la del árbol binario de búsqueda:
Node * remove(Node *& root, const Key & key)
{
if (root == Node::NullPtr)
return Node::NullPtr;
if (key < KEY(root))
return remove(LLINK (root), key);
else if (KEY(root) < key)
return remove(RLINK (root), key);
Node * ret_val = root;
root = join_treaps(LLINK (root), RLINK (root) );
return ret_val;
}
Esta eliminación es más simple pero ligeramente de menor desempeño que
la anterior. Si las prioridades son únicas, entonces los árboles
producidos por ambas eliminaciones son exactamente los mismos.Yo presento dos métodos de eliminación sobre el treap porque cuando plantee las demostraciones deseo ofrecer dos perspectivas para decir que la eliminación del treap es equivalente a la eliminación sobre un árbol binario de búsqueda.
2.2 La verdad sobre los treaps (análisis)
Lo que hace a un treap extraordinariamente interesante es el siguiente teorema.2.2.1 Teorema de equivalencia entre un treap y un árbol binario de búsqueda
Si las prioridades de un treap T son escogidas al azar, entonces T siempre es completamente equivalente a un árbol binario de búsqueda construido al azar.
Antes de proceder a la demostración, reflexionemos sobre las consecuencias de la verdad de este conocimiento.
Sabemos que si el orden de inserción es aleatorio, entonces un árbol binario de búsqueda tiene un desempeño de O(lgn) para la búsqueda, inserción y al menos una eliminación. Pero si el teorema es verdadero, entonces en un treap no importa en orden de inserción, pues éste será equivalente a un árbol binario de búsqueda aleatorio. Mejor aún, en el treap podemos efectuar cuantas eliminaciones queramos sin perder la esperanza de tener un tiempo O(lgn).
Pero todo esto no es verdad hasta que esté demostrado. Así que aboquémosnos a ello.
2.2.2 Lema de la unicidad del treap
Sea K = { k1, k2, …, kn } un conjunto de claves y P = { p1, p2, … pn } un conjunto de prioridades. Entonces, el conjunto { (k1, p1), (k2, p2), … (kn, pn), } ⊂ K× P tiene un único treap.La demostración es por inducción sobre la cantidad de nodos n:
- n = 1: En este caso existe un único treap conformado por un par único. El lema es cierto para n=1.
- n > 1: Ahora asumimos que el lema es cierto para todo n y verificamos su veracidad para n +1. Puesto que las prioridades son únicas, el treap de n +1 nodos sólo puede tener una raíz cuya prioridad es la menor de todas. Sea (ki, pi) el nodo raíz del treap. Una vez determinada la raíz del treap y a causa de la propiedad de orden de un ABB, el conjunto de nodos de las ramas izquierda y derecha queda determinado en K< = { (k1, p1), …, (Ki−1, pi−1) } y K> = { (ki+1, pi+1), …, (kn,pn) }, respectivamente. Por la hipótesis inductiva, K< y K>, cuyas cardinalidades son inferiores a n+1, tienen treaps únicos. El lema es cierto para todo n ▫
2.2.3 Demostración del teorema de equivalencia
Asumamos un conjunto KP = {(k1,p1),(k2,p2),…,(kn,pn)} de pares (clave,prioridad), en el cual las claves se adjudican al azar.Notemos que según el lema de la unicidad el treap resultante del conjunto KP es único, independientemente del orden en que se inserten los pares. En virtud de esto, podemos suponer una secuencia especial de inserción KP′= {(k1,p1)′,(k2,p2)′,…,(kn,pn)′} que está ordenada por prioridad; es decir, la prioridad p1 en (k1,p1)′ es mínima y pn en (kn,pn)′ máxima. Esta asunción es posible porque de todos modos, comprobado por el lema de la unicidad, el treap resultante será el mismo que el de cualquier otra secuencia de inserción. Pero la secuencia KP′ es de sumo interés en virtud de las siguientes observaciones:
-
KP′ es una secuencia aleatoria, independientemente de
que haya sido ordenada por prioridad. Probemos informalmente esta proposición mediante un ejercicio
de imaginación.
Consideremos el orden en que dispondremos que un grupo de n estudiantes se sienten en un salón de clase. Para ello supongamos que los pupitres están enumerado desde 1 hasta n según orden en la fila, luego en la columna . Si no hacemos nada, entonces el orden en que los estudiantes se sienten está sesgado por diversos factores tales como el orden de llegada, la costumbre de cada estudiante y otras cosas, pero en todo caso, la disposición de los estudiantes en los n pupitres no será aleatoria.
Ahora supongamos que cuando llega un estudiante se sortea uniformemente el pupitre donde le corresponderá sentarse . En este caso, el lugar se decide estrictamente al azar, no por algún otro factor. Ahora bien, si vemos los pupitres enumerados de 1 a n entonces las permutación de nombres de estudiantes sentados por este mecanismo aleatorio de disposición es una permutación aleatoria.
En síntesis, Los pupitres están enumerados y ordenados, pero los estudiantes están sentados al azar.
La secuencia de estudiantes es aleatoria o lo que a nuestro interés es lo mismo: la secuencia KP′ es aleatoria
Así, para un treap cualquiera, en el ejercicio de ordenar KP por prioridad y obtener KP′, éste último (KP′) es aleatorio, pues recordemos o insistamos que sabemos por el lema de la unicidad que el treap resultante será el mismo. KP′ siempre puede verse como una secuencia aleatoria. Nos resta demostrar que su treap es equivalente, idéntico, al que se obtendría con un árbol binario de búsqueda. - La secuencia KP′ no causa absolutamente ninguna rotación en el treap. En efecto, como KP′ está ordenado por prioridad, cada inserción de un par ki,pi tendrá a su padre con una prioridad menor, razón por la cual nunca habría necesidad de rotarlo. ¡Aja! pero resulta que en ausencia de rotaciones ¡la inserción en un treap es computacionalmente idéntica a la inserción en un árbol binario de búsqueda! Es decir, la tercera parte del algoritmo presentado en § 2.1.2 (“Rotar p de forma que éste suba de nivel hasta que su prioridad PRIO(p) sea mayor que la de su padre”) jamás se ejecutará. Elimina esta parte del algoritmo y lo resultante es exactamente la inserción en un árbol binario de búsqueda.
2.2.4 Consumo de espacio
Quizá la principal crítica contra el treap sea el consumo de espacio debido a la prioridad que hay que poner en cada nodo. Con claves enteras y en arquitecturas de 64 bits, cada nodo ocupa 2× 8
| + |
| + |
| = 32 bytes (1) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
Podría parecerte exagerado 4295 millones de nodos. ¡Pues no si tomamos en cuenta las aplicaciones modernas; en mi caso especial el mundo del “Data Mining”.
Existe, empero, una manera de no guardar la prioridad y así tener el mismo coste en espacio que los AVL o rojo-negro.
2.2.5 Prioridades como una función hash
El truco es extremadamente simple: en lugar de seleccionar aleatoriamente un valor de prioridad, ésta se calcula mediante una función hash h(k): —→ N que transforma la clave a un valor de prioridad. Cada vez que se desee obtener la prioridad se recalcula la función.Por supuesto, la calidad del treap depende de cuan buena sea la función hash.
3 Conclusión
Los treaps son mi primera opción a la hora de escoger un árbol binario de búsqueda. Lo que sigue es mi por qué.Por lo general, la estructuras de manipulación sobre conjuntos de claves basadas en árboles binarios manejan tiempos por operación de O(lgn). En añadidura, los árboles binarios tienen la extrema bondad de preservar el orden entre las claves, lo que le permite a un iterador mirar las claves en orden, sin sacrificio del desempeño O(lgn).
Los árboles tradicionales son muy simples, pero la esperanza O(lg n) para árboles clásicos se mantiene sí y sólo si la secuencia de inserción es aleatoria y no ocurren eliminaciones, lo cual no siempre es el caso. Por esa razón se añaden condiciones de equilibrio que traten con los sesgos. En el caso del treap es la condición de prioridad aunado a su selección aleatoria lo que rompe el sesgo y proporciona una expectativa O(lgn) para todas las condiciones, siempre y cuando la selección de prioridad sea aleatoria o, si es el caso, la función hash emule a una distribución aleatoria. El siguiente árbol de 512 claves ilustra el equilibrio de un treap:
Hechos estos planteamientos, puedo decir que mi preferencia por los treaps se resume en que su enfoque para mantener el equilibrio es el más simple que conozco. Otros árboles, los aleatorizados, splay, avl y rojo-negro, por ejemplos, tienen condiciones de equilibrio más difíciles de implementar pero, sobre todo, con mayores costes constantes.
Si el espacio es determinante, entonces yo usaría treaps que calculen su prioridad con una función hash.
Sólo si la cantidad de claves es muy grande o el consumo de memoria es determinante, entoces yo optaría por un árbol determinista; un AVL o rojo-negro, por ejemplos.
4 Opcional: análisis de los ABB
La verdad sobre los treaps depende de la verdad sobre los árbol binario de búsqueda, la cual se confirma con la proposición siguiente:Sea T un árbol binario de búsqueda de n nodos construido aleatoriamente según una secuencia de inserción aleatoria. No hay supresiones. Sean:
- Sn el número de nodos visitados durante una búsqueda exitosa, y
- Un el número de nodos visitados durante una búsqueda fallida.
|
Demostración
El número de nodos visitados en una búsqueda exitosa es la longitud del camino desde raiz(T) hasta el nodo encontrado. Si ni es el nodo encontrado, entonces |C raiz(T), ni| = nivel(ni) + 1, pues el nivel comienza desde cero. Por definición de promedio, tenemos:
|
| EPL(T) = (m −1) IPL(T) + m |T| (3) |
| S_n = |
| + 1 (4) |
|
| S_n = |
| + 1 (6) |
Supongamos que la permutación de inserción es n0 n1 n2 … nn −2 nn −1. Notemos que la cantidad de nodos que se visitan cuando se busca exitosamente el nodo ni es equivalente a uno más el número de nodos que se visitaron durante la búsqueda infructuosa que se realizó durante la inserción de ni. Esto sólo es correcto si se asume que no hay supresiones. La ausencia de supresiones garantiza que los nodos nunca cambian de lugar en el árbol. Podemos entonces decir que:
| S_i = U_i-1 + 1 (7) |
|
|
| n U_n-1 = |
| U_i + 2 (n−1) (10) |
|
|
| U_n = 2 (Hn+1 − 1) = 2Hn+1 −2 ≈ 2 ( ln (n+1) − γ) −2 ≈ 1,386 lg (n+1) ▫ (12) |
Ahora sustituimos (12) en (6):
|
- 1
- Hn = ∑i=1n1/i.
- 2
- El símbolo γ denota la
constante de Euler caracterizada por:
.γ = lim n—→∞ (Hn − lnn) ≈ 0,5772156649…
This document was translated from LATEX by HEVEA.
