Análisis de Algoritmos

Zacatecas , Zac. México., 21 de Mayo de 2013

ÁRBOL AVL

Presentado por: Pedro Morales, Tomás Zamudio, Álvaro Carrillo, Karla Mandujano

UNIVERSIDAD AUTÓNOMA DE ZACATECAS

UNIDAD ACADÉMICA DE INGENIERÍA ELÉCTRICA

PROGRAMA INGENIERÍA EN COMPUTACIÓN





Introducción

  • El árbol AVL, es un árbol binario ordenado (BST) pero además balanceado en altura.Se debe cumplir la siguiente condición: Para todo nodo A del árbol, la altura de los subárboles izquierdo y derecho no debe diferir en más de una unidad.
  • Reciben su nombre en honor a sus creadores, los matemáticos rusos: Adelson Velski y E.M. Landis.
  • Las operaciones que realiza son las de insertar( siendo inserción izquierda para los números más pequeños y derecha para números mayores),además de aquí subyacerá la inserción externa e interna (Según sea el caso), de borrar y de buscar; por cada operación que realiza va acomodando sus nodos mediante rotaciones, pudiendo ser rotación interna o rotación externa.






Resumen

Nuestro programa consta de 5 botones principales, cada uno de ellos tiene una función específica; los botones de nuestro programa “AVL” son los siguientes (Todos subyacentes del menú “Archivo”)

1* “Nuevo Proyecto”

2*”Construir Árbol”

3*”Mostrar Árbol”

4*”Buscar en el Árbol”

5* “Salir”

Objetivos

El objetivo de esta implementación es demostrar el funcionamiento del Árbol AVL visualmente mediante la codificación de sus Algoritmo (EN JAVA).


Metodología

El primer número del arreglo se coloca en la raíz del árbol (como en este ejemplo siempre vamos a trabajar con árboles binarios, simplemente diremos árbol, para referirnos a un árbol binario) con sus subárboles izquierdo y derecho vacíos. Luego, cada elemento del arreglo se compara son la información del nodo raíz y se crean los nuevos hijos con el siguiente criterio:

  • Si el elemento del arreglo es menor que la información del nodo raíz, entonces se crea un hijo izquierdo.
  • Si el elemento del arreglo es mayor que la información del nodo raíz, entonces se crea un hijo derecho.




Conclusiones

Podemos dilucidar que un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia.

Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene elementos, se deben hacer comparaciones.

Si usamos un árbol binario, el número de comparaciones se reduce bastante.