Reinventarlo

Un invariante de balance

Las rotaciones arreglan la forma. Falta una regla que diga cuándo rotar. Un árbol AVL guarda en cada nodo su altura y mantiene este invariante:

en cada nodo, las alturas de sus dos subárboles difieren como mucho en 1

Al insertar, se baja como en un BST. Al volver por el camino hacia la raíz, se recalculan las alturas, y si un nodo queda con una diferencia de 2, se rota. Si el hijo pesado cuelga hacia el lado contrario (un zigzag), primero se rota ese hijo y después el nodo: es una rotación doble.