6 - Eliminación en AVL

Eliminar en un AVL combina la lógica de un BST con una pasada extra para restaurar el balance. Tras desconectar el nodo, se recalculan alturas, se detectan desbalances y se aplican las rotaciones LL, RR, LR o RL que correspondan.

6.1 Eliminación tipo BST

  • Se busca la clave bajando por izquierda o derecha según corresponda.
  • Si el nodo tiene un hijo o ninguno, se reemplaza por su hijo existente (o por NULL).
  • Si tiene dos hijos, se toma el sucesor inorden (mínimo del subárbol derecho), se copia su clave y luego se elimina el sucesor.

6.2 Ajustes posteriores

Al volver de la recursión, cada nodo recalcula su altura con la fórmula conocida 1 + max(alturaIzq, alturaDer). Esta actualización es necesaria para que el factor de balance quede consistente antes de revisar un posible desbalance.

6.3 Detección de desbalance

  • Se calcula el factor de balance (FB) del nodo actual.
  • Si FB queda fuera de [-1, 1], el subárbol necesita una rotación.
  • Para elegir el caso correcto se mira el signo del FB y del FB del hijo más alto.

6.4 Rotaciones de reequilibrio

La combinación de signos determina la rotación:

  • LL: FB > 1 y el FB del hijo izquierdo ≥ 0. Rotación simple a la derecha.
  • LR: FB > 1 y el FB del hijo izquierdo < 0. Rotación izquierda en el hijo, luego derecha.
  • RR: FB < -1 y el FB del hijo derecho ≤ 0. Rotación simple a la izquierda.
  • RL: FB < -1 y el FB del hijo derecho > 0. Rotación derecha en el hijo, luego izquierda.
typedef struct AvlNode {
  int clave;
  int altura;
  struct AvlNode *izquierdo;
  struct AvlNode *derecho;
} AvlNode;

static int alturaNodo(AvlNode *n) { return n ? n->altura : -1; }

static AvlNode *minNodo(AvlNode *n) {
  while (n && n->izquierdo) n = n->izquierdo;
  return n;
}

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

static int factorBalance(AvlNode *n) {
  if (!n) return 0;
  return alturaNodo(n->izquierdo) - alturaNodo(n->derecho);
}

AvlNode *rotarDerecha(AvlNode *y);
AvlNode *rotarIzquierda(AvlNode *x);

AvlNode *eliminarAvl(AvlNode *raiz, int clave) {
  if (!raiz) return NULL;

  if (clave < raiz->clave) {
    raiz->izquierdo = eliminarAvl(raiz->izquierdo, clave);
  } else if (clave > raiz->clave) {
    raiz->derecho = eliminarAvl(raiz->derecho, clave);
  } else {
    if (!raiz->izquierdo || !raiz->derecho) {
      AvlNode *hijo = raiz->izquierdo ? raiz->izquierdo : raiz->derecho;
      free(raiz);
      return hijo;
    } else {
      AvlNode *succ = minNodo(raiz->derecho);
      raiz->clave = succ->clave;
      raiz->derecho = eliminarAvl(raiz->derecho, succ->clave);
    }
  }

  raiz->altura = 1 + max(alturaNodo(raiz->izquierdo), alturaNodo(raiz->derecho));
  int fb = factorBalance(raiz);

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

  return raiz;
}

6.5 Código completo para probar en CLion

Ejemplo autocontenible que inserta, elimina claves y muestra el inorden antes y después. 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; }
static int alturaNodo(AvlNode *n) { return n ? n->altura : -1; }

static void actualizarAltura(AvlNode *n) {
  if (!n) return;
  n->altura = 1 + max(alturaNodo(n->izquierdo), alturaNodo(n->derecho));
}

static int factorBalance(AvlNode *n) {
  if (!n) return 0;
  return alturaNodo(n->izquierdo) - alturaNodo(n->derecho);
}

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 *crearNodo(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 *minNodo(AvlNode *n) {
  while (n && n->izquierdo) n = n->izquierdo;
  return n;
}

AvlNode *insertarAvl(AvlNode *raiz, int clave) {
  if (!raiz) return crearNodo(clave);
  if (clave < raiz->clave) raiz->izquierdo = insertarAvl(raiz->izquierdo, clave);
  else if (clave > raiz->clave) raiz->derecho = insertarAvl(raiz->derecho, clave);
  else return raiz;

  actualizarAltura(raiz);
  int fb = factorBalance(raiz);

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

AvlNode *eliminarAvl(AvlNode *raiz, int clave) {
  if (!raiz) return NULL;

  if (clave < raiz->clave) {
    raiz->izquierdo = eliminarAvl(raiz->izquierdo, clave);
  } else if (clave > raiz->clave) {
    raiz->derecho = eliminarAvl(raiz->derecho, clave);
  } else {
    if (!raiz->izquierdo || !raiz->derecho) {
      AvlNode *hijo = raiz->izquierdo ? raiz->izquierdo : raiz->derecho;
      free(raiz);
      return hijo;
    } else {
      AvlNode *succ = minNodo(raiz->derecho);
      raiz->clave = succ->clave;
      raiz->derecho = eliminarAvl(raiz->derecho, succ->clave);
    }
  }

  actualizarAltura(raiz);
  int fb = factorBalance(raiz);

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

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

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

int main(void) {
  int claves[] = {30, 20, 40, 10, 25, 50, 5, 35, 45};
  int eliminar[] = {10, 40, 30};
  int n1 = (int)(sizeof(claves) / sizeof(claves[0]));
  int n2 = (int)(sizeof(eliminar) / sizeof(eliminar[0]));

  AvlNode *raiz = NULL;
  for (int i = 0; i < n1; ++i) raiz = insertarAvl(raiz, claves[i]);

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

  for (int j = 0; j < n2; ++j) {
    raiz = eliminarAvl(raiz, eliminar[j]);
    printf("Tras eliminar %d: ", eliminar[j]);
    imprimirInorden(raiz);
    printf("\n");
  }

  printf("AVL final: ");
  imprimirInorden(raiz);
  printf("\n");

  liberar(raiz);
  return 0;
}
Secuencia de eliminación y rebalanceo en un árbol AVL
Retornar