Árbol biselado

Las rotaciones internas en árboles binarios son operaciones internas comunes muy utilizadas en árboles autobalanceables.

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 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 aparte 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 árbol 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. Un operación de búsqueda cuidadosamente diseñada puede devolver el nodo más a la izquierda o más a la derecha de una clave dada.

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.

Extracció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:

Caso 1: x es hijo izquierdo o derecho de la raíz, p.
Caso 2: x es hijo izquierdo de p y este a su vez hijo izquierdo de q o bien ambos son hijos derechos.
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.

Teoremas de rendimiento

Hay muchos teoremas y conjeturas con respecto al peor caso en tiempo de ejecución para realizar una secuencia S de m accesos en un árbol biselado con n elementos.

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.

Teorema de optimalidad estática

Sea $q_{i}$ el número de veces que se accede al elemento i en S. El coste de realizar la secuencia de accesos S es del orden de $O\left(m+\sum _{i=1}^{n}q_{i}\log {\frac {m}{q_{i}}}\right)$ . En otras palabras, los árboles biselados se comportan tan bien como los árboles binarios de búsqueda estáticos óptimos en las secuencias de al menos n accesos.

Teorema "Static Finger"

Sea $i_{j}$ el elemento visitado en el j-ésimo acceso de S, y sea f un elemento fijo ("finger"). El coste de realizar la secuencia de accesos S es del orden de $O{\Bigl (}m+n\log n+\sum _{j=1}^{m}\log(|i_{j}-f|+1){\Bigr )}.$

Teorema "Working Set"

Sea $t(j)$ el número de elementos distintos accedidos desde la última vez que se accedió a j antes del instante i. El coste de realizar la secuencia de accesos S es del orden de $O{\Bigl (}m+n\log n+\sum _{j=1}^{m}\log(t(j)+1){\Bigr )}$ .

Teorema "Dynamic Finger"

El coste de realizar la secuencia de accesos S es del orden de $O{\Bigl (}m+n+\sum _{j=1}^{m}\log(|i_{j+1}-i_{j}|+1){\Bigr )}$ .

Teorema "Scanning"

También conocido como Teorema de Acceso Secuencial. El acceso a los n elementos de un árbol biselado en orden simétrico es de orden exacto $\Theta (n)$ , independientemente de la estructura inicial del árbol. El límite superior más ajustado demostrado hasta ahora es $4,5n$

Conjetura de optimalidad dinámica

Además de 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.

Conjetura de optimalidad dinámica: 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

T_{1}

y

T_{2}

dos árboles biselados que contienen los mismos elementos. Sea S la secuencia obtenida tras visitar los elementos de

T_{2}

en preorden. El coste total para realizar la secuencia S de accesos en

T_{1}

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).

Véase también

Enlaces externos

Algoritmo

"Self-adjusting Binary Search Trees", Sleator and Tarjan (la publicación original en INGLÉS)

Implementaciones

Datos: Q80729