Árboles AVL: árboles binarios de búsqueda equilibrados y rotaciones

Un árbol binario de búsqueda (ABB) permite buscar, insertar y borrar en tiempo proporcional a su altura. Si está bien repartido, eso es

O(\log n)

: un millón de elementos en unos 20 pasos. Pero si los datos llegan ordenados, el árbol degenera en una lista y todo pasa a costar

O(n)

. Los árboles AVL (Adelson-Velski y Landis, 1962) fueron la primera solución: después de cada inserción o borrado, comprueban el equilibrio y lo corrigen con unas operaciones llamadas rotaciones.

Lo que vas a aprender

Cómo funciona un árbol binario de búsqueda.
Por qué un ABB se puede degenerar.
Qué es el factor de equilibrio de un nodo.
Las rotaciones simples y dobles, y cuándo aplicar cada una.
Cómo insertar en un AVL paso a paso.
Por qué la altura de un AVL es siempre logarítmica.

Fundamentos teóricos

Árbol binario de búsqueda

En cada nodo, todo lo que hay en el subárbol izquierdo es menor y todo lo del derecho es mayor. Para buscar se compara con la raíz y se baja por un lado. El recorrido en inorden (izquierda, raíz, derecha) da los elementos ordenados. Puedes ver árboles animados en el simulador de estructuras de datos.

Operación	Árbol equilibrado	Árbol degenerado
Buscar	$O(\log n)$	$O(n)$
Insertar	$O(\log n)$	$O(n)$
Borrar	$O(\log n)$	$O(n)$

Insertar 1, 2, 3, 4, 5 en orden da una “rama” con todos los nodos a la derecha: una lista enlazada con más memoria.

Factor de equilibrio

FE(\text{nodo}) = h(\text{subárbol derecho}) - h(\text{subárbol izquierdo})

(algunos libros lo definen al revés; lo importante es ser coherente). Un árbol es AVL si en todos los nodos

FE \in \{-1, 0, +1\}

Rotaciones

Cuando una inserción deja un nodo con

|FE| = 2

, se corrige con una rotación sobre ese nodo (el más bajo que se haya desequilibrado):

Caso	Situación	Solución
LL (izquierda-izquierda)	Se insertó en el subárbol izquierdo del hijo izquierdo	Rotación simple a la derecha
RR (derecha-derecha)	En el subárbol derecho del hijo derecho	Rotación simple a la izquierda
LR (izquierda-derecha)	En el subárbol derecho del hijo izquierdo	Rotación izquierda en el hijo y luego derecha en el nodo
RL (derecha-izquierda)	En el subárbol izquierdo del hijo derecho	Rotación derecha en el hijo y luego izquierda en el nodo

Rotación simple a la derecha sobre el nodo

A

con hijo izquierdo

B

B

sube a ocupar el lugar de

A

A

pasa a ser hijo derecho de

B

, y el antiguo subárbol derecho de

B

pasa a ser el izquierdo de

A

. Se conserva el orden del ABB y solo cambian tres punteros.

        A                B
       / \              / \
      B   T3    →     T1   A
     / \                  / \
   T1   T2              T2   T3

Código de una inserción

class Nodo:
    def __init__(self, clave):
        self.clave, self.izq, self.der, self.altura = clave, None, None, 1

def h(n): return n.altura if n else 0
def actualizar(n): n.altura = 1 + max(h(n.izq), h(n.der))
def fe(n): return h(n.der) - h(n.izq)

def rot_der(a):
    b = a.izq
    a.izq, b.der = b.der, a
    actualizar(a); actualizar(b)
    return b

def rot_izq(a):
    b = a.der
    a.der, b.izq = b.izq, a
    actualizar(a); actualizar(b)
    return b

def insertar(n, clave):
    if n is None:
        return Nodo(clave)
    if clave < n.clave:
        n.izq = insertar(n.izq, clave)
    else:
        n.der = insertar(n.der, clave)
    actualizar(n)
    if fe(n) < -1:                       # cargado a la izquierda
        if fe(n.izq) > 0:                # caso LR
            n.izq = rot_izq(n.izq)
        return rot_der(n)                # caso LL
    if fe(n) > 1:                        # cargado a la derecha
        if fe(n.der) < 0:                # caso RL
            n.der = rot_der(n.der)
        return rot_izq(n)                # caso RR
    return n

En una inserción basta una rotación (simple o doble) para reequilibrar todo el árbol. En un borrado pueden hacer falta varias, subiendo hasta la raíz.

Altura logarítmica

El AVL con menos nodos para una altura

h

tiene

N(h) = N(h-1) + N(h-2) + 1

nodos: crece como Fibonacci. De ahí sale que la altura de un AVL con

n

nodos es como mucho unas

h < 1{,}44\log_2(n + 2)

Es decir, en el peor caso es solo un 44 % más alto que un árbol perfecto.

AVL frente a rojo-negro

	AVL	Rojo-negro
Equilibrio	Más estricto	Más relajado (altura hasta $2\log_2 n$ )
Búsquedas	Algo más rápidas	Algo más lentas
Inserciones y borrados	Más rotaciones	Menos rotaciones
Uso	Bases de datos en memoria, muchas lecturas	`TreeMap` de Java, `std::map` de C++, el núcleo de Linux

En disco se usan árboles B, con muchos hijos por nodo, para leer pocos bloques.

Ejemplos resueltos

Ejemplo 1 · Insertar 10, 20, 30 (caso RR)

Tras insertar 10 y 20, el 20 es hijo derecho del 10. Al insertar 30 como hijo derecho del 20, el nodo 10 queda con

FE = +2

, y su hijo derecho con

+1

: caso RR.Rotación a la izquierda sobre 10: el 20 sube a la raíz, con 10 a la izquierda y 30 a la derecha.

Ejemplo 2 · Insertar 30, 10, 20 (caso LR)

30 es la raíz, 10 su hijo izquierdo y 20 el hijo derecho del 10. El 30 queda con

FE = -2

y su hijo izquierdo con

+1

: caso LR.Rotación izquierda sobre 10 (el 20 sube sobre el 10) y rotación derecha sobre 30. Resultado: 20 en la raíz, 10 y 30 como hijos.

Ejemplo 3 · Secuencia completa

Insertar 1, 2, 3, 4, 5, 6, 7 en orden:

1, 2, 3: rotación RR en 1. Raíz 2.
4, 5: rotación RR en 3. Árbol: 2 (1, 4 (3, 5)).
6: el 2 queda con $FE = +2$ : rotación RR en 2. Raíz 4: 4 (2 (1, 3), 5 (—, 6)).
7: rotación RR en 5.

Resultado: un árbol perfecto de altura 3 con raíz 4. Un ABB sin equilibrar habría quedado como una lista de altura 7.

Ejemplo 4 · ¿Es AVL?

Raíz 8 con hijo izquierdo 4 (hijos 2 y 6) y sin hijo derecho. La raíz tiene subárbol izquierdo de altura 2 y derecho de altura 0:

FE = -2

. No es AVL: necesitaría una rotación derecha (caso LL, porque

FE(4) = 0

y se trata como LL).

Errores frecuentes

Rotar sobre la raíz en lugar del nodo desequilibrado más bajo.
Aplicar una rotación simple en un caso doble (LR o RL): el árbol sigue desequilibrado.
Olvidar actualizar las alturas después de cada rotación, de abajo arriba.
Confundir el signo del factor de equilibrio al mezclar convenios de libros distintos.
Perder un subárbol al rotar: el subárbol “del medio” (T2) cambia de padre.

Preguntas frecuentes

¿Merece la pena frente a una tabla hash?

Una tabla hash busca en

O(1)

de media, más rápido. Pero un árbol mantiene los datos ordenados: permite recorrerlos en orden, buscar el mínimo, el máximo, el siguiente de un valor o todos los valores de un rango. Para eso, un árbol equilibrado es mejor.

¿Y el borrado?

Se borra como en un ABB (si el nodo tiene dos hijos, se sustituye por su sucesor en inorden) y luego se sube hacia la raíz comprobando el equilibrio de cada antecesor y rotando donde haga falta.

Temas relacionados

Estructuras de datos

Pilas, colas, listas y árboles animados.

Árbol binario enhebrado

Recorrer un árbol sin pila.

Montículos

Otro árbol binario con una propiedad distinta.

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Árboles AVL: árboles binarios de búsqueda equilibrados y rotaciones

Lo que vas a aprender

Fundamentos teóricos

Árbol binario de búsqueda

Factor de equilibrio

Rotaciones

Código de una inserción

Altura logarítmica

AVL frente a rojo-negro

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados

Estructuras de datos

Árbol binario enhebrado

Montículos

​Lo que vas a aprender

​Fundamentos teóricos

​Árbol binario de búsqueda

​Factor de equilibrio

​Rotaciones

​Código de una inserción

​Altura logarítmica

​AVL frente a rojo-negro

​Ejemplos resueltos

​Errores frecuentes

​Preguntas frecuentes

​Temas relacionados

Estructuras de datos

Árbol binario enhebrado

Montículos

Lo que vas a aprender

Fundamentos teóricos

Árbol binario de búsqueda

Factor de equilibrio

Rotaciones

Código de una inserción

Altura logarítmica

AVL frente a rojo-negro

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados