Análisis de Algoritmos
Zacatecas , Zac. México., 21 de Mayo de 2013
ÁRBOL AVL
UNIVERSIDAD AUTÓNOMA DE ZACATECAS
UNIDAD ACADÉMICA DE INGENIERÍA ELÉCTRICA
PROGRAMA INGENIERÍA EN COMPUTACIÓN
Email: CONTACTO@SMARTALOGISTICS.COM
Website: WWW.SMARTALOGISTICS.COM
Location: Campus UAZ Siglo XXI, Mexico
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.
Construyendo Árbol
Al dar click en éste botón tendremos la posibilidad de ingresar el tamaño del árbol (¿De cuánto nodos será), además del valor numérico para cada nodo. Método: public synchronized void insertar(int d)
Mostrando Árbol
Al seleccionar ésta opción nos aparecerá en el panel la representación de un árbol AVL, poniendo así los elementos numéricos acomodados, e indicado en qué posición van, ya sean en la posición derecha o izquierda. También se señala cuál será la raíz. Métodos: void pintar(int d,String h) void mostrarArbol(NodoArbol R,String hijo)
Buscando Árbol
Al dar click en éste botón tendremos la posibilidad de buscar mediante valor numérico algún dato del árbol que se había creado con anterioridad, mostrándonos así la existencia o inexistencia de dichos datos. Métodos: public synchronized String buscador(NodoArbol R,int d)
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.
Referencias
- http://trevinca.ei.uvigo.es/~pavon/transparencias/TTema4Grafos.pdf
- http://xue.unalmed.edu.co/~dosorio/linux/hash.htm
- http://www.cee.hw.ac.uk/DSA/ProgramIndex.htm
- http://www.cs.utsa.edu/~carola/teaching/cs5633/spring04/slides/Lecture18.pdf
- http://www.dcc.uchile.cl/~rbaeza/handbook/hbook.html
- http://www.dma.fi.upm.es/fleury/definicionesGrafos.htm
- http://www.dma.fi.upm.es/gregorio/grafos/paginagrafos.html