Árbol biselado

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.

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.

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.

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 ${\displaystyle T_{1}}$ y ${\displaystyle T_{2}}$ dos árboles biselados que contienen los mismos elementos. Sea S la secuencia obtenida tras visitar los elementos de ${\displaystyle T_{2}}$ en preorden. El coste total para realizar la secuencia S de accesos en ${\displaystyle 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 ${\displaystyle 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).

• Árbol (estructura de datos)
• Árbol binario
• Árbol binario de búsqueda
• Árbol AVL
• Árbol rojo-negro
• Árbol multirrama