5 - Inserción en AVL

Insertar en un AVL combina el recorrido de un BST con pasos extra de balanceo. Tras colocar la nueva clave, se recalculan alturas y se corrige cualquier desbalance usando las rotaciones LL, RR, LR o RL descritas en el tema anterior. El objetivo es conservar altura O(log n) aun con datos adversos.

vizualizador de arbol AVL

5.1 Inserción normal tipo BST

El primer tramo repite la lógica de un árbol de búsqueda: bajar por izquierda si la clave es menor, derecha si es mayor. No se permiten duplicados para simplificar.

  • Si el nodo actual es nulo, se crea una nueva hoja con altura 0.
  • Si la clave ya existe, se devuelve el nodo sin cambios.
  • El enlace de retorno conecta la subllamada al hijo correspondiente.

5.2 Actualización de alturas

Al volver de la recursión, cada nodo recalcula su altura usando las alturas de sus hijos. Esto prepara el dato para evaluar el factor de balance en O(1).

  • Altura de nodo nulo: -1.
  • Altura de nodo: 1 + max(alturaIzq, alturaDer).
  • Se actualiza desde el nodo hijo hacia la raíz.

5.3 Detección de desbalance

El factor de balance (FB) es la resta entre la altura izquierda y la derecha. Si |FB| > 1, el nodo está desbalanceado y requiere una rotación que dependen del signo de FB y del subárbol donde se insertó la clave.

  • FB > 1 implica exceso a la izquierda; FB < -1, exceso a la derecha.
  • El signo del FB del hijo afectado indica si es un caso simple (LL o RR) o doble (LR o RL).
  • El ajuste se hace localmente: rotar el nodo actual y devolver el nuevo subárbol equilibrado.

5.4 Casos LL, RR, LR y RL

El algoritmo completa la inserción aplicando la rotación correcta según la posición de la clave insertada:

AvlNode *insertarAvl(AvlNode *nodo, int clave) {
  if (!nodo) return crearNodoAvl(clave);

  if (clave < nodo->clave) {
    nodo->izquierdo = insertarAvl(nodo->izquierdo, clave);
  } else if (clave > nodo->clave) {
    nodo->derecho = insertarAvl(nodo->derecho, clave);
  } else {
    return nodo; /* duplicado: no se inserta */
  }

  actualizarAltura(nodo);
  int fb = factorBalanceAvl(nodo);

  /* LL */
  if (fb > 1 && clave < nodo->izquierdo->clave) {
    return rotarDerecha(nodo);
  }
  /* RR */
  if (fb < -1 && clave > nodo->derecho->clave) {
    return rotarIzquierda(nodo);
  }
  /* LR */
  if (fb > 1 && clave > nodo->izquierdo->clave) {
    nodo->izquierdo = rotarIzquierda(nodo->izquierdo);
    return rotarDerecha(nodo);
  }
  /* RL */
  if (fb < -1 && clave < nodo->derecho->clave) {
    nodo->derecho = rotarDerecha(nodo->derecho);
    return rotarIzquierda(nodo);
  }

  return nodo;
}

Notas prácticas:

  • La función supone helpers previos: crearNodoAvl, actualizarAltura, factorBalanceAvl, rotarDerecha y rotarIzquierda de los temas anteriores.
  • Si se permiten duplicados, se puede definir una regla (por ejemplo, ir siempre a la derecha) y adaptar las condiciones de casos LR/RL acorde al subárbol usado.
  • Tras cada rotación se devuelven las nuevas raíces de subárbol; no olvide asignarlas al padre en el llamado recursivo.

5.5 Código completo para probar en CLion

Ejemplo autocontenible con inserciones y recorrido inorden. Copia, compila y ejecuta.

#include <stdio.h>
#include <stdlib.h>

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

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);
}

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

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

AvlNode *rotarDerecha(AvlNode *y) {
  AvlNode *x = y->izquierdo;
  AvlNode *t2 = x->derecho;
  x->derecho = y;
  y->izquierdo = t2;
  actualizarAltura(y);
  actualizarAltura(x);
  return x;
}

AvlNode *rotarIzquierda(AvlNode *y) {
  AvlNode *x = y->derecho;
  AvlNode *t2 = x->izquierdo;
  x->izquierdo = y;
  y->derecho = t2;
  actualizarAltura(y);
  actualizarAltura(x);
  return x;
}

AvlNode *insertarAvl(AvlNode *nodo, int clave) {
  if (!nodo) return crearNodoAvl(clave);
  if (clave < nodo->clave) nodo->izquierdo = insertarAvl(nodo->izquierdo, clave);
  else if (clave > nodo->clave) nodo->derecho = insertarAvl(nodo->derecho, clave);
  else return nodo; /* duplicado */

  actualizarAltura(nodo);
  int fb = factorBalanceAvl(nodo);

  if (fb > 1 && clave < nodo->izquierdo->clave) return rotarDerecha(nodo);       /* LL */
  if (fb < -1 && clave > nodo->derecho->clave) return rotarIzquierda(nodo);      /* RR */
  if (fb > 1 && clave > nodo->izquierdo->clave) {                                /* LR */
    nodo->izquierdo = rotarIzquierda(nodo->izquierdo);
    return rotarDerecha(nodo);
  }
  if (fb < -1 && clave < nodo->derecho->clave) {                                 /* RL */
    nodo->derecho = rotarDerecha(nodo->derecho);
    return rotarIzquierda(nodo);
  }
  return nodo;
}

void imprimirInorden(AvlNode *nodo) {
  if (!nodo) return;
  imprimirInorden(nodo->izquierdo);
  printf("%d ", nodo->clave);
  imprimirInorden(nodo->derecho);
}

void liberar(AvlNode *nodo) {
  if (!nodo) return;
  liberar(nodo->izquierdo);
  liberar(nodo->derecho);
  free(nodo);
}

int main(void) {
  int claves[] = {30, 20, 40, 10, 25, 50, 5, 35};
  int n = (int)(sizeof(claves) / sizeof(claves[0]));
  AvlNode *raiz = NULL;

  for (int i = 0; i < n; ++i) {
    raiz = insertarAvl(raiz, claves[i]);
  }

  printf("AVL en inorden: ");
  imprimirInorden(raiz);
  printf("\n");

  liberar(raiz);
  return 0;
}
Visualización de un árbol AVL equilibrado
Retornar