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.

def rotar_derecha(y):
  x = y.izquierdo
  t2 = x.derecho

  x.derecho = y
  y.izquierdo = t2

  actualizar_altura(y)
  actualizar_altura(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.

def rotar_izquierda(y):
  x = y.derecho
  t2 = x.izquierdo

  x.izquierdo = y
  y.derecho = t2

  actualizar_altura(y)
  actualizar_altura(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.

def rotacion_izquierda_derecha(nodo):
  nodo.izquierdo = rotar_izquierda(nodo.izquierdo)
  return rotar_derecha(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.

def rotacion_derecha_izquierda(nodo):
  nodo.derecho = rotar_derecha(nodo.derecho)
  return rotar_izquierda(nodo)

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

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.