¿Qué es un árbol binario de búsqueda (BST) y cómo funciona?

Un BST (Binary Search Tree) es una estructura de datos en la que cada nodo tiene como máximo dos hijos. La regla fundamental es que todos los nodos del subárbol izquierdo tienen valores menores que el nodo raíz, y todos los del subárbol derecho tienen valores mayores. Esto permite buscar, insertar y eliminar elementos en O(log n) de media, ya que en cada paso se descarta la mitad del árbol.

¿Cuál es la diferencia entre un BST y un árbol AVL?

Un BST estándar puede degenerar en una lista enlazada si se insertan elementos en orden, lo que convierte las operaciones en O(n). El árbol AVL (Adelson-Velsky y Landis, 1962) es un BST auto-balanceado que mantiene un factor de balance de -1, 0 o +1 en cada nodo. Cuando una inserción o borrado desequilibra el árbol, realiza rotaciones (simple o doble) para restaurar el equilibrio, garantizando O(log n) siempre.

¿Qué son las rotaciones LL, RR, LR y RL en un árbol AVL?

Las rotaciones reequilibran el árbol tras inserciones o borrados. La rotación LL (simple derecha) corrige un desequilibrio izquierdo-izquierdo; la RR (simple izquierda) corrige uno derecho-derecho. Las rotaciones dobles LR y RL se aplican cuando el desequilibrio ocurre en la dirección opuesta al hijo problemático: LR combina una rotación izquierda sobre el hijo y luego una derecha sobre el nodo desbalanceado; RL hace lo inverso.

¿Qué recorridos se pueden hacer sobre un árbol binario?

Los cuatro recorridos clásicos son: inorden (izquierdo → raíz → derecho), que devuelve los elementos ordenados en un BST; preorden (raíz → izquierdo → derecho), útil para serializar el árbol; postorden (izquierdo → derecho → raíz), usado para liberar memoria o evaluar expresiones; y por niveles (BFS), que visita nodo a nodo de arriba a abajo. El simulador permite ejecutar los cuatro de forma animada.

¿Para qué asignaturas es útil este simulador de árboles?

Es especialmente útil para las asignaturas de Estructuras de Datos y Algoritmia de grados en Informática, Ingeniería del Software, Matemáticas e Ingeniería de Telecomunicaciones. También lo usan preparadores de entrevistas técnicas en empresas de software, ya que los árboles BST y AVL son uno de los temas más habituales en pruebas de código de selección. El simulador visual ayuda a memorizar el comportamiento de las rotaciones, que en papel resultan difíciles de seguir.

meskeIA

Simulador de Árboles BST y AVL

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.

Términos de UsoTérminos|Política de PrivacidadPrivacidad|Contacto

Tipo de árbol

Operaciones

Insertar nodo

Eliminar nodo

Buscar nodo

Insertar varios (separados por comas o espacios)

Ejemplos preconfigurados

Velocidad animación:600 ms

Visualización del árbol

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”.

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, derivado de AVL) 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: carga el preset balanceado y elimina valores; observa rotaciones en cascada.

¿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

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.

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.

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.

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).

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).

🔗Apps relacionadas

🌲Árbol B (B-Tree)Índices de bases de datos 🕸️Algoritmos de GrafosBFS, DFS, Dijkstra, A*🗂️Estructuras de DatosPilas, colas, árboles y hash 📊Algoritmos Ordenación7 algoritmos paso a paso

meskeIA

Cargando aplicación...

Preparando tu experiencia meskeIA

meskeIA

Simulador de Árboles BST y AVL

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.

Términos de UsoTérminos|Política de PrivacidadPrivacidad|Contacto

Tipo de árbol

Operaciones

Insertar nodo

Eliminar nodo

Buscar nodo

Insertar varios (separados por comas o espacios)

Ejemplos preconfigurados

Velocidad animación:600 ms

Visualización del árbol

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”.