Arbol biselado

2012-01-27T16:36:14Z

Eliza93: Página creada con ''''Árbol Biselado''' Un Árbol biselado o Árbol Splay<ref>http://sisbib.unmsm.edu.pe/BibVirtual/publicaciones/risi/2009_n1/v6n1/a06v6n1.pdf</ref> es un Árbol binario de bús...'

'''Árbol Biselado'''

Un Árbol biselado o Árbol Splay<ref>http://sisbib.unmsm.edu.pe/BibVirtual/publicaciones/risi/2009_n1/v6n1/a06v6n1.pdf</ref> 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|á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|á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|árbol]] biselado<ref>http://elisa.dyndns-web.com/~elisa/teaching/aa/pdf/clase0210.pdf</ref> 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 [[Árbol|á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| algoritmo]] básico del [[Árbol|árbol]] biselado es el acceso secuencial a todos los elementos del [[Árbol|á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|á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 <ref>http://elisa.dyndns-web.com/~elisa/teaching/aa/pdf/clase0210.pdf</ref>un valor de [[Clave|clave]] en un árbol biselado tiene la característica particular de que modifica la estructura del [[Árbol|á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|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|nodo]] insertado. Además, si el valor de [[Clave|clave]] a insertar ya existe en el árbol, se bisela el [[Nodo|nodo]] que lo contiene.

===Eliminación===

Esta operación requiere dos biselaciones. Primero se busca el [[Nodo|nodo]] que contiene el valor de clave que se debe extraer. Si no se encuentra, el [[Árbol|árbol]] es biselado en el último [[Nodo|nodo]] examinado y no se realiza ninguna acción adicional. Si se encuentra, el [[Nodo|nodo]] se bisela y se elimina. Con esto el árbol se queda separado en dos mitades, por lo que hay que seleccionar un [[Nodo|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|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|nodo]] de interés mantiene el [[Árbol|árbol]] parcialmente equilibrado y además los [[Nodo|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.

===Biselación ascendente===
Las operaciones OP se<ref>http://sisbib.unmsm.edu.pe/BibVirtual/publicaciones/risi/2009_n1/v6n1/a06v6n1.pdf</ref> realizan en forma similar a un árbol binario de búsqueda. Luego se realiza una operación
biselación sobre un [[Nodo|nodo]]. En una búsqueda, se devuelve el [[Nodo|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|árbol]]. En biselación ascendente
se requiere descender de la raíz hasta el [[Nodo|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|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|árbol]] en dos subárboles, uno con claves menores al buscado y otro con [[Clave|claves]] mayores al buscado, y a medida que se desciende se van efectuado
las rotaciones. Cuando se encuentra el [[Nodo|nodo]] en la raíz del subárbol central, se unen los subárboles, dejando como raíz al [[Nodo|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|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|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 [[Árbol|á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|algoritmo]] de búsqueda en árboles binarios hasta un factor constante.
Sea A cualquier [[Algoritmo|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|á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|á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 [[Árbol|á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|árbol]] biselado es del orden de O(m + n).

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

==Enlaces externos==
*[http://sisbib.unmsm.edu.pe/BibVirtual/publicaciones/risi/2009_n1/v6n1/a06v6n1.pdf PDF]
*[http://sites.google.com/site/tutoriasdeingenieria/estructura-de-datos/21-clase Clase]

==Referencias bibliográficas==
{{Listaref}}

[[Category:Telemática]]

EcuRed - Contribuciones del colaborador [es]

Arbol biselado