1 - Introducción a los árboles balanceados

Iniciamos el recorrido por los árboles de búsqueda balanceados, estructuras que controlan su altura para evitar que las operaciones se degraden a tiempo lineal. Trabajaremos en C y usaremos como ejemplos los dos clásicos: AVL y Red-Black Tree.

Este primer tema define el concepto de balanceo, repasa por qué un Binary Search Tree (BST) puede terminar desbalanceado, y muestra por qué el equilibrio mantiene las operaciones en O(log n). También listamos escenarios reales donde resulta imprescindible.

1.1 Qué significa balancear un árbol

Balancear un árbol es limitar su altura para que crezca de manera proporcional a la cantidad de nodos. Un árbol está bien balanceado cuando la diferencia de alturas entre subárboles es pequeña y la altura total es cercana a log2(n). Para lograrlo, las variantes balanceadas imponen invariantes fáciles de chequear después de cada inserción o eliminación.

• Altura acotada: la altura se mantiene proporcional al logaritmo del número de nodos.
• Factor de balance: en AVL, la diferencia de alturas entre hijos izquierdo y derecho de cada nodo está en el rango [-1, 1].
• Reequilibrio local: rotaciones y recoloreos corrigen el desbalance desde el nodo afectado hacia la raíz.

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

int alturaNodo(NodoBalanceado *nodo) {
  return nodo ? nodo->altura : -1;
}

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

El esqueleto anterior refleja el estilo de nodos balanceados: se almacena la altura para recalcular rápido el factor de equilibrio y decidir si se necesitan rotaciones.

1.2 Problema del desbalance en BST

Un árbol de búsqueda (BST) sin políticas de balanceo puede degenerar cuando los datos llegan en orden ascendente o descendente. El resultado es una estructura con forma de lista enlazada:

• Altura lineal: con n nodos, la altura pasa a ser n-1, porque cada inserción cuelga del extremo derecho o izquierdo.
• Operaciones degradadas: búsquedas, inserciones y eliminaciones tardan O(n); la ventaja del árbol desaparece.
• Cache menos efectiva: se recorren más nodos consecutivos en memoria, lo que reduce la localidad y empeora el rendimiento práctico.

Balancear es la respuesta natural: impide que un caso de datos ordenados arruine la complejidad de las operaciones.

1.3 Importancia del equilibrio para O(log n)

Si la altura permanece proporcional al logaritmo del número de nodos, cada operación visita como máximo unos pocos niveles:

• Exploración controlada: la cantidad de comparaciones crece despacio; duplicar los nodos solo añade un nivel extra.
• Costos estables: las inserciones y eliminaciones incluyen pasos adicionales (rotaciones o recoloreos), pero siguen siendo O(log n).
• Escalabilidad real: al mantener la altura baja se soportan más claves sin que la latencia crezca de forma dramática.

AVL logra esta garantía con un balance estricto en cada nodo; Red-Black Tree opta por reglas de color que permiten un poco más de altura a cambio de menos rotaciones promedio.

1.4 Aplicaciones reales

Los árboles balanceados sostienen servicios y bibliotecas que dependen de operaciones rápidas incluso en escenarios adversos:

• Índices de bases de datos: muchas implementaciones usan variantes balanceadas para ordenar claves y resolver consultas de rango.
• Tablas de símbolos en compiladores: asociar identificadores a tipos u offsets requiere búsquedas consistentes en cada etapa de compilación.
• Gestores de memoria: estructuras como los buddy allocators y mapas de intervalos usan árboles balanceados para ubicar huecos libres.
• Planificadores y colas priorizadas: la prioridad cambia a menudo; balancear evita cuellos de botella en inserciones y extracciones.
• Ruteo y seguridad: tablas de reglas, ACL (listas de control de acceso) y ruteo por prefijos se benefician de búsquedas logarítmicas aun con miles de entradas.

Con esta base clara, en los siguientes temas profundizaremos en las propiedades formales y los algoritmos específicos de AVL y Red-Black Tree.