arboles avl
TRANSCRIPT
UNIVERSIDAD DE EL SALVADOR
FACULTAD DE INGENIERIA Y ARQUITECTURA
ESCUELA DE INGENIERIA EN SISTEMAS INFORMATICOS
PROGRAMACION II
“ESTRUCTURA TIPO ÁRBOLES BALANCEADOS”
INSTRUCTOR: Ing. Rodrigo Vásquez.
GRUPO TEORICO: 03
INTEGRANTES: CARNET FIRMA
Ayala Núñez Mario Ernesto AN06006 ____________
Calles Viera Rosario del Carmen CV06032 ____________
Duran Mena Isabel Astrid DM06025 ____________
San Salvador, Lunes 20 de Mayo de 2011.
INDICE
I- INTRODUCCION ................................................................................................... i
II- OBJETIVOS. ........................................................................................................ ii
III- MARCO CONCEPTUAL. .................................................................................... 5
I V - APLICACION DE LA ESTRUCTURA DE DATOS “ÁRBOL BINARIO DE
BÚSQUEDA” A UN CASO REAL. ................................................................... 10
IV. i- ENUNCIADO DEL PROBLEMA. ................................................................. 10
I V . ii- DESARROLLO LOGICO DE LA APLICACIÓN . ........................................... 11
V. CONLUSIONES. ............................................................................................... 12
VI- BIBLIOGRAFIA 13
I- INTRODUCCION
El presente trabajo es dedicado al uso de Estructuras Arboles Balanceados (AVL)
con el cual se pretende demostrar de forma práctica el manejo de este tipo de
herramienta a situaciones cotidianas.
Dentro del desarrollo del trabajo marco teórico se explica a manera conceptual el
manejo de este tipo de estructuras; la forma sobre la cual se realizan las
funciones de inserción, reestructuración, eliminación de nodos en los arboles
AVL, la lógica de solución de los problemas.
En este capítulo se muestra de forma general el manejo de las funciones sin
importar el tipo de lenguaje sobre el cual se desarrollaran los programas con este
tipo de estructuras.
Dentro del planteamiento del problema se pretende mostrar un ejemplo completo
de las aplicaciones de dicha estructura; así como explicar de manera
generalizada el funcionamiento interno de los procesos externos en el programa a
desarrollar.
i
II- OBJETIVOS.
OBJETIVO GENERAL:
Analizar y desarrollar la aplicación de los Arboles Balanceados. El cual
permita mostrar la implementación de la estructura en una situación real;
demostrando la forma en que la estructura funciona.
OBJETIVOS ESPECIFOS:
Desarrollar conocimientos adquiridos, en el manejo de estructuras de datos
en situaciones reales.
Implementar estructuras del tipo Arboles Balanceados.
Adquirir conocimientos en el desarrollo de aplicaciones de software.
Descubrir el funcionamiento de las estructuras de tipo Arboles Balanceados
ii
MARCO TEORICO
ARBOLES BALANCEADOS (AVL)
Un árbol balanceado es un árbol binario en el cual las alturas de los dos subárboles para cada nodo nunca difieren en más de una unidad. También se le llama arboles AVL en honor a sus inventores, dos matemáticos Rusos, G.m. Adelson – Velskii y E.M. Landis.
Estos árboles binarios balanceados, que nos permiten después de cada inserción rotar los nodos de forma de que quede ordenado.Básicamente un árbol AVL es un Árbol binario de búsqueda al que se le añade una condición de equilibrio.
Características:
Un AVL es un ABB.
La diferencia entre las alturas de los subárboles derecho e izquierdo no debe excederse en más de 1.
Cada nodo tiene asignado un peso de acuerdo a las alturas de sus subár-boles.
Un nodo tiene un peso de 1 si su subárbol derecho es más alto, -1 si su su-bárbol izquierdo es más alto y 0 si las alturas son las mismas.
La inserción y eliminación en AVL es la misma que en los ABB.
Los AVL utilizan el factor de balanceo para decidir si es necesario rotar una rama luego de insertar.
5
Este Factor de Balanceo o Equilibrio (FB) o (FE), nos dice la diferencia de alturas entre el subárbol derecho menos el subárbol izquierdo, por lo que restando las al-turas de los mismos obtenemos este valor.
FB = Altura subárbol derecho - Altura subárbol izquierdo
El factor de balanceo de cada nodo en un árbol balanceado será -1, 1 o 0. Si FB llegara a tomar los valores de -2 o 2. Si alguno de los pesos de los nodos se modifica en un valor no válido (2 o -2) debe seguirse un esquema de rotación.
Figura 1 Figura 2
Analizando la figura, 1 tenemos que la primer rama izquierda tiene un desbalanceo, ya que la altura de su subrama izquierda es -2, y la de la derecha es 0, lo que nos da: FB = -2. Tenemos desbalance.
Analizando la figura 2, el FB no supera el valor -1, por lo que no hay necesidad de rotar. Operaciones sobre los AVL:
INSERTAR
Usamos la misma técnica para insertar un nodo en un ABB ordenado.
Trazamos una ruta desde el nodo raíz hasta un nodo hoja (donde hacemos la inserción).
Insertamos el nodo nuevo.
Volvemos a trazar la ruta de regreso al nodo raíz, ajustando el equilibrio a lo largo de ella.
Si el equilibrio de un nodo llega a ser + - 2, volvemos a ajustar los subárboles de los nodos para que su equilibrio se mantenga acorde con los lineamientos AVL (que son +- 1).
6
-2
BALANCEAR
En esta operación se distinguen los casos de Rotación Simple o Compuesta:
Caso 1: Rotación simple izquierda RII.
Si esta desequilibrado a la izquierda y su hijo derecho tiene el mismo signo (+) hacemos rotación sencilla izquierda.
Caso 2: Rotación simple derecha RDD.
Si esta desequilibrado a la derecha y su hijo izquierdo tiene el mismo signo (-) hacemos rotación sencilla derecha.
Caso 3: Rotación Compuesta izquierda - derecha RID.
Si está desequilibrado a la izquierda (FE < –1), y su hijo derecho tiene distinto signo (+) hacemos rotación izquierda-derecha.
7
Caso 4: Rotación Compuesta derecha - izquierda RDI.
Si esta desequilibrado a la derecha y su hijo izquierdo tiene distinto signo (–) hacemos rotación derecha-izquierda.
ELIMINAR
Al eliminar un nodo en un árbol AVL puede afectar el equilibrio de sus nodos. Entonces hay que hacer rotaciones simples o compuestos.Eliminas un nodo como lo hacemos en un árbol binario ordenado. Al localizar el nodo que queremos eliminar seguimos este procedimiento:
Si el nodo es un nodo hoja, simplemente lo eliminamos.
Si el nodo solo tiene un hijo, lo sustituimos con su hijo.
Si el nodo eliminado tiene dos hijos, lo sustituimos por el hijo derecho y colocamos el hijo izquierdo en el subárbol izquierdo del hijo derecho.
Si el equilibrio del padre del nodo eliminado cambia de 0 a +-1 el algoritmo concluye.
Si en algunos de los nodos se viola el criterio de equilibrio, entonces se debe reestructurarse el árbol.Ejemplos:
8
Figura 1
Figura 2
9
IV- APLICACION DE LA ESTRUCTURA DE DATOS “ÁRBOLES
BALANCEADOS A UN CASO REAL”.
IV. i- ENUNCIADO DEL PROBLEMA.
Se tiene la situación de una bodega en una empresa “X” en la cual se registran los
productos que entran y salen de la bodega.
Estos datos de la empresa los manejan y se encargan de los mismos una unidad
específica, para llevar un mejor control.
Se implementara un programa de búsqueda para facilitar el manejo de toda la
información en relación al producto, dicha búsqueda se hará por medio de un
código numérico para facilitar la inserción, eliminación y búsqueda de dichos
productos y modificar los datos necesarios para una operación u otra.
10
IV. ii- DESARROLLO LOGICO DE LA APLICACIÓN.
Para la solución del problema planteado se hará uso de la estructuras de datos
“Arboles Balanceados” ya que por lo mencionado anteriormente se debe aplicar
una búsqueda rápida y por tanto es aplicable este tipo de estructura tomando en
cuenta el factor de equilibrio o balance del árbol reestructurando cuando sea
necesario.
El diseño de esta estructura se hará en base a memoria dinámica, ya que dada las
circunstancias no se debe de limitar el tamaño de dicha estructura;
En la aplicación se dispondrán de las funciones como búsqueda, inserción,
eliminación, visualización por medio de un menú con las opciones anteriores y el
tipo de recorrido que se usara es en orden.
Se deberá validar los datos que se ingresen ya que serán solo numéricos por lo
que la variable será tipo “int”.
11
DECLARACION Y FUNCIONES LOGICAS DE LA ESTRUCTURA AVL IMPLEMENTADA EN C++
V. CONLUSION.
La estructura de datos de Arboles Balanceados (AVL) es rápida y eficiente ya que
nos permite después de cada inserción rotar los nodos de forma de que quede
ordenado, la cual se le añade una condición de equilibrio; es representado por
nodos, uno de los cuales es la Raíz donde esta se despliega dos subárboles el
izquierdo y el derecho, dentro del árbol se puede insertar, eliminar y se puede
realizar una búsqueda por medio de un recorrido.
Esta estructura es usada en situaciones donde se requiere encontrar un elemento con una buena rapidez para hacer uso de dicho elemento.
12
VI- BIBLIOGRAFIA.
Estructura de datos con C y C++.
SEGUNDA EDICION
YEDIDYAH LAGSAM
MOSHE J. AUGENSTEIN.
AARON M. TENEMBAUM.
COMO PROGRAMAR EN C/C++
SEGUNDA EDICION
H. M. DIITEL/ P. J. DEITEL
http://es.wikipedia.org/wiki/%C3%81rbol_binario_de_b%C3%BAsqueda
PROGRAMACION EN C – METODOLOGIA , ALGORITMOS Y
ESTRUCTURA DE DATOS
LUIS JOYANES AGUILAR – IGNACIO ZAHONERO MARTINEZ
1ª EDICION
EDITORIAL McGRAW HILL
13