Arvoles AVL

Estado
No está abierto para más respuestas.

AFQR-BARBAX

Lanero Reconocido
Se unió
26 Dic 2001
Mensajes
448
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?
 

Sh4dow

Lanero Reconocido
Se unió
4 Jun 2002
Mensajes
587
jejej tipicos de la materia Estructuras de datos y teoria de archivos :D
 

Sh4dow

Lanero Reconocido
Se unió
4 Jun 2002
Mensajes
587
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 =)
 

ODDG

LANero Fundador
Lanero VIP
Se unió
13 Abr 2001
Mensajes
1,684
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.
 

AFQR-BARBAX

Lanero Reconocido
Se unió
26 Dic 2001
Mensajes
448
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
 

Sh4dow

Lanero Reconocido
Se unió
4 Jun 2002
Mensajes
587
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
 

Adjuntos

Sh4dow

Lanero Reconocido
Se unió
4 Jun 2002
Mensajes
587
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.
 

Adjuntos

Sh4dow

Lanero Reconocido
Se unió
4 Jun 2002
Mensajes
587
eso es gráficamente la definición de un árbol AVL, espero te pueda servir de alto =)
 

AFQR-BARBAX

Lanero Reconocido
Se unió
26 Dic 2001
Mensajes
448
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
 

=LT=totobany

Lanero Reconocido
Se unió
12 Feb 2002
Mensajes
1,245
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:
 
G

gK-||sico||

Guest
uyyyyy totobany, monta el archivo aca que a mi me gustaria verlo y analizarlo...
 

gK-Dante

Lanero Reconocido
Se unió
28 Ene 2002
Mensajes
2,646
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
No está abierto para más respuestas.
Arriba