2 - Conceptos generales aplicados a AVL y Red-Black

Antes de profundizar en los algoritmos específicos de AVL y Red-Black Tree, conviene repasar cuatro conceptos que ambos comparten: cómo medir la altura, calcular el factor de equilibrio, usar rotaciones y entender por qué las complejidades siguen siendo logarítmicas.

2.1 Altura del árbol

La altura es la cantidad de aristas del camino más largo desde la raíz hasta una hoja. Se usa como indicador de la profundidad de búsqueda.

• Un nodo nulo suele tener altura -1 o 0 según la convención; aqui usamos -1 para que una hoja tenga altura 0.
• La altura de un nodo se define como 1 + max(altura(hijoIzq), altura(hijoDer)).
• En árboles balanceados, la altura crece como O(log n); es la propiedad que queremos preservar.

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

2.2 Factor de equilibrio

El factor de equilibrio (FB, factor de balance) compara las alturas de los subárboles izquierdo y derecho de un nodo.

• En AVL, el FB debe estar en el intervalo [-1, 1] para considerarse equilibrado.
• En Red-Black Tree no se guarda el FB explícito; el color y las reglas de altura negra cumplen el mismo rol de control.
• El FB orienta las decisiones de rotación tras insertar o eliminar.

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

2.3 Rotaciones

Las rotaciones son transformaciones locales que reordenan nodos para recuperar el balance sin perder el orden del BST. Se aplican tanto en AVL como en Red-Black Tree.

• Simple a la derecha (LL, left-left): corrige un exceso en el subárbol izquierdo.
• Simple a la izquierda (RR, right-right): simétrica de la anterior, corrige exceso a la derecha.
• Doble izquierda-derecha (LR, left-right): primero gira el hijo izquierdo a la izquierda, luego el nodo a la derecha.
• Doble derecha-izquierda (RL, right-left): primero gira el hijo derecho a la derecha, luego el nodo a la izquierda.

struct NodoBalanceado *rotarDerecha(struct NodoBalanceado *y) {
  struct NodoBalanceado *x = y->izquierdo;
  struct NodoBalanceado *t2 = x->derecho;

  x->derecho = y;
  y->izquierdo = t2;

  y->altura = 1 + max(alturaNodo(y->izquierdo), alturaNodo(y->derecho));
  x->altura = 1 + max(alturaNodo(x->izquierdo), alturaNodo(x->derecho));
  return x;
}

Actualizar alturas tras cada rotación evita cálculos repetidos y mantiene coherente el FB en el camino de regreso.

2.4 Garantía de complejidad

La motivación del balanceo es sostener la complejidad O(log n) en las operaciones principales:

• Búsqueda: el camino desde la raíz hasta un nodo toma a lo sumo la altura, que se mantiene logarítmica.
• Inserción/eliminación: además de recorrer el camino de búsqueda, se ejecutan un número constante de rotaciones o recoloreos.
• AVL vs Red-Black: AVL impone balance más estricto (altura menor), pero realiza más rotaciones; Red-Black admite algo más de altura a cambio de menos ajustes.

Estas garantías son las que habilitan a usar estas estructuras en sistemas que deben responder rápido y de forma estable aun con datos adversos.