Arboles Avl

Arboles AVL

| |Arboles Equilibrados |
| |El comportamiento de los ABB no es siempre tan bueno como nos gustaría. Pues bien, para minimizar el problema de los ABB desequilibrados, sea cual sea el grado de |
| |desequilibrio que tengan,se puede recurrir a algoritmos de equilibrado de árboles globales. En cuanto a estos algoritmos, existen varios, por ejemplo, crear una lista |
| |mediante la lectura en inorden del árbol, y volver a reconstruirlo equilibrado. Conociendo el número de elementos no es demasiado complicado. |
| |El problema de estos algoritmos es que requieren explorar y reconstruirtodo el árbol cada vez que se inserta o se elimina un elemento, de modo que lo que ganamos al |
| |acortar las búsquedas, teniendo que hacer menos comparaciones, lo perdemos equilibrando el árbol. |
| |Para resolver este inconveniente podemos recurrir a los árboles AVL.|
| |  |
| |Definición|
| |Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus |
| |subárboles izquierdo y derecho no difieren en más de 1. |
| |No se trata de árbolesperfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos |
| |donde los ABB no garantizan tiempos de búsqueda óptimos. |
| |El algoritmo para mantener un árbol AVL equilibrado se basa en reequilibradoslocales, de modo que no es necesario explorar todo el árbol después de cada inserción o |
| |borrado. |
| | |
| |Operaciones en AVL |
| |Los AVL son también ABB, de modo que mantienen todas las operaciones que poseen éstos. Las nuevas operaciones son las de equilibrar el árbol, pero eso se hace como parte || |de las operaciones de insertado y borrado. |
| |  |
| |Factor de Equilibrio|
| |Cada nodo, además de la información que se pretende almacenar, debe tener un miembro nuevo: el factor de equilibrio. |
| |El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el...