3 - Árboles AVL

Los árboles AVL son la primera familia de árboles de búsqueda balanceados diseñada para mantener altura logarítmica. Cada nodo almacena su altura y exige que el factor de balance permanezca en el rango [-1, 1]. Cuando se viola esa condición, se aplican rotaciones para restaurar el equilibrio.

3.1 Definición y propiedades

  • Un AVL es un árbol de búsqueda binaria (BST) en el que, para cada nodo, la diferencia entre las alturas de sus subárboles izquierdo y derecho es -1, 0 o 1.
  • La altura de un AVL con n nodos está acotada por O(log n), garantizando búsquedas, inserciones y eliminaciones rápidas.
  • El balance estricto implica más rotaciones que en un Red-Black Tree, pero ofrece una altura menor en promedio.
  • El mantenimiento del equilibrio se realiza localmente: solo se ajustan los nodos en el camino desde el punto de inserción o eliminación hasta la raíz.

3.2 Estructura del nodo en Python

El nodo conserva la clave, la altura precomputada y las referencias a los hijos. Es común guardar también una referencia al padre, pero no es obligatorio para las operaciones básicas.

class AvlNode:
  def __init__(self, clave):
    self.clave = clave
    self.altura = 0  # hoja
    self.izquierdo = None
    self.derecho = None

def crear_nodo_avl(clave):
  return AvlNode(clave)

3.3 Cálculo de la altura

Guardar la altura en cada nodo permite recalcular rápido después de una inserción o rotación. Un nodo nulo usa altura -1, de modo que una hoja quede en 0.

def altura_nodo_avl(nodo):
  return nodo.altura if nodo else -1

def actualizar_altura(nodo):
  if not nodo:
    return
  h_izq = altura_nodo_avl(nodo.izquierdo)
  h_der = altura_nodo_avl(nodo.derecho)
  nodo.altura = 1 + max(h_izq, h_der)

Al actualizar la altura desde la rama que se modifica hacia la raíz, mantenemos listo el dato para evaluar el factor de balance en O(1).

3.4 Factor de balance

El factor de balance (FB) es la resta entre la altura del subárbol izquierdo y el derecho. Si el valor cae fuera de [-1, 1], el nodo requiere rotación.

def factor_balance_avl(nodo):
  if not nodo:
    return 0
  return altura_nodo_avl(nodo.izquierdo) - altura_nodo_avl(nodo.derecho)

El FB guía la elección de rotación: LL y RR para desbalances simples, LR y RL para desbalances en zig-zag. En el siguiente tema aplicaremos este cálculo a la inserción y eliminación.

Retornar