Arboles AVL
manel
No se si este es el sitio adecuado para exponer mi duda, ahí va:
En una estructura de datos en arbol de búsqueda equlibrado (AVL), ¿porqué
siempre se toma 1 como límite de desequilibrio?, ¿qué diferencia en cuanto a
coste en los algoritmos habria si el límite fuera 2?, es decir, ¿qué
ventajas o desventajas tendrian ambos métodos?.
A ver si tengo suerte y alguien me lo puede explicar..
Gracias.
manel.
znôrt
"manel" <ma...@NOSPAMesbatgimnas.com> escribió en el mensaje
news:asch7c$3v3$1...@nsnmrro2-gest.nuria.telefonica-data.net...
> Hola,
> No se si este es el sitio adecuado para exponer mi duda, ahí va:
> En una estructura de datos en arbol de búsqueda equlibrado (AVL), ¿porqué
> siempre se toma 1 como límite de desequilibrio?, ¿qué diferencia en cuanto
a
> coste en los algoritmos habria si el límite fuera 2?, es decir, ¿qué
> ventajas o desventajas tendrian ambos métodos?.
Porque es el mínimo, no hay forma de equilibarar a 0 todos los árboles
posibles. Funcinaría igual con "limites" mas grandes, pero sería una pérdida
de eficacia en las búsquedas. Precisamente la ventaja de un árbol AVL es
que tiene es que todos los caminos máximos tienen la misma profundidad
(+-1), osea, garantizan que encontrarás cualquier nodo con un máximo de n
saltos, siendo n el mínimo número de niveles necesarios para sostener el
árbol ( 2^nodos -1).
Si amplías el "limite" a 50, habría una rama 50 nodos más profunda que otra,
y el invento pierde su gracia.
saludos
znôrt
manel
Pero si el límite es 2, habrà que reequilibrar menos veces el arbol sin que
la diferencia de profundidad de las ramas sea demasiada NO?, entonces que
desventaja tiene que el límite sea 2 en vez de 1?.
Con límites grandes entiendo la desventaja, però con un límite 2 no se la
veo.
A ver si alguien me lo puede explicar.
Gracias.
manel.
"znôrt" <x...@x.com> escribió en el mensaje
news:asdoj1$qa6mj$1...@ID-134350.news.dfncis.de...
Jose Antonio
el otro, es decir, si lo pones a 2 es posible que se produzcan menos
equilibrios (no muchos menos) pero las búsquedas también son
más lentas (no mucho más lentas).
Pero la ventaja del AVL, es que la complejidad del algoritmo
de reequilibrado no es muy grande (logn creo recordar), sin
embargo ten en cuenta que este tan sólo se puede ejecutar
en determinados casos cuando se inserta o borra un nodo.
Lo más normal en una estructura de este tipo es que los nodos
se borren o se inserten con menor frecuencia que búsquedas
se han sobre ésta. Como se harán más búsquedas es lógico
que se ponga el limite al mínimo que es 1.
¿Te he convencido ;-)?
Saludos.
Jose.