4 - Rotaciones en árboles AVL

Las rotaciones mantienen el equilibrio de un árbol AVL sin romper la propiedad de orden de un BST. Cada operación es local, de costo constante, y se decide según el factor de balance (FB) del nodo desbalanceado y de su hijo.

Detección rápida de casos:

  • LL (left-left): FB del nodo = +2 y FB del hijo izquierdo ≥ 0.
  • RR (right-right): FB del nodo = -2 y FB del hijo derecho ≤ 0.
  • LR (left-right): FB del nodo = +2 y FB del hijo izquierdo < 0.
  • RL (right-left): FB del nodo = -2 y FB del hijo derecho > 0.

4.1 Rotación simple a la derecha

Corrige un desbalance izquierda-izquierda (LL) cuando un nodo tiene FB = +2 y su hijo izquierdo tiene FB ≥ 0.

Intuición: el hijo izquierdo sube a raíz del subárbol y el nodo desbalanceado pasa a ser su hijo derecho; el subárbol derecho original del hijo izquierdo (t2) se reubica como hijo izquierdo del nodo desbalanceado.

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

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

  actualizarAltura(y);
  actualizarAltura(x);
  return x;
}

Después de mover subárboles, se recalculan alturas de abajo hacia arriba: primero y, luego x. El costo es O(1) porque solo se ajustan unos pocos punteros.

4.2 Rotación simple a la izquierda

Simétrica a la anterior. Se usa en desbalances derecha-derecha (RR) con FB = -2 y el hijo derecho con FB ≤ 0.

El hijo derecho sube y el nodo desbalanceado pasa a ser hijo izquierdo; el subárbol izquierdo del antiguo hijo derecho (t2) se convierte en hijo derecho del nodo original.

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

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

  actualizarAltura(y);
  actualizarAltura(x);
  return x;
}

La simetría permite reutilizar la misma lógica y sólo invertir punteros, manteniendo la propiedad de orden.

4.3 Rotación doble izquierda-derecha

Resuelve un desbalance izquierda-derecha (LR): FB del nodo es +2 y el hijo izquierdo tiene FB negativo.

  1. Rotar simple a la izquierda el hijo izquierdo.
  2. Rotar simple a la derecha el nodo desbalanceado.

El primer paso convierte el caso en un desbalance LL, listo para la rotación final a la derecha.

AvlNode *rotacionIzquierdaDerecha(AvlNode *nodo) {
  nodo->izquierdo = rotarIzquierda(nodo->izquierdo);
  return rotarDerecha(nodo);
}

Se actualizan alturas en cada llamada interna, por lo que no se requieren ajustes extra después del segundo giro.

4.4 Rotación doble derecha-izquierda

Aplica al caso derecha-izquierda (RL): FB del nodo es -2 y el hijo derecho tiene FB positivo.

  1. Rotar simple a la derecha el hijo derecho.
  2. Rotar simple a la izquierda el nodo desbalanceado.

El primer giro convierte el desbalance en un caso RR que se soluciona con la rotación final a la izquierda.

AvlNode *rotacionDerechaIzquierda(AvlNode *nodo) {
  nodo->derecho = rotarDerecha(nodo->derecho);
  return rotarIzquierda(nodo);
}

En ambos casos dobles, el reequilibrio se logra con dos rotaciones simples, manteniendo la propiedad de BST y ajustando alturas en cada llamada.

vizualizador de arbol AVL

Notas prácticas:

  • Las rotaciones se ejecutan mientras se desenrolla la recursión de inserción o eliminación, por lo que cada llamada calcula el FB y decide el tipo de giro.
  • Son operaciones O(1); el costo total de balanceo tras insertar o eliminar sigue siendo O(log n) por el recorrido de altura del árbol.
  • Para depurar, imprime el FB antes y después de cada rotación; ayudará a detectar cálculos de altura olvidados.
Retornar