AVL Tree es un árbol de búsqueda binario auto-balanceado donde la diferencia de alturas entre subárboles left y right de cualquier nodo (balance factor) está en {-1, 0, 1}.

Fue el primer BST balanceado (Adelson-Velsky y Landis, 1962). Garantiza altura O(log n) tras cada inserción/eliminación mediante rotations.

Balance Factor

balance_factor = height(left) - height(right)

Válido: -1, 0, 1. Si |balance_factor| > 1, el árbol está desbalanceado y requiere rebalanceo.

Rotations

Casos de Desbalance

Left-Left (LL): insert en subárbol left-left.

• Solución: right rotation en el nodo desbalanceado.

Right-Right (RR): insert en subárbol right-right.

• Solución: left rotation en el nodo desbalanceado.

Left-Right (LR): insert en subárbol left-right.

• Solución: left rotation en left child, luego right rotation en el nodo.

Right-Left (RL): insert en subárbol right-left.

• Solución: right rotation en right child, luego left rotation en el nodo.

Ejemplo: Right Rotation (RR)

Antes:

    z (bf=2)
   / \\
  y   C
 / \\
A   B

Después de right rotation:

    y
   / \\
  A   z
     / \\
    B   C

Altura se reduce en 1; balance factors se actualizan.

Insert y Delete

1. BST insert/delete estándar.
2. Backtrack hacia la raíz, actualizando alturas y balance factors.
3. Si desbalance: aplica la rotation correspondiente.

Comparación con Red-Black

Aplicaciones

• Databases — indexing donde búsquedas dominan
• In-memory maps — C++ std::map (a menudo RB, pero AVL para read-heavy)
• Enseñanza — introduce auto-balance y rotations

Trayectoria de Práctica

1. Implementa AVL tree con insert; traza LR y RL cases.
2. Implementa delete con rebalance.
3. Verifica que altura máxima es O(log n) para n=1000.
4. Compara con BST sin balance: genera árbol degenerado.
5. Investiga Red-Black tree: ¿por qué es más usado en librerías estándar?