Arvoles AVL

Estado
Cerrado para nuevas respuestas.

AFQR-BARBAX

Lanero Reconocido
26 Dic 2001
447
Oe señores.

Quien me puede explicar hacerca de los árboles AVL ó árboles Balanceados? Lo que quieran decirme.

Señor MigPosada, ODDG lo de la U Help?
 
jejej tipicos de la materia Estructuras de datos y teoria de archivos :D
 
ok veo que digiste explicar, aqui va lo poco que se de ellos

Un árbol AVL es basicamente un arbol binario de búsqueda, al que se le añade una condición de equilibrio. Esta condición es que para todo nodo la altura de de sus subárboles izquierdo y derecho pueden diferir a lo sumo en 1. Esto es lo básico que debes saber sobre ellos, lo que pediste =)

si necesitas algoritmos de inserción, borrado y recorrer el arból, lo que siempre le digo a la gente www.google.com =)
 
mmmmm a ver......
*AVL son las iniciales del autor de este arbol.
*Los arboles AVL son arboles hechos para estar equlibrados y facil de identificar cuando no
*Cada nodo tiene un campo información para registrar ahí si:
-1=No equilibrado a la izquierda
0= Equilibrado
+1=No Equilibrado a la derecha
*El valor del campo información se llena así:
Si hay hijo izquierdo + Si hay hijo derecho = información padre

Ejemplo:
un padre con dos hijos
-1 + 1 = 0 Equilibrado

Es interesante a partir de mas nodos así:

Los siguientes hermanos son padres
un padre tiene 2 hijos (equi) = 0
un padre solo tiene 1 hijo a la izquierda (desequi) = -1

El abuelo de estos hijos tiene el siguiente valor
El hijo de la izquierda es el quiene 2 hijos o sea que:
-1 + .....
El hijo de la derecha es el que tiene 1 hijo o sea que:
-1 + -1 = -2 valor del abuelo
Así entonces por AVL concluimos que el arbol se encuentra desequilibrado a su derecha.
 
Muchas gracias por sus acotes, pero cómo hago para rotar un árbol? y cómo diferencio yo cuando un árbol está balanceado o no a simple vista, pues no le entiendo al libro del profe
 
Originalmente colocado por barbax
Muchas gracias por sus acotes, pero cómo hago para rotar un árbol? y cómo diferencio yo cuando un árbol está balanceado o no a simple vista, pues no le entiendo al libro del profe

creo que con graficos notarás más facil la diferencia

Este es un árbol AVL balanceado
 

Archivos adjuntos

  • arboliz.png
    arboliz.png
    26.6 KB · Visitas: 368
y este es un arbol AVL desbalanceado
nota que como te dije arriba en la definición, para todo nodo la altura de sus subárboles izquierdo y derecho pueden diferir a lo sumo en 1.

Este está desbalanceado porque el nodo 6 tiene altura 3 en el subárbol izquierdo y algura 1 en el derecho.
 

Archivos adjuntos

  • exavlder.png
    exavlder.png
    26.7 KB · Visitas: 375
eso es gráficamente la definición de un árbol AVL, espero te pueda servir de alto =)
 
A que Rules señores muchas gracias por su ayuda, ahora si a darle duro a esta cosa.

Suerte y gracias Mr. Sh4dow Y Srita ODDG son unos bacanes. jeje
 
barbax.

Si te interesa una de las practicas de structuras de datos en la U, fue hacer una herrammienta grafica que me muestre el funcionamiento de estos arboles si queres te la puedo enviar pa que la pilles.


:reir:
 
uyyyyy totobany, monta el archivo aca que a mi me gustaria verlo y analizarlo...
 
Pa rotar un nodo existen:

giro a la derecha
giro a la izquierda
doble giro a la derecha
doble giro a la izquierda

y se aplican según el caso de desbalanceo q exista en este.
las reglas y el mecanismo te lo puede explicar toto.
 
Estado
Cerrado para nuevas respuestas.

Los últimos temas