9 - Balance y optimización

Tras implementar inserciones y eliminaciones, el siguiente paso es vigilar el balance del árbol. Un ABB degradado puede comportarse como una lista enlazada, elevando el costo de búsqueda a O(n). En este tema explicamos cómo detectar desequilibrios, aplicar rotaciones simples o dobles y rearmar el árbol a partir de un recorrido inorden para recuperar el rendimiento.

9.1 Estructura usada

Partimos del mismo TreeNode utilizado en los temas previos. Si ya cuentas con funciones de inserción y recorrido, puedes integrarlas sin cambios.

typedef struct TreeNode {
  int valor;
  struct TreeNode *izquierdo;
  struct TreeNode *derecho;
} TreeNode;

9.2 Detectar desequilibrios

El factor de balance se define como la diferencia entre la altura del subárbol izquierdo y el derecho. Valores muy grandes (por ejemplo, mayores a 1 o menores a -1) indican que la estructura necesita una rotación.

int altura(TreeNode *nodo) {
  if (!nodo) return 0;
  int izq = altura(nodo->izquierdo);
  int der = altura(nodo->derecho);
  return 1 + (izq > der ? izq : der);
}

int factorBalance(TreeNode *nodo) {
  if (!nodo) return 0;
  return altura(nodo->izquierdo) - altura(nodo->derecho);
}

9.3 Rotaciones simples

Una rotación simple a la derecha compensa un exceso de nodos en la rama izquierda. La rotación a la izquierda actúa de manera simétrica.

TreeNode *rotarDerecha(TreeNode *y) {
  TreeNode *x = y->izquierdo;
  TreeNode *subDerecho = x->derecho;
  x->derecho = y;
  y->izquierdo = subDerecho;
  return x;
}

TreeNode *rotarIzquierda(TreeNode *x) {
  TreeNode *y = x->derecho;
  TreeNode *subIzquierdo = y->izquierdo;
  y->izquierdo = x;
  x->derecho = subIzquierdo;
  return y;
}

9.4 Rotaciones dobles

Si la rama pesada está inclinada en dirección opuesta (casos LR o RL), primero se aplica una rotación simple sobre el hijo y luego una rotación en sentido contrario sobre el nodo problemático.

TreeNode *balancearNodo(TreeNode *nodo) {
  int balance = factorBalance(nodo);

  if (balance > 1) {
    if (factorBalance(nodo->izquierdo) < 0) {
      nodo->izquierdo = rotarIzquierda(nodo->izquierdo);
    }
    return rotarDerecha(nodo);
  }
  if (balance < -1) {
    if (factorBalance(nodo->derecho) > 0) {
      nodo->derecho = rotarDerecha(nodo->derecho);
    }
    return rotarIzquierda(nodo);
  }
  return nodo;
}

9.5 Inserción con balanceo básico

A diferencia del ABB simple, algunas variantes (como AVL) balancean cada nodo durante la inserción. La función siguiente muestra una versión sencilla que llama a balancearNodo al regresar de la recursión.

TreeNode *insertarBalanceado(TreeNode *nodo, int valor) {
  if (!nodo) {
    return crearNodo(valor);
  }
  if (valor < nodo->valor) {
    nodo->izquierdo = insertarBalanceado(nodo->izquierdo, valor);
  } else {
    nodo->derecho = insertarBalanceado(nodo->derecho, valor);
  }
  return balancearNodo(nodo);
}

9.6 Rearmado desde inorden

Cuando el árbol está muy degradado podemos rearmarlo tomando todos los valores, ordenándolos y montando un nuevo ABB balanceado.

void guardarInorden(TreeNode *nodo, int *destino, int *indice) {
  if (!nodo) return;
  guardarInorden(nodo->izquierdo, destino, indice);
  destino[(*indice)++] = nodo->valor;
  guardarInorden(nodo->derecho, destino, indice);
}

TreeNode *armarBalanceado(int *valores, int inicio, int fin) {
  if (inicio > fin) return NULL;
  int medio = (inicio + fin) / 2;
  TreeNode *nodo = crearNodo(valores[medio]);
  nodo->izquierdo = armarBalanceado(valores, inicio, medio - 1);
  nodo->derecho = armarBalanceado(valores, medio + 1, fin);
  return nodo;
}

9.7 Estrategia de optimización

En la práctica combinamos ambas técnicas:

  • Balanceo incremental mediante rotaciones luego de cada inserción o eliminación.
  • Rearmado periódico para limpiar acumulaciones de error.
  • Monitoreo del ancho y de la altura para decidir cuándo ejecutar cada acción.

9.8 Código completo para CLion

El archivo siguiente muestra una inserción balanceada estilo AVL y verifica que el inorden permanezca ordenado tras varias operaciones.

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

typedef struct TreeNode {
  int valor;
  struct TreeNode *izquierdo;
  struct TreeNode *derecho;
} TreeNode;

TreeNode *crearNodo(int valor) {
  TreeNode *n = malloc(sizeof(TreeNode));
  if (!n) return NULL;
  n->valor = valor;
  n->izquierdo = NULL;
  n->derecho = NULL;
  return n;
}

int altura(TreeNode *nodo) {
  if (!nodo) return 0;
  int izq = altura(nodo->izquierdo);
  int der = altura(nodo->derecho);
  return 1 + (izq > der ? izq : der);
}

int factorBalance(TreeNode *nodo) {
  if (!nodo) return 0;
  return altura(nodo->izquierdo) - altura(nodo->derecho);
}

TreeNode *rotarDerecha(TreeNode *y) {
  TreeNode *x = y->izquierdo;
  TreeNode *subDerecho = x->derecho;
  x->derecho = y;
  y->izquierdo = subDerecho;
  return x;
}

TreeNode *rotarIzquierda(TreeNode *x) {
  TreeNode *y = x->derecho;
  TreeNode *subIzquierdo = y->izquierdo;
  y->izquierdo = x;
  x->derecho = subIzquierdo;
  return y;
}

TreeNode *balancearNodo(TreeNode *nodo) {
  int balance = factorBalance(nodo);
  if (balance > 1) {
    if (factorBalance(nodo->izquierdo) < 0) {
      nodo->izquierdo = rotarIzquierda(nodo->izquierdo);
    }
    return rotarDerecha(nodo);
  }
  if (balance < -1) {
    if (factorBalance(nodo->derecho) > 0) {
      nodo->derecho = rotarDerecha(nodo->derecho);
    }
    return rotarIzquierda(nodo);
  }
  return nodo;
}

TreeNode *insertarBalanceado(TreeNode *nodo, int valor) {
  if (!nodo) return crearNodo(valor);
  if (valor < nodo->valor) nodo->izquierdo = insertarBalanceado(nodo->izquierdo, valor);
  else nodo->derecho = insertarBalanceado(nodo->derecho, valor);
  return balancearNodo(nodo);
}

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

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

int main(void) {
  int valores[] = {30, 20, 40, 10, 25, 35, 50, 5, 27};
  unsigned int total = (unsigned int)(sizeof(valores)/sizeof(valores[0]));
  TreeNode *raiz = NULL;
  for (unsigned int i = 0; i < total; i++) {
    raiz = insertarBalanceado(raiz, valores[i]);
  }
  puts("Inorden tras inserciones balanceadas:");
  imprimirInorden(raiz);
  printf("\nAltura final: %d\n", altura(raiz));
  liberar(raiz);
  return 0;
}
Retornar