¿Qué es un árbol AVL?

Cada nodo en un Árbol AVL rastrea su propia altura: el número de aristas en el camino más largo hacia una hoja. Una hoja tiene una altura de 1, y un subárbol vacío cuenta como altura 0. A partir de la altura de los dos hijos de un nodo, puedes calcular su factor de equilibrio: height(left) - height(right).

Un nodo está equilibrado cuando su factor de equilibrio es -1, 0 o 1. La regla del Árbol AVL es simple: cada uno de los nodos debe permanecer equilibrado, todo el tiempo. Cada vez que una inserción o eliminación empuja el factor de equilibrio de un nodo a 2 o -2, el árbol realiza una rotación: un reordenamiento local de unos pocos punteros que restaura el equilibrio en tiempo constante sin romper el orden del árbol de búsqueda.

Existen cuatro casos de rotación (izquierda-izquierda, derecha-derecha, izquierda-derecha, derecha-izquierda), pero todos se reducen a dos bloques de construcción: una rotación simple a la izquierda y una rotación simple a la derecha. Construirás ambos desde cero en las próximas lecciones.