Rotaciones y balanceo en arboles AVL

Enunciado

Un arbol AVL es un arbol binario de busqueda (BST) auto-balanceado donde, para cada nodo, la diferencia de alturas entre sus subarboles izquierdo y derecho (factor de balance) es como maximo 1:

$FB(nodo) = altura(subarbol_{izq}) - altura(subarbol_{der}), \quad |FB| \leq 1$

(a) Inserte los siguientes valores en orden en un arbol AVL inicialmente vacio:

$[30, 20, 10, 25, 40, 35, 50]$

Para cada insercion:

1. Muestre el arbol despues de insertar el nodo (antes de balancear).
2. Calcule el factor de balance de cada nodo.
3. Si se detecta un desbalance ($|FB| > 1$), identifique el tipo de rotacion necesaria:
   • Rotacion simple a la derecha (caso izquierda-izquierda)
   • Rotacion simple a la izquierda (caso derecha-derecha)
   • Rotacion doble izquierda-derecha (caso izquierda-derecha)
   • Rotacion doble derecha-izquierda (caso derecha-izquierda)
4. Muestre el arbol despues de la rotacion.

(b) Despues de insertar todos los valores, muestre el arbol AVL final con los factores de balance de cada nodo.

(c) Cual es la altura maxima que puede tener un arbol AVL con $n$ nodos? Compare con la altura maxima de un BST sin balanceo.

(d) Explique por que todas las operaciones (busqueda, insercion, eliminacion) en un arbol AVL tienen complejidad garantizada de $O(\log n)$, a diferencia de un BST regular.

(e) Cual es el costo adicional (overhead) de mantener el arbol balanceado? En que escenarios vale la pena usar un AVL en lugar de un BST simple?