Estructuras Lineales
Arboles Binarios
Arboles Enearios
Teoria de Grafos
Descargar Material
Los arboles biselados (inglés: splay tree) son árboles binarios de búsqueda que ofrecen en tiempo O(log n) en las operaciones de búsqueda, inserción y eliminación de un nodo.
En un árbol biselado cada vertice contiene a una clave y las claves en el ramo izquierdo son menores que la clave del vértice mismo, mientras a la derecha están las claves mayores.
Las claves son unicas.
La idea básica es que después de acceder a un nodo éste se lleva a la raíz mediante rotaciones.
En cada operación splay se hace ascender al nodo en uno o dos niveles, dependiendo de su orientación relativa respecto de su nodo abuelo.
Un splay mueve el elemento recuperado a la raíz del árbol.
Así, un splay hace que:
- Todos los nodos accedidos durante una consulta luego sean mucho menos costosos de acceder.
- Todos los demás nodos no accedidos, su consulta se empeora sólo un poco.
Ejemplo de Splay (1,S):
Ejemplo de Splay (2,S):
Para hacer splay en un nodo x, repetimos los siguientes pasos hasta que x sea la raíz del árbol:
Caso Zig: si x es un hijo izquierdo de la raíz del árbol, rotar x a derecha y terminar.
Caso Zag: si x es un hijo derecho de la raíz del árbol, rotar x a izquierda y terminar.
Caso Zig-Zig: si x es un hijo izquierdo y su padre es un hijo izquierdo, rotar el padre de x y luego en x ambos a derecha.
Caso Zig-Zag: si x es un hijo izquierdo y su padre es un hijo derecho, rotar en x a derecha y luego en x de nuevo, pero a izquierda.
Caso Zag-Zig: si x es un hijo derecho y su padre es un hijo izquierdo, rotar en x a izquierda y luego en x de nuevo pero a derecha.
Acceder al nodo a; es decir splay(a, root).
Para la búsqueda de un nodo x realiza un splay sobre el árbol:
- Si la localización es exitosa, la salida será un árbol binario de búsqueda con x como raíz.
- Si la localización fracasa, la salida será un árbol binario de búsqueda que tendrá como raíz al nodo en el que la búsqueda fracasó.
Ejemplo: Buscar 7
Ejemplo de una búsqueda sin éxito.
Buscar 2 -> como el 2 no se encuentra en el árbol entonces se guarda el ultimo nodo en el cual la búsqueda fracaso, en este caso es 3, y luego se hace splay a ese nodo quedando como raíz.
Para insertar un nodo x en un árbol splay; primero se inserta como si fuera un árbol binario de búsqueda y luego se hace splay en el nodo insertado.
Ejemplo: Insertar 5
- Buscar x.
- Si la raíz no es x, no hay nada que hacer.
- Eliminar el nodo que contiene a x. Quedan dos subárboles I y D.
- Buscar el máximo de I.
- Colocarle D como hijo derecho del máximo.
Ejemplo: Eliminar 6
Eliminar 4: como 4 no se encuentra en el árbol entonces se aplica splay al nodo 3 ya que fue el último nodo donde fracaso la búsqueda y luego no se hace nada.
El Árbol Splay o Árbol Biselado es una más de las representaciones del Árbol Binario de Búsqueda, cuya principal propiedad de biselar los elementos del árbol al realizar las diferentes operaciones. Biselar consiste en ubicar el ultimo dato con el que se interactura en la raíz. Las operaciones que determinan esta propiedad son la inserción en el que de no existir el dato se ubica el nodo con el dato más cercano, donde cada acceso a un dato con lleva a la realización de una operación llamada “biselación”.
La implementación de este tipo de Arboles se realiza utilizando como base el Árbol Binario de Búsqueda, debido a que sus funciones y operaciones son las mismas de dicho Árbol combinadas con una operación básica, llamada “biselación”.
A continuación se presenta el diagrama de clases para el Árbol Splay implementado, con cada una de sus operaciones:
Requerimientos funcionales implementados para Arboles Splay:
RF1 - Crear un nuevo Árbol Splay.
RF2 - Conocer y editar la raíz del Árbol Splay.
RF3 - Insertar nuevos datos en un Árbol Splay, realizando la biselación del dato.
RF4 - Eliminar datos de un Árbol Splay, realizando la biselación del dato.
RF5 - Consultar la existencia de objetos dentro del Árbol Splay. Realizando biselación del dato consultado.
RF6 - Consultar el listado de hojas de un Árbol Splay.
RF7 - Conocer el número de hojas del Árbol Splay.
RF8 - Recorrer un Árbol Splay en Preorden.
RF9 - Recorrer un Árbol Splay en Inorden.
RF10 - Recorrer un Árbol Splay en PostOrden.
RF11 - Recorrer un Árbol Splay por niveles.
RF12 - Conocer el peso de un Árbol Splay.
RF13 - Consultar la altura de un Árbol Splay.
RF14 - Conocer por consola los datos presentes en el Árbol Splay.
Implementación de un Simulador para Arbol Splay:
El Simulador para ArbolSplay posee las operaciones indicadas por su menú de opciones dentro del mismo:
Recurso Documental para Proyecto de Grado SEED "Simuladores para Estudio de Estructuras de Datos"
Desarrolladores del Proyecto: Wilfred Uriel García - Cindy Yulieth Pabón Sánchez
2014