3 - Árboles AVL

Los árboles AVL son la primera familia de árboles de búsqueda balanceados diseñada para mantener altura logarítmica. Cada nodo almacena su altura y exige que el factor de balance permanezca en el rango [-1, 1]. Cuando se viola esa condición, se aplican rotaciones para restaurar el equilibrio.

3.1 Definición y propiedades

  • Un AVL es un árbol de búsqueda binaria (BST) en el que, para cada nodo, la diferencia entre las alturas de sus subárboles izquierdo y derecho es -1, 0 o 1.
  • La altura de un AVL con n nodos está acotada por O(log n), garantizando búsquedas, inserciones y eliminaciones rápidas.
  • El balance estricto implica más rotaciones que en un Red-Black Tree, pero ofrece una altura menor en promedio.
  • El mantenimiento del equilibrio se realiza localmente: solo se ajustan los nodos en el camino desde el punto de inserción o eliminación hasta la raíz.

3.2 Estructura del nodo en C

El nodo conserva la clave, la altura precomputada y los punteros a los hijos. Es común guardar también un puntero al padre, pero no es obligatorio para las operaciones básicas.

typedef struct AvlNode {
  int clave;
  int altura;
  struct AvlNode *izquierdo;
  struct AvlNode *derecho;
} AvlNode;

AvlNode *crearNodoAvl(int clave) {
  AvlNode *n = malloc(sizeof(AvlNode));
  if (!n) return NULL;
  n->clave = clave;
  n->altura = 0; /* hoja */
  n->izquierdo = n->derecho = NULL;
  return n;
}

3.3 Cálculo de la altura

Guardar la altura en cada nodo permite recalcular rápido después de una inserción o rotación. Un nodo nulo usa altura -1, de modo que una hoja quede en 0.

static int max(int a, int b) { return (a > b) ? a : b; }

int alturaNodoAvl(AvlNode *nodo) {
  return nodo ? nodo->altura : -1;
}

void actualizarAltura(AvlNode *nodo) {
  if (!nodo) return;
  int hIzq = alturaNodoAvl(nodo->izquierdo);
  int hDer = alturaNodoAvl(nodo->derecho);
  nodo->altura = 1 + max(hIzq, hDer);
}

Al actualizar la altura desde la rama que se modifica hacia la raíz, mantenemos listo el dato para evaluar el factor de balance en O(1).

3.4 Factor de balance

El factor de balance (FB) es la resta entre la altura del subárbol izquierdo y el derecho. Si el valor cae fuera de [-1, 1], el nodo requiere rotación.

int factorBalanceAvl(AvlNode *nodo) {
  if (!nodo) return 0;
  return alturaNodoAvl(nodo->izquierdo) - alturaNodoAvl(nodo->derecho);
}

El FB guía la elección de rotación: LL y RR para desbalances simples, LR y RL para desbalances en zig-zag. En el siguiente tema aplicaremos este cálculo a la inserción y eliminación.

Retornar