> ## Documentation Index > Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt > Use this file to discover all available pages before exploring further. # Árboles AVL: árboles binarios de búsqueda equilibrados y rotaciones > Árboles binarios de búsqueda y árboles AVL explicados: búsqueda, inserción y borrado en un ABB, por qué se degeneran, factor de equilibrio, rotaciones simples y dobles (LL, RR, LR, RL), inserción paso a paso, altura logarítmica, comparación con árboles rojo-negro y código de ejemplo. 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](https://apuntes.simulab.es/programacion/algoritmos/estructuras-datos.md). | 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 ```python theme={null} 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 > [accordion] 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. > [accordion] 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. > [accordion] 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. > [accordion] 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 > [accordion] ¿Merece la pena frente a una tabla hash? > > Una [tabla hash](https://apuntes.simulab.es/programacion/java/tablas-hash.md) 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. > [accordion] ¿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 > [card] [Estructuras de datos](https://apuntes.simulab.es/programacion/algoritmos/estructuras-datos.md) > > Pilas, colas, listas y árboles animados. > [card] [Árbol binario enhebrado](https://apuntes.simulab.es/programacion/java/arbol-enhebrado.md) > > Recorrer un árbol sin pila. > [card] [Montículos](https://apuntes.simulab.es/programacion/algoritmos/monticulos.md) > > Otro árbol binario con una propiedad distinta. This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.