Visualizador de árboles binarios de búsqueda
Mira exactamente cómo cambia un árbol binario de búsqueda al insertar, eliminar y buscar. Cambia entre un BST simple, un árbol AVL autoequilibrado y un árbol rojo-negro, observa cómo se animan paso a paso cada comparación, rotación y recoloreado, y recorre el árbol en inorden, preorden, postorden o por niveles.
Última actualización:
El árbol está vacío. Inserta un valor o genera un árbol aleatorio.
Estadísticas del árbol
Resultado del recorrido
Registro de pasos
Insertar una lista de valores
Números enteros de -999 a 9999, separados por comas o espacios. Los duplicados se omiten. Hasta 63 nodos. Insertar 10, 20, 30… en orden muestra por qué los BST simples necesitan equilibrarse.
Cómo usar Visualizador de árboles binarios de búsqueda
- Elige un tipo de árbol: árbol binario de búsqueda, árbol AVL o árbol rojo-negro. Tus valores se reconstruyen en la nueva estructura.
- Escribe un número entero y pulsa Insertar, Eliminar o Buscar. Cada comparación se resalta y se explica debajo del árbol.
- Observa el reequilibrio: los árboles AVL muestran los factores de equilibrio y rotan cuando uno llega a ±2; los árboles rojo-negro recolorean y rotan para mantener sus reglas de color.
- Pulsa un botón de recorrido para visitar los nodos en inorden, preorden, postorden o por niveles y copia la secuencia.
- Abre Insertar una lista de valores para construir un árbol con muchos números a la vez y luego descárgalo como imagen SVG.
Complejidad temporal de los árboles binarios de búsqueda
| Árbol | Buscar | Insertar | Eliminar | Altura en el peor caso | Rotaciones por inserción |
|---|---|---|---|---|---|
| Árbol binario de búsqueda (no equilibrado) | O(h), O(n) en el peor caso | O(h), O(n) en el peor caso | O(h), O(n) en el peor caso | n − 1 | 0 |
| Árbol AVL | O(log n) | O(log n) | O(log n) | aprox. 1.44·log₂(n + 2) | Como máximo 1 rotación simple o doble |
| Árbol rojo-negro | O(log n) | O(log n) | O(log n) | 2·log₂(n + 1) | Como máximo 2 |
h es la altura del árbol y n el número de claves. Un árbol perfectamente equilibrado con n claves tiene una altura de ⌈log₂(n + 1)⌉ − 1 aristas; el panel de estadísticas la muestra como "Mejor posible" para que puedas compararla con el árbol actual.
Los cuatro casos de rotación AVL
| Caso | Cuándo ocurre | Corrección | Prueba a insertar |
|---|---|---|---|
| Izquierda-Izquierda | El nodo está en +2 y su hijo izquierdo en 0 o +1 | Rotación simple a la derecha en el nodo | 30, 20, 10 |
| Derecha-Derecha | El nodo está en −2 y su hijo derecho en 0 o −1 | Rotación simple a la izquierda en el nodo | 10, 20, 30 |
| Izquierda-Derecha | El nodo está en +2 y su hijo izquierdo en −1 | Rotación a la izquierda en el hijo y luego a la derecha en el nodo | 30, 10, 20 |
| Derecha-Izquierda | El nodo está en −2 y su hijo derecho en +1 | Rotación a la derecha en el hijo y luego a la izquierda en el nodo | 10, 30, 20 |
Consejos para aprender con el visualizador
- Observa la degeneración: borra el árbol, elige Árbol binario de búsqueda e inserta 10, 20, 30, 40, 50 en orden. Luego cambia a AVL para ver las mismas claves reconstruidas con altura 2 en lugar de 4.
- Recoloreado rojo-negro: inserta 10, 20, 30, 15, 25, 5 en un árbol rojo-negro vacío para ver una rotación seguida de casos de recoloreado en los que el tío es rojo.
- Casos de eliminación: elimina una hoja, un nodo con un hijo y un nodo con dos hijos para comparar los tres casos de eliminación en un BST.
- Comprueba tus deberes: escribe las claves de un ejercicio en Insertar una lista de valores y compara cada recorrido con tu propia respuesta.
Preguntas frecuentes
¿Qué es un árbol binario de búsqueda?
Un árbol binario de búsqueda (BST) es un árbol binario en el que la clave de cada nodo es mayor que todas las claves de su subárbol izquierdo y menor que todas las de su subárbol derecho. Ese orden permite buscar, insertar o eliminar una clave siguiendo un único camino desde la raíz, así que cada operación tarda un tiempo proporcional a la altura del árbol.
¿Por qué hay que equilibrar los BST?
Si las claves llegan ordenadas, un BST simple degenera en una lista enlazada de altura n − 1 y la búsqueda pasa a ser O(n). Los árboles autoequilibrados como los AVL y los rojo-negro se reestructuran con rotaciones para que la altura se mantenga en O(log n), de modo que la búsqueda, la inserción y la eliminación siguen siendo rápidas en el peor caso.
¿Cuál es la diferencia entre un árbol AVL y uno rojo-negro?
Un árbol AVL mantiene las alturas de los dos subárboles de cada nodo con una diferencia máxima de 1, así que está más equilibrado (altura como máximo de unos 1.44·log₂ n) y las búsquedas son algo más rápidas. Un árbol rojo-negro usa colores en los nodos y permite una altura de hasta 2·log₂(n + 1), pero necesita menos rotaciones al insertar y eliminar. Muchas bibliotecas estándar usan árboles rojo-negro para mapas y conjuntos ordenados.
¿Cómo se elimina un nodo con dos hijos?
El nodo se sustituye por su sucesor en inorden, la clave más pequeña de su subárbol derecho. El sucesor no tiene hijo izquierdo, así que se puede desenlazar fácilmente y mover a la posición del nodo eliminado. Así se mantiene el orden del BST. (Usar el predecesor en inorden, la clave más grande del subárbol izquierdo, funciona igual de bien.)
¿Qué significa el factor de equilibrio?
En un árbol AVL, el factor de equilibrio de un nodo es altura(subárbol izquierdo) − altura(subárbol derecho). Los nodos AVL válidos tienen un factor de equilibrio de −1, 0 o +1. Cuando una inserción o eliminación lo deja en +2 o −2, el árbol hace una rotación simple o doble en ese nodo para recuperar el equilibrio.
¿Qué recorrido da las claves ordenadas?
El recorrido en inorden (subárbol izquierdo, nodo, subárbol derecho) visita las claves de un árbol binario de búsqueda en orden ascendente. El preorden (primero el nodo) es útil para copiar o serializar un árbol, el postorden (el nodo al final) para eliminarlo o evaluar árboles de expresiones, y el recorrido por niveles visita el árbol fila a fila con una cola.
¿Cuáles son las reglas de un árbol rojo-negro?
Cada nodo es rojo o negro, la raíz es negra, un nodo rojo nunca tiene un hijo rojo y todo camino desde un nodo hasta una hoja vacía (nil) pasa por el mismo número de nodos negros, llamado altura negra. Las hojas vacías cuentan como negras. Estas reglas garantizan que el camino más largo mide como máximo el doble que el más corto.
¿Se prueban todas las herramientas de FreeToolCabin para comprobar su calidad y precisión?
Sí. Cada herramienta del sitio pasa pruebas automáticas en navegadores reales para comprobar que el resultado es correcto y que no hay errores. Si encuentras un fallo o tienes una sugerencia, escríbenos a [email protected] y lo revisaremos.