AVL Arboles

Podriamos decir que el AVL es una clasificación binaria y aca conseguimos encontrar el mayor equilibrio posible para hacer el árbol ‘ideal’.

• La altura del árbol es clave
• Altura de un nodo: La altura es el camino mas largo desde el nodo hasta la hoja
• Profundidad es: Desde el nodo a la raíz
• la altura max se calcula con la altura del hijo izquierdo mas la altura del hijo derecho + 1[pic 1]

AVL TREE

• Nuestro objetivo será mantener las alturas bajas o ‘equilibradas’, lo natural es almacenar las alturas y cuando el árbol crezca demasiado arreglarlo.
• Los punteros Null podríamos definirlos con una altura -1 y es -1 para que la formula funcione.
• Hacer que ambos lados izquierdo y derecho sean mas o menos iguales
• Exigir alturas de izquierdos y derechos children de cada nodo que difiere entre mas o menos 1 Es decir la formula seria |HL - HR| ≤ 1 si es 0 seria un árbol perfecto
• 0 es imposible y 1 es bueno
• Balanceado es que el orden este sujeto a Log n
• ¿Cual es el peor caso? Cual el árbol derecho tiene un altura mas que el izquierdo por cada nodo. Esto se resolverá con recurrencia y se resuelve con un principio de Fibonacci

Un método para el balanceo de un árbol conseguimos las rotaciones, estas pueden ser simples a la derecha, simples a la izquierda, doble a la derecha o doble a la izquierda. Acá definimos el factor de equilibrio que es la flag que nos indica si esto se realizara o no. FE = altura del subárbol derecho – la altura del subárbol izquierdo, deben cumplir el parámetro que sus valores sean -1, 0 o 1 cada uno tiene significado. El -1 es una carga hacia la izquierda el 0 es equilibrado y el 1 es cargado a la derecha es decir que hay más nodos a la derecha. Cada una de las rotaciones nombradas tiene su ejecución dependiendo su caso cuando calculamos el FE esperamos de 0.  

Este sería el ejemplo sencillo respecto a la rotación:

[pic 2]

Destacamos cada nodo como que el conjunto naranja si o si es menor que el elemento guardado en el nodo T y a su vez menor a W y así con los demás triángulos. Si notamos se encuentra desbalanceado hay una carga al lado izquierdo. Para solucionarlo solo nos vamos a enfocar en dos nodos en este caso T y W aquí realizamos una rotación a la derecha cuando rotamos los notos solo nos queda ajustar los subárboles y ya estaría en equilibrio. Este sería un ejemplo básico de la rotación y el equilibrio que queda.

...