Arbol biselado

Árbol biselado. Concepto: Árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores.

Un Árbol biselado o Árbol Splay es un Árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores. Realiza operaciones básicas como pueden ser la inserción, la búsqueda y el borrado en un tiempo del orden de O(log n). Para muchas secuencias no uniformes de operaciones, el árbol biselado se comporta mejor que otros árboles de búsqueda, incluso cuando el patrón específico de la secuencia es desconocido. Esta estructura de datos fue inventada por Robert Tarjan y Daniel Sleator.

Todas las operaciones normales de un árbol binario de búsqueda son combinadas con una operación básica, llamada biselación. Esta operación consiste en reorganizar el árbol para un cierto elemento, colocando éste en la raíz. Una manera de hacerlo es realizando primero una búsqueda binaria en el árbol para encontrar el elemento en cuestión y, a continuación, usar rotaciones de árboles de una manera específica para traer el elemento a la cima. Alternativamente, un algoritmo "de arriba a abajo" puede combinar la búsqueda y la reorganización del árbol en una sola fase.

Ventajas e inconvenientes

El buen rendimiento de un árbol biselado depende del hecho de que es auto-balanceado, y además se optimiza automáticamente. Los nodos accedidos con más frecuencia se moverán cerca de la raíz donde podrán ser accedidos más rápidamente. Esto es una ventaja para casi todas las aplicaciones, y es particularmente útil para implementar cachés y algoritmos de recolección de basura; sin embargo, es importante apuntar que para un acceso uniforme, el rendimiento de un árbol biselado será considerablemente peor que un árbol de búsqueda binaria balanceado simple.

Los árboles biselados también tienen la ventaja de ser consideradamente más simples de implementar que otros árboles binarios de búsqueda auto-balanceados, como pueden ser los árboles Rojo-Negro o los árboles AVL, mientras que su rendimiento en el caso promedio es igual de eficiente. Además, los árboles biselados no necesitan almacenar ninguna otra información adicional a parte de los propios datos, minimizando de este modo los requerimientos de memoria. Sin embargo, estas estructuras de datos adicionales proporcionan garantías para el peor caso, y pueden ser más eficientes en la práctica para el acceso uniforme.

Uno de los peores casos para el algoritmo básico del árbol biselado es el acceso secuencial a todos los elementos del árbol de forma ordenada. Esto deja el árbol completamente des balanceado (son necesarios n accesos, cada uno de los cuales del orden de O(log n) operaciones). Volviendo a acceder al primer elemento se dispara una operación que toma del orden de O(n) operaciones para volver a balancear el árbol antes de devolver este primer elemento. Esto es un retraso significativo para esa operación final, aunque el rendimiento se amortiza si tenemos en cuenta la secuencia completa, que es del orden de O(log n). Sin embargo, investigaciones recientes muestran que si aleatoriamente volvemos a balancear el árbo podemos evitar este efecto de desbalance y dar un rendimiento similar a otros algoritmos de auto-balanceo.

Al contrario que otros tipos de árboles auto balanceados, los árboles biselados trabajan bien con nodos que contienen claves idénticas. Incluso con claves idénticas, el rendimiento permanece amortizado del orden de O(log n). Todas las operaciones del árbol preservan el orden de los nodos idénticos dentro del árbol, lo cual es una propiedad similar a la estabilidad de los algoritmos de ordenación.

Operaciones

Búsqueda

La búsqueda de un valor de clave en un árbol biselado tiene la característica particular de que modifica la estructura del árbol. El descenso se efectúa de la misma manera que un árbol binario de búsqueda, pero si se encuentra un nodo cuyo valor de clave coincide con el buscado, se realiza una biselación de ese nodo. Si no se encuentra, el nodo biselado será aquel que visitamos por último antes de descartar la búsqueda. Así, la raíz contendrá un sucesor o predecesor del nodo buscado.

Inserción

Es igual que en el árbol binario de búsqueda con la salvedad de que se realiza una biselación sobre el nodo insertado. Además, si el valor de clave a insertar ya existe en el árbol, se bisela el nodo que lo contiene.

Eliminación

Esta operación requiere dos biselaciones. Primero se busca el nodo que contiene el valor de clave que se debe extraer. Si no se encuentra, el árbol es biselado en el último nodo examinado y no se realiza ninguna acción adicional. Si se encuentra, el nodo se bisela y se elimina. Con esto el árbol se queda separado en dos mitades, por lo que hay que seleccionar un nodo que haga las veces de raíz. Al ser un árbol binario de búsqueda y estar todos los valores de clave ordenados, podemos elegir como raíz el mayor valor del subárbol izquierdo o el menor valor de clave del derecho.

Operación de biselación

Esta operación traslada un nodo x, que es el nodo al que se accede, a la raíz. Para realizar esta operación debemos rotar el árbol de forma que en cada rotación el nodo x está más cerca de la raíz. Cada biselación realizada sobre el nodo de interés mantiene el árbol parcialmente equilibrado y además los nodos recientemente accedidos se encuentran en las inmediaciones de la raíz. De esta forma amortizamos el tiempo empleado para realizar la biselación. Podríamos distinguir 3 casos generales:

1. Caso 1: x es hijo izquierdo o derecho de la raíz, p.
2. Caso 2: x es hijo izquierdo de p y este a su vez hijo izquierdo de q o bien ambos son hijos derechos.
3. Caso 3: x es hijo izquierdo de p y este a su vez hijo derecho de q o viceversa.

CASO 1: Si x es hijo izquierdo de p entonces realizaremos una rotación simple derecha. En caso de que x sea el derecho la rotación que deberemos realizar es simple izquierda.

CASO 2: Si x es hijo y nieto izquierdo de p y q, respectivamente. Entonces debemos realizar rotación doble a la derecha, en caso de que x sea hijo y nieto derecho de p y q la rotación será doble izquierda.

CASO 3: En caso de que x sea hijo izquierdo de p y nieto derecho de q realizaremos una rotación simple derecha en el borde entre x y p y otra simple izquierda entre x y q. En caso contrario, x sea hijo derecho y nieto izquierdo de q, la rotaciones simples será izquierda y después derecha.

Biselación ascendente

Las operaciones OP se realizan en forma similar a un árbol binario de búsqueda. Luego se realiza una operación biselación sobre un nodo. En una búsqueda, se devuelve el nodo que contiene el valor buscado, o el padre de la hoja si no lo encuentra. En una inserción, el nodo sobre el que se aplica la operación biselación es el de igual valor al buscado, si ya existía; o el nuevo nodo si éste no estaba en el árbol. En biselación ascendente se requiere descender de la raíz hasta el nodo al que se le aplicará la operación biselación. Luego se van efectuado las rotaciones a medida que se asciende.

Es decir se recorre el árbol dos veces. A partir del nodo, al que se le aplicará la operación, se asciende hasta encontrar el abuelo, y se efectúa la rotación doble que corresponda; si no existe abuelo, pero sí padre, se efectúa rotación simple.

Biselación descendente

Consiste en partir el árbol en dos subárboles, uno con claves menores al buscado y otro con claves mayores al buscado, y a medida que se desciende se van efectuado las rotaciones. Cuando se encuentra el nodo en la raíz del subárbol central, se unen los subárboles, dejando como raíz al nodo. Cada vez que se desciende desde un nodo x, por un enlace izquierdo, entonces x y su subárbol derecho serán mayores que el nodo (que será insertado o que es buscado). De esta forma se puede formar un subárbol, con x y su subárbol derecho, sea este subárbol DER.

El caso simétrico, que se produce cuando se sigue un enlace derecho, permite identificar el subárbol izquierdo de la nueva raíz, sea este subárbol denominado IZQ. Como se recorre sólo una vez, ocupa la mitad del tiempo que el ascendente. Se mantienen punteros a IZQ y DER, y punteros a los puntos de inserción de nuevos nodos en IZQ y DER; éstos son el hijo derecho del máximo elemento de IZQ; y el hijo izquierdo del mínimo elemento de DER. Estas variables evitan la necesidad de recorrer IZQ y DER; los nodos y subárboles que se agreguen a IZQ o DER, no cambian sus posiciones en IZQ o DER. A partir de la raíz se desciende hasta encontrar un posible nieto, se efectúa la operación pasando el abuelo y el padre a los subárboles IZQ y DER; el nieto queda en la raíz del árbol central. Si se encuentra el nodo se efectúa una unión final.

Teoremas de rendimiento

Teorema del balance

El coste de realizar la secuencia de accesos S es del orden de O(m(logn + 1) + nlogn). En otras palabras, los árboles biselados se comportan tan bien como los árboles de búsqueda binaria con balanceo estático en secuencias de al menos n accesos.

Conjetura de optimalidad dinámica

Además del las garantías probadas del rendimiento de los árboles biselados, en el documento original de Sleator y Tarjan hay una conjetura no probada de gran interés. Esta conjetura se conoce como la conjetura de optimalidad dinámica, y básicamente sostiene que los árboles biselados se comportan tan bien como cualquier otro algoritmo de búsqueda en árboles binarios hasta un factor constante.

Sea A cualquier algoritmo de búsqueda binaria en árboles que accede a un elemento x atravesando el camino desde la raíz hasta x, a un coste de d(x) + 1, y que entre los accesos puede hacer cualquier rotación en el árbol a un coste de 1 por rotación. Sea A(S) el coste para que A realice la secuencia S de accesos. Entonces el coste de realizar los mismos accesos para un árbol biselado es del orden O(n + A (S)).

Existen varios corolarios de la conjetura de optimalidad dinámica que permanecen sin probar:

Conjetura Transversal: Sean T1 y T2 dos árboles biselados que contienen los mismos elementos. Sea S la secuencia obtenida tras visitar los elementos de T2 en preorden. El coste total para realizar la secuencia S de accesos en T1 es del orden de O(n). Conjetura Deque: Sea S una secuencia de m operaciones de cola doblemente terminada (push, pop, inject, eject). Entonces el coste para la realización de esta secuencia de operaciones S en un árbol biselado es del orden de O(m + n).

Conjetura Split: Sea S cualquier permutación de los elementos del árbol biselado. Entonces el coste de la eliminación de los elementos en el orden S es del orden de O(n).

Referencias

Fuentes

• Árbol biselado. Disponible en: Portal Sisbib (PDF)
• Estructura de datos. Disponible en: Portal Tutoriales de ingeniería