domingo, 29 de septiembre de 2013

¡Gracias Treaps!

¡Gracias Treaps!

¡Gracias Treaps!

Leandro Rabindranath León

Los árboles binarios de búsqueda son una de las opciones principales para manejar conjuntos en los cuales haya que insertar, buscar y eliminar rápidamente. En añadidura, los árboles binarios de búsqueda permiten obtener la secuencia ordenada en O(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:
  1. 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.
  2. 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.
  3. 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.
Puedo ufanarme de haber implementado todos estos esquemas de árboles binarios. También puedo ufanarme de haberlos usado en aplicaciones reales. Así que me siento con un poquitín de autoridad para criticarlos. En este post presentaré el treap, el cual, luego de evaluar factores tales como el tiempo de codificación, el entendimiento de los algoritmos, el desempeño y los costes de operación constantes para bajas escalas, es el primer mejor compromiso como árbol binario de búsqueda. Si en incertidumbre me preguntaran cuál de ellos elegir, sin titubear mi respuesta serían los treaps.
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

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:
  


   ∀ n< ∈ LLINK(T) ⇒ KEY(n<) < KEY(ni)      y 
   ∀ n> ∈ RLINK(T) ⇒ KEY(n>) > KEY(ni
Dicho coloquialmente, para todo nodo ni con clave KEY(ni), entonces todas las claves contenidas en su rama izquierda son menores que KEY(ni), mientras que las contenidas en su rama derecha son mayores. Este ejemplo de ABB con claves generadas al azar ayudará a constatar:
Es conveniente notar algunas cosas:
  1. 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.
  2. El menor elemento es el nodo más a la izquierda.
  3. 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:
El siguiente dibujo muestra los rangos entre corchetes en los cuales se colocarían nuevas claves:
Si vamos a insertar, por ejemplo, el 33, entonces lo colocamos en el rango [31..49] el cual está a la derecha del nodo 30. Así que buscamos el 33, lo cual nos encontrará el árbol vacío correspondiente al rango [31..49] en donde colocaremos el 33.

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:
Entonces, la unión exclusiva se expresa así:
Es decir, escogemos como raíz del resultado a T< (ts) y su rama derecha T> (tg).
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:
  1. 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).
  2. 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).
  3. 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),
  4. 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<.
En síntesis, si las inserciones son aleatorias y no tenemos eliminaciones (o efectuamos pocas), entonces el ABB es una estructura estupenda para operar muy eficientemente sobre conjuntos de claves.

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.
El siguiente árbol es un ejemplo de heap:
Como se puede apreciar, las dos propiedades se satisfacen.
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:
  1. KEY(ni) ∈ K es la clave de búsqueda, donde K es un conjunto ordenable cualquiera.
  2. PRIO(ni) ∈ P es la prioridad del nodo, donde P es un conjunto ordenable cualquiera.
Un árbol binario cuyos nodos tengan esta estructura es un treap si y sólo si:
  • 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:niT, 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.
Nada mejor que un ejemplo para terminar de aprehender el concepto:
Los campos superiores de los nodos son las claves del árbol binario de búsqueda, mientras que los inferiores las prioridades del pseudoheap.
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 árbol con raíz p se puede rotar hacia la derecha y se obtiene el árbol con raíz q. Del mismo modo, si el árbol con raíz q se rota hacia la izquierda, entonces se obtiene el original de raíz p.
El recorrido infijo del árbol con raíz p es (α A β) B χ, mientras que el del árbol con raíz q es α AB χ ); 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:
  1. PRIO(p) = número al azar (la prioridad se escoge al azar)
  2. Insertar p exactamente como en un árbol binario de búsqueda.
  3. Rotar p de forma que éste suba de nivel hasta que su prioridad PRIO(p) sea mayor que la de su padre.
Notemos que la diferencia entre este algoritmo general y el de inserción en un árbol binario de búsqueda es tan solo la línea 3.
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).
Como el nodo fue insertado como en un árbol binario de búsqueda, éste no viola la condición de orden, mas sí viola la condición de prioridad, pues 26 < 54. Así que lo que hacemos es rotar el nodo (28,54) hacia la izquierda, lo que hace que (28,54) quede por debajo de (38,26):
Pero (38,26) viola la prioridad de su padre (39,30), lo cual requiere que (39,30) sea rotado hacia la derecha:
De nuevo, (38,26) viola la condición de prioridad de su padre (12,28), lo cual acarrea su rotación hacia la izquierda, la cual depara en el siguiente resultado definitivo:
El cual ya es un treap.
¿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:
  1. 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).
  2. 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.
  3. Una vez que p devino hoja, la eliminación consiste simplemente en “cortarla” del árbol.
Sorprendentemente, el lugar por donde finalmente se elimina un nodo es exactamente el mismo por donde se insertaría. Para ello, veamos como eliminamos el nodo (38,26) del siguiente treap:
Aquí debes percatarte de que el sentido de rotación no es arbitrario. Si rotamos (38,26) hacia la izquierda, entonces el nodo (39,30) violará la condición de prioridad respecto al nodo (12,28). Por tanto, debemos rotarlo hacia la derecha, de modo tal que la menor de la prioridades de los hijos de p sea la que suba. Así, el estado del treap luego de esta rotación es:
La regla general para decidir el sentido de rotación es hacia el lado contrario de donde se encuentre su hijo de menor prioridad. Así, la siguiente rotación se efectúa hacia la izquierda, o sea hacia el lado contrario donde se encuentra su hijo derecho (39,30), lo que nos arroja el siguiente resultado:
En esta situación nos encontramos con que (38,26) “tiene un solo hijo”; así que si lo rotamos hacia el lado donde no tiene su hijo entonces (38,26) deviene una hoja:
Aquí (38,26) ya es una hoja, por lo que sólo nos queda cortarlo para que culminemos la eliminación.
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
El lema de la unicidad nos explica por qué el árbol por donde se inserta una nueva clave es idéntico al árbol por donde la misma clave se elimina: el treap siempre es único.

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:
  1. 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.
  2. 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.
Al ser KP una secuencia de inserción aleatoria, que no causa rotaciones en la inserción del treap, entonces el treap es equivalente a un árbol binario de búsqueda construido aleatoriamente; con el gran añadido de que no interesa el orden de inserción ni que ocurran eliminaciones ▪

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
 
 
2× 8


punteros
 +
 
 
8


clave
 + 
 
 
8


prioridad
= 32 bytes     (1)
Un árbol rojo-negro o uno AVL puede implementarse en 24 bytes por nodo. Si guardamos en memoria unos 4295 millones de enteros, entonces requeriríamos 30 × 32/10243 ≈ 128 Gb, mientras que con un AVL requeriríamos 30 × 24/10243 ≈ 96 Gb.
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:
En contraste, otros enfoques deterministas de equilibrio producen mejores árboles. Por ejemplo, árbol anterior como AVL se ve del siguiente modo:
Como se ve, es más o menos la mitad de altura, lo que redunda en mejores búsquedas. Sin embargo, aunque mucho mejor como árbol, el AVL conlleva un coste constante cuya recompensa se obtiene cuando se tienen muchos nodos.
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.
Entonces:
    S_n=




1 + 
1
n
 



Hn    −    3    ≈    1.386 lgn      =   O(lgn)  y 
    U_n=Hn+1    −    2    ≈    1.386 lg (n+1)      =   O(lgn)
Donde S_n y U_n denotan los promedios de Sn y Un respectivamente, mientras que Hn es el n-ésimo número armónico1.
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:
     
     S_n =
 
1
n
 
∀ ni ∈ T
 (nivel(ni) + 1)   
 
  =
 
1
n
 
∀ ni ∈ T
nivel(ni)    +    1   
 
  =
 
1
n
 IPL(T)    +    1  
    (2)
Otro teorema de los árboles binarios nos dice que:
   EPL(T) = (m −1) IPL(T) + m   |T|     (3)
Sustituimos (3) en (2):
S_n = 
EPL(T) − 2n
n
    +    1       (4)
Ahora planteamos una ecuación similar para una búsqueda infructuosa. Puesto que el nodo no se encuentra en el árbol, la búsqueda descenderá hasta un nodo externo. El número de nodos visitados en una búsqueda infructuosa es, pues, equivalente a la longitud del camino desde la raíz hasta el nodo externo. Podemos entonces plantear el promedio de longitudes entre todos los caminos desde la raíz hasta un nodo externo. Esto es:
     
U_n =
1
n+1
 
∀ nx
nx  nodo externo
     nivel(nx)   
 
  =
 
EPL(T)
n+1
 =⇒  
 
EPL(T)= (n+1) U_n        (5)
Sustituimos (5) en (4):
S_n = 
 (n+1) U_n − 2n
n
     +    1       (6)
La ecuación (6) nos plantea las dos incógnitas que intentamos encontrar. Para poder resolverla requerimos una segunda ecuación, independiente de (6), que también nos relacione S_n y U_n,
Supongamos que la permutación de inserción es n0 n1 n2nn −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)
Ahora, por la misma definición de promedio, podemos plantear una nueva ecuación:
     
     S_n=
 
 (U_0 + 1) + (U_1 + 1) + (U_2 + 1) + ⋯ + (U_n-1 + 1)
n
   
 
  =
 1    +    
1
n
n−1
i = 0
U_i   
    (8)
Igualamos (8) con (6):
     
     
 (n+1) U_n − 2n
n
     +    1
 =
 1    +    
1
n
n−1
i = 0
U_i       =⇒ 
 
     (n+1)U_n =
 
n−1
i=0
U_i     +    2n   
    (9)
Evaluamos (9) para n−1 y obtenemos:
n U_n-1 = 
n−2
i=0
U_i     +    2 (n−1)       (10)
Restamos (9) menos (10):
     
     (n+1)U_n    −    n U_n-1= U_n-1    +    2    =⇒    
     U_n =
 U_n-1 + 
2
n+1
    (11)
Lo que da una ecuación recurrente de U_n que podemos resolver por expansión sucesiva hasta el último término U_0 = 0:
     U_n=
U_n-1 + 
2
n+1
 
 =
U_n-2 + 
2
n
 + 
2
n+1
 
  
 =
U_0 + 
2
2
 + 
2
3
 + ⋯ + 
2
n−1
2
n
 + 
2
n+1
 
 =
 (
 (
 (
 (
 (
1
2
 + 
1
3
 + ⋯ + 
1
n−1
1
n
 + 
1
n+1
 



La serie ∑i=1n1/i es el n-ésimo número armónico. Así pues:
U_n  =  2 (Hn+1 − 1)  =  2Hn+1 −2  ≈        2 ( ln (n+1) − γ) −2 ≈  1,386 lg (n+1)           ▫              (12)
2
Ahora sustituimos (12) en (6):
     S_n=
 (n+1) 2 (Hn+1 − 1) − 2n
n
     +    1 
 =
n+1
n
 (2 (Hn+1 − 1))    −    1 
 =
n+1
n
  (
 (
 (
 (
 (
Hn + 
1
n+1
 − 1 



   −    1 
 =
n+1
n
 Hn − 3  ≈  2 lnn  ≈  1,386 lgn      ▪

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.

No hay comentarios:

Publicar un comentario

Estás invitado a dejar comentarios enriquecedores: críticas, errores, mejoras. etc. También puede plantear dudas o preguntas.