Arbol biselado - Historial de revisiones

Carlos idict: Texto reemplazado: «
» por «»

2019-07-17T11:04:39Z

Texto reemplazado: «<div align="justify">» por «»

Carlos idict en 12:30 15 jul 2013

2013-07-15T12:30:19Z

Ronny0611ad jc.hlg en 15:05 26 abr 2013

2013-04-26T15:05:00Z

Yoadis jc.palacios en 14:11 26 mar 2012

2012-03-26T14:11:56Z

Mostrar los cambios

Michel0302 jc en 16:11 24 mar 2012

2012-03-24T16:11:51Z

Humberto0601ad jc en 16:43 30 ene 2012

2012-01-30T16:43:12Z

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

2012-01-27T16:36:14Z

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

Página nueva

'''Á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]]

@@ Línea 1: / Línea 1: @@
-<div align="justify">
 {{Definición
 |nombre= Árbol biselado.

@@ Línea 12: / Línea 12: @@
 ==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.
+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 [[nodo]]s 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.
@@ Línea 35: / Línea 35: @@
 ==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.
+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]]s 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.

@@ Línea 1: / Línea 1: @@
 <div align="justify">
 {{Definición
-|nombre=Árbol biselado
+|nombre= Árbol biselado.
-|imagen=
+|imagen= Arbolbisalado.JPG
 |tamaño=
-|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.
+|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'''<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]].

← Revisión anterior		Revisión del 16:43 30 ene 2012
Línea 1:		Línea 1:
−	'''Árbol ~~Biselado~~'''	+	{{Normalizar\|motivo=Colocar la plantilla}}
		+
		+	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.

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

@@ Línea 1: / Línea 1: @@
 {{Normalizar|motivo=Colocar la plantilla}}
-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.
+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.
+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.
+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.
+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.
+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==
@@ Línea 19: / Línea 20: @@
 ===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.
+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===
@@ Línea 27: / Línea 28: @@
 ==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.
+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 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.
@@ Línea 46: / Línea 47: @@
 ===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
+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.
+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.
+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.
+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==
@@ Línea 62: / Línea 63: @@
 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)).
+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: