¿Qué significa el pequeño número de factor de equilibrio bajo cada nodo?

Es el factor de equilibrio del nodo: la altura de su subárbol izquierdo menos la altura de su subárbol derecho. Un árbol AVL mantiene este valor en menos uno, cero o más uno para cada nodo; una magnitud mayor indica un desequilibrio que una rotación necesitaría corregir.

Inicio▸Algoritmos e IA▸Árbol Binario de Búsqueda — Insertar, Buscar y Equilibrar

🌳 Árbol Binario de Búsqueda — Insertar, Buscar y Equilibrar

Construye, busca y recorre un árbol binario de búsqueda paso a paso. Inserta nodos, encuentra elementos y compara un ABB con el autoequilibrado AVL. Complejidad O(log n) frente a O(n).

Algoritmos e IA3DFácil60 FPS

Acerca de Árbol Binario de Búsqueda

Un árbol binario de búsqueda (ABB) es una estructura de datos fundamental en informática donde cada nodo almacena un valor y tiene como máximo dos hijos: todos los valores del subárbol izquierdo son menores que el nodo, y todos los del subárbol derecho son mayores. Esta propiedad de orden significa que buscar, insertar y eliminar elementos toman todos O(log n) tiempo en promedio — la misma eficiencia asintótica que la búsqueda binaria en un arreglo ordenado, pero con la flexibilidad de una estructura enlazada dinámicamente. Los ABB son la base de los índices de bases de datos, las tablas de símbolos en los compiladores y el contenedor std::map de C++.

Este simulador te permite insertar, buscar y eliminar valores, ver recorridos en orden/preorden/postorden con animación paso a paso, y aplicar el equilibrado AVL para convertir un árbol degenerado (tipo lista enlazada) en uno equilibrado en altura. El panel de estadísticas muestra el número de nodos, la altura del árbol y si el árbol cumple el criterio de equilibrio AVL (|h_L − h_R| ≤ 1 en cada nodo).

Preguntas Frecuentes

¿Cuál es la complejidad temporal de la búsqueda en un ABB?

En un ABB equilibrado, la búsqueda toma O(log n) tiempo porque cada comparación reduce a la mitad los candidatos restantes, igual que la búsqueda binaria. En el peor caso — cuando los valores se insertan en orden ya ordenado, produciendo una cadena lineal — el árbol degenera y la búsqueda cae a O(n). Por esto se inventaron variantes autoequilibradas como los árboles AVL y los árboles rojo-negro.

¿Qué es un árbol AVL y cómo funciona el equilibrado?

Un árbol AVL (llamado así por Adelson-Velsky y Landis, 1962) es un ABB autoequilibrado que mantiene el invariante de que la diferencia de altura entre los subárboles izquierdo y derecho (el factor de equilibrio) es como máximo 1 en cada nodo. Cuando una inserción o eliminación viola esto, una rotación — ya sea simple (izquierda o derecha) o doble (izquierda-derecha o derecha-izquierda) — restaura el equilibrio en tiempo O(log n) sin cambiar la propiedad de orden del ABB.

¿Qué produce el recorrido en orden?

El recorrido en orden (izquierda → raíz → derecha) visita cada nodo en orden ascendente. Esta es una de las propiedades más útiles de un ABB: un único recorrido O(n) produce una lista ordenada. En cambio, preorden (raíz → izquierda → derecha) es útil para serializar un árbol, y postorden (izquierda → derecha → raíz) se usa cuando es necesario procesar los hijos antes que los padres, como al eliminar un árbol completo.

¿Qué es el factor de equilibrio y cómo se calcula?

El factor de equilibrio (bf) de un nodo se define como la altura de su subárbol izquierdo menos la altura de su subárbol derecho. En un árbol AVL, bf debe ser −1, 0 o +1 para cada nodo. El simulador muestra "bf:x" debajo de cada nodo. Un nodo con bf = +2 tiene un desequilibrio hacia la izquierda y requiere una rotación derecha (o una rotación doble izquierda-derecha si el hijo está desequilibrado hacia la derecha).

¿Cuándo se convierte un ABB en un árbol degenerado (peor caso)?

Si los elementos se insertan en orden estrictamente ascendente o descendente — por ejemplo, 1, 2, 3, 4, 5 — el ABB se convierte en una cadena derecha (o izquierda) con altura n−1, idéntica en estructura a una lista enlazada. Cada búsqueda entonces requiere visitar los n nodos, dando O(n) tiempo. Prueba a insertar valores ordenados en este simulador y compara la altura con una inserción de los mismos valores en orden aleatorio.

¿Cómo se implementa la eliminación en un ABB?

Eliminar un nodo en un ABB tiene tres casos: (1) el nodo es una hoja — simplemente se elimina; (2) el nodo tiene un hijo — se empalma el hijo en su lugar; (3) el nodo tiene dos hijos — se reemplaza el valor del nodo con el valor más pequeño de su subárbol derecho (el sucesor en orden), y luego se elimina ese nodo sucesor, que está garantizado que caerá en el caso 1 o 2. Este simulador implementa los tres casos.

¿Cuáles son las aplicaciones reales de los ABB?

Los sistemas de gestión de bases de datos usan árboles B (una generalización de los ABB con múltiples claves por nodo) para sus índices basados en disco, permitiendo búsquedas de filas O(log n) en millones de registros. El núcleo de Linux usa árboles rojo-negro (otro ABB autoequilibrado) para programar tareas y gestionar áreas de memoria virtual. std::map y std::set de C++ se implementan típicamente como árboles rojo-negro, garantizando operaciones O(log n) en el peor caso.

¿Cuál es la diferencia entre un ABB y un montículo?

Ambas son estructuras de datos basadas en árboles pero con propiedades de orden diferentes. Un ABB impone el orden hijo-izquierdo-menor-que-padre en todo el árbol, haciendo eficiente la búsqueda. Un montículo solo impone la propiedad del montículo entre un padre y sus hijos inmediatos (montículo máximo: padre ≥ hijos), haciendo que encontrar el mínimo o máximo sea O(1) pero la búsqueda arbitraria O(n). Los montículos son óptimos para colas de prioridad; los ABB son óptimos para diccionarios ordenados.

¿Cómo se relaciona la altura de un ABB equilibrado con el número de nodos?

Para un ABB perfectamente equilibrado con n nodos, la altura h = ⌊log₂ n⌋. Un árbol AVL garantiza una altura de como máximo 1,44 × log₂(n+2), que sigue siendo O(log n). Un árbol rojo-negro garantiza una altura de como máximo 2 × log₂(n+1). Estos límites son lo que hace que todas las operaciones sean O(log n) incluso en órdenes de inserción adversarios.

¿Puede un ABB almacenar valores duplicados?

Las definiciones estándar de ABB excluyen los duplicados, pero las implementaciones reales los manejan de una de tres maneras: (1) ignorar los duplicados (como en este simulador); (2) permitir duplicados en el subárbol derecho (val ≤ padre va a la derecha); (3) almacenar un contador junto a cada valor de nodo. La elección afecta la lógica de eliminación y la semántica de recorrido, por lo que normalmente se fija en tiempo de diseño según los requisitos de la aplicación.

Acerca de esta simulación

Esta simulación construye un árbol binario de búsqueda en vivo en tu navegador, para que puedas insertar, buscar y eliminar valores enteros y ver cada comparación resaltada paso a paso. Un ABB simple obtiene su forma únicamente del orden de inserción, por lo que puede degradarse en un árbol lento en forma de cadena; el botón Equilibrio AVL reescribe los mismos valores en un árbol equilibrado en altura usando rotaciones, para que puedas comparar el comportamiento de búsqueda antes y después. Los tres botones de recorrido revelan los órdenes de visita clásicos en orden, preorden y postorden, y el panel de estadísticas muestra el número de nodos, la altura del árbol y si la condición de equilibrio AVL se cumple actualmente.

🔬 Qué muestra

Cada valor insertado se convierte en un nodo colocado a la izquierda o derecha de su padre siguiendo la regla del ABB: los valores más pequeños van a la izquierda, los más grandes a la derecha. La búsqueda resalta el camino de comparación en amarillo, volviéndose verde cuando se encuentra el valor o rojo cuando está ausente, para que puedas ver cuántas comparaciones necesita realmente una búsqueda — O(log n) en promedio para un árbol equilibrado, pero O(n) para uno muy sesgado.

🎮 Cómo usarlo

Introduce un valor y pulsa Insertar, Buscar o Eliminar; usa Aleatorio 10 para llenar el árbol rápidamente, o Limpiar para empezar de nuevo. Pulsa Equilibrio AVL para remodelar los valores actuales en un árbol equilibrado mediante rotaciones, y luego compara la altura mostrada antes y después. Los botones En orden, Preorden y Postorden animan cada orden de recorrido en el cuadro de resultados, mientras que el panel de estadísticas rastrea el número de nodos, la altura, el estado de equilibrio y la última operación realizada.

💡 ¿Sabías Que…?

El recorrido en orden de cualquier árbol binario de búsqueda siempre visita los valores en orden estrictamente ascendente — esta única propiedad es la razón por la que los ABB mantienen los datos ordenados de forma eficiente para buscar, insertar y eliminar sin necesitar nunca un paso de ordenamiento separado. Los descendientes prácticos del árbol AVL modelado aquí, como los árboles rojo-negro, son la base del std::map de C++ y el TreeMap de Java.

Preguntas frecuentes

¿Qué ocurre realmente cuando inserto un valor?

El simulador compara el nuevo valor con la raíz: si es menor va a la izquierda, si es mayor va a la derecha, repitiendo recursivamente hasta llegar a un espacio vacío, donde se crea un nuevo nodo. Esto preserva la propiedad de orden del ABB — cada descendiente izquierdo es menor y cada descendiente derecho es mayor que su ancestro — sin ningún reequilibrado.

¿Qué hace el botón de Equilibrio AVL al árbol?

Lee todos los valores mediante un recorrido en orden, vacía el árbol y luego reinserta esos mismos valores usando inserción de estilo AVL, que aplica rotaciones izquierda y derecha cada vez que las alturas de los subárboles izquierdo y derecho de un nodo difieren en más de uno. Los valores no cambian, pero la forma resultante está equilibrada en altura, típicamente reduciendo considerablemente la altura del árbol.

¿Cuál es la diferencia entre los tres botones de recorrido?

En orden visita el subárbol izquierdo, luego el nodo, luego el subárbol derecho, produciendo valores en orden ascendente. Preorden visita primero el nodo, luego la izquierda, luego la derecha, lo cual es útil para copiar o serializar un árbol. Postorden visita ambos subárboles antes que el propio nodo, el orden necesario al eliminar un árbol completo de forma segura.

¿Por qué la búsqueda puede tardar O(n) en lugar de O(log n)?

Si los valores se insertan en un orden ya ordenado, el ABB simple crece hasta convertirse en una cadena unilateral, no muy diferente de una lista enlazada, por lo que una búsqueda puede tener que revisar cada nodo. Prueba a insertar números en orden ascendente, anota la altura mostrada, y luego pulsa Equilibrio AVL para ver cómo la altura y el costo de búsqueda en el peor caso se reducen de nuevo.

¿Qué significa el pequeño número "bf" bajo cada nodo?

Es el factor de equilibrio del nodo: la altura de su subárbol izquierdo menos la altura de su subárbol derecho. Un árbol AVL mantiene este valor en −1, 0 o +1 para cada nodo; una magnitud mayor indica un desequilibrio que una rotación necesitaría corregir.

⚙ Bajo el capó

Operaciones animadas de ABB: insertar, buscar, eliminar y recorrido en orden. Cambia al modo AVL para ver las rotaciones de equilibrado automático. Muestra la complejidad Big-O y la altura del árbol en vivo.

árbol binario de búsquedaABBAVLrotaciónrecorrido de árbolBig-O

3D · renderizador Three.js / WebGL · 60 FPS objetivo · funciona totalmente del lado del cliente, sin instalación