Inserta, elimina y busca nodos. Compara un árbol binario de búsqueda simple con un AVL auto-balanceado y observa las rotaciones LL, RR, LR y RL paso a paso.
El árbol está vacío. Inserta valores para comenzar.
Número de nodos0
Altura del árbol0
TipoAVL
Recorridos del árbol
INORDEN (LNR)
Devuelve los valores en orden creciente
—
PREORDEN (NLR)
Útil para reconstruir el árbol o copiarlo
—
POSTORDEN (LRN)
Útil para liberar memoria y eliminar el árbol
—
POR NIVELES (BFS)
Recorrido en anchura, nivel por nivel
—
Historial de rotaciones AVL (0)
Aún no se ha realizado ninguna rotación. Prueba el ejemplo “Inserción ordenada”.
📝 Casos para clase
12 problemas con solución, siempre los mismos y en el mismo orden. Un profesor puede decir «resuelve los casos 3, 7 y 11» y corregir sin ambigüedad. Puedes comprobar cada resultado insertando la secuencia en el simulador de arriba, con el modo (BST o AVL) que diga el enunciado.
Caso 1 · La secuencia ordenada degenera el BST
Partiendo de un árbol VACÍO y en modo BST (sin rebalanceo), se insertan por este orden: 10, 20, 30, 40, 50, 60, 70. ¿Cuál es la altura final del árbol? La altura se cuenta en nodos: una hoja mide 1.
Inserción, borrado y rotaciones de auto-balanceado
BST vs AVL — Comparativa
Característica
BST simple
AVL
Balanceo
No (peor caso: lista)
Auto-balanceado tras cada operación
Altura en el peor caso
O(n)
O(log n) — siempre
Búsqueda
O(log n) promedio, O(n) peor caso
O(log n) garantizado
Inserción
O(log n) promedio
O(log n) + 1 o 2 rotaciones
Borrado
O(log n) promedio
O(log n) + posibles rotaciones en cascada
Memoria por nodo
Valor + 2 punteros
Valor + 2 punteros + altura (o factor balance)
Cuándo usarlo
Datos aleatorios, simplicidad
Lecturas frecuentes, datos ordenados
Casos de Uso Reales
📚Índices de bases de datos
Las bases de datos relacionales (PostgreSQL, MySQL, SQLite) usan árboles equilibrados —B-Tree y B+Tree, que no derivan del AVL sino que resuelven el mismo problema para bloques de disco— para indexar columnas y mantener búsquedas en O(log n) sobre millones de filas.
Tip: un BST simple sobre IDs autoincrementales se degenera a lista — por eso siempre se usan árboles equilibrados.
🗺️Sistemas de archivos
ext4, NTFS y Btrfs guardan los nombres de archivo de un directorio en árboles auto-balanceados para que listar y buscar archivos sea rápido aunque haya millones.
Tip: por eso un directorio con 10.000 archivos no es 1.000 veces más lento que uno con 10.
🧠Diccionarios y mapas ordenados
std::map en C++, TreeMap en Java o std::collections::BTreeMap en Rust usan árboles equilibrados internamente. Permiten búsqueda, inserción e iteración ordenada en O(log n).
Tip: si solo necesitas búsqueda y no orden, una tabla hash (HashMap) es más rápida en O(1) promedio.
🎮Tablas de routing y autocompletado
Routers de red, motores de autocompletado y editores de texto usan variantes de árboles balanceados para ofrecer respuestas en milisegundos sobre millones de entradas.
Tip: en autocompletado moderno se prefieren tries (árboles de prefijos), pero la idea de balanceo es la misma.
Preguntas Frecuentes
¿Por qué un BST simple puede degenerarse?
Si insertas valores ya ordenados (1, 2, 3, 4, 5...), cada nuevo nodo se va siempre a la derecha. El árbol acaba siendo una lista enlazada con altura n y búsqueda O(n). Pruébalo con el ejemplo “Inserción ordenada” en modo BST y compara con AVL.
Conclusión: los datos reales rara vez son aleatorios, así que en producción casi nunca se usa BST simple.
¿Qué es el factor de balance?
Para cada nodo: factor = altura(subárbol izquierdo) − altura(subárbol derecho). En un AVL siempre debe estar entre −1 y +1. Si llega a ±2, hay desbalanceo y se aplica una rotación.
En el simulador verás el número junto a cada nodo (en modo AVL). +1 = ligeramente cargado a la izquierda.
¿Cuándo se hace una rotación doble (LR o RL)?
Cuando el desbalanceo está “en zig-zag”. Por ejemplo: insertas 3, después 1, después 2. El subárbol izquierdo de 3 está cargado a la derecha, así que primero se rota izquierda en el hijo y después derecha en el nodo desbalanceado. Es lo que llamamos LR.
Regla mnemotécnica: las rotaciones dobles tienen dos letras (LR, RL) y siempre rotan primero en el hijo y después en el padre.
¿Diferencia entre AVL y árboles Red-Black?
Ambos están auto-balanceados. AVL es más estricto (factor balance entre −1 y +1): búsquedas más rápidas pero más rotaciones en inserciones/borrados. Red-Black permite algo más de desbalanceo: menos rotaciones, ideal cuando hay muchas escrituras.
Java TreeMap, C++ std::map y el kernel de Linux usan Red-Black, no AVL.
¿Por qué el borrado en AVL es más complejo?
Tras eliminar un nodo, el desbalanceo puede propagarse hacia arriba. Hay que recalcular factores de balance subiendo por el camino y aplicar rotaciones en cada nodo desbalanceado, no solo en el primero. Esto puede generar varias rotaciones en cadena.
Pruébalo en modo AVL: pega en «Insertar varios» 80, 50, 110, 30, 70, 100, 120, 20, 40, 60, 90, 10 (un árbol de Fibonacci, el AVL con menos nodos para su altura; entra sin ninguna rotación) y elimina el 120. Se encadenan dos rotaciones: una LL en el 110 y, al subir, otra LL en la raíz 80.
¿Qué recorrido devuelve los valores en orden creciente?
El recorrido inorden (izquierda → nodo → derecha). Es la propiedad clave de un BST: al recorrerlo en inorden, los valores salen ordenados de menor a mayor.
Si inviertes hijos izquierdo y derecho en el recorrido, obtienes orden decreciente.
Cómo Insertar a Mano en AVL — Paso a Paso
1
Inserta como en un BST normal
Compara el valor nuevo con el nodo actual. Si es menor, baja a la izquierda; si es mayor, baja a la derecha. Cuando llegues a una posición vacía, crea ahí el nuevo nodo.
2
Sube actualizando la altura de cada antecesor
Mientras vuelves recursivamente hacia la raíz, recalcula altura(nodo) = 1 + máx(altura(izq), altura(der)) en cada nodo del camino.
3
Comprueba el factor de balance
Calcula FB = altura(izq) − altura(der). Si está entre −1 y +1, todo bien: continúa subiendo. Si es +2 o −2, ese nodo está desbalanceado y hay que rotar.
4
Identifica el caso (LL, RR, LR o RL) y rota
FB = +2 y el valor entró en el subárbol izquierdo del hijo izquierdo → LL (rotación derecha). FB = −2 y entró en el derecho del derecho → RR (rotación izquierda). Si entró en zig-zag, aplica rotación doble (LR o RL).
5
Devuelve la nueva raíz del subárbol
Tras una rotación, el nodo que estaba arriba ya no es la raíz del subárbol; lo es el que ocupa su sitio. Asegúrate de que el padre apunte al nuevo nodo, no al antiguo.
Mejores Prácticas
🎯Compara siempre BST vs AVL con el mismo input
Carga un mismo preset primero en BST y después en AVL. Verás de un vistazo cómo las rotaciones aplanan el árbol y reducen su altura.
📐Almacena la altura, no el factor de balance
Es más fácil de actualizar y permite calcular el factor en O(1). El factor se deriva restando la altura de los hijos.
🔄Implementa rotaciones como funciones puras
rotarDerecha(y) y rotarIzquierda(x) deben recibir un nodo y devolver la nueva raíz. No modifiques el padre dentro de la función: que el llamador asigne el resultado.
🧪Prueba con secuencias adversariales
1, 2, 3, 4, 5... y 10, 9, 8, 7... son los casos peor para BST. Si tu AVL los maneja bien, las rotaciones están correctas.
🚦Usa recursión con cuidado en árboles grandes
Para árboles de millones de nodos, la recursión puede agotar la pila. Considera versiones iterativas con tu propia pila explícita.
📊Si necesitas O(1) sin orden, usa hash
Los AVL son ideales cuando necesitas iteración ordenada o búsqueda por rangos. Si solo importa “está o no está”, una tabla hash es más rápida.
⚠️Errores frecuentes al implementar AVL
Olvidar actualizar la altura del nodo antes de calcular el factor de balance.
Asignar el resultado de la rotación a la variable equivocada (no devolver la nueva raíz).
Confundir LR con RL: la rotación doble se nombra por la dirección de la inserción, no de las rotaciones.
No rebalancear durante el borrado: solo se rebalancea durante la inserción (esto es incorrecto).
Permitir duplicados sin decidir si van a izquierda o derecha (causa árboles inconsistentes).
Comparar valores con == en lenguajes con tipos mixtos (siempre normalizar a número).