Árboles binarios de búsqueda
Mapa conceptual
Búsqueda y la idea de mitad a mitad
Para buscar un valor, empiezas en la raíz y comparas: si el valor es menor, vas a la izquierda; si mayor, a la derecha. Cada paso descarta todo el subárbol opuesto. En un árbol de altura h, el coste es O(h); y si está balanceado, h = log n, así que O(log n).
Buscar 15 en un BST balanceado
- — Raíz = 8
- — Nodo = 12
- — Nodo = 16
- — Nodo = 15
El peligro: desbalancearse
Si insertas datos ya ordenados (1, 2, 3, 4, …), cada nuevo valor va siempre a la derecha y el árbol se convierte en una LISTA enlazada de altura n. Entonces O(h) pasa a ser O(n): el BST pierde toda su ventaja. De ahí que existan árboles AUTOEQUILIBRADOS (AVL, rojo-negro) que rotan nodos para mantener h ≈ log n.
| Operación | Árbol balanceado | Árbol degenerado (peor caso) |
|---|---|---|
| Buscar | O(log n) | O(n) |
| Insertar | O(log n) | O(n) |
| Mínimo / máximo | O(log n) | O(n) |
| Recorrido completo | O(n) | O(n) |
Los tres recorridos
- In-orden (izquierda, nodo, derecha): visita los valores ORDENADOS de menor a mayor. Es la prueba de fuego del BST.
- Pre-orden (nodo, izquierda, derecha): útil para serializar/copiar el árbol.
- Post-orden (izquierda, derecha, nodo): útil para borrar o evaluar expresiones.
[Coste de búsqueda: logarítmico (balanceado) vs lineal (degenerado)]
Esta actividad interactiva ('Grafico interactivo') requiere el motor completo de Lumbre. El contenido estatico se muestra arriba; para la experiencia interactiva, visita la version online de este objeto.
¿Qué recorrido de un BST visita sus claves en orden creciente?
Insertar siempre valores crecientes en un BST sin equilibrar mantiene la altura en O(log n).
Une cada operación/propiedad del BST con su coste o resultado (árbol balanceado).
Errores frecuentes
- Olvidar el caso de borrar un nodo con DOS hijos: se sustituye por el mínimo de la derecha (o máximo de la izquierda) para preservar la invariante.
- Asumir BST = rápido sin equilibrar: el rendimiento depende de la ALTURA, que puede degenerar.
- Confundir «árbol binario» (cualquiera con ≤2 hijos) con «BST» (con la invariante de orden).
Ejemplo resuelto
- Inserta 8, 3, 10, 1, 6 en un BST vacío.
- 8 es la raíz. 3 menor → izquierda. 10 mayor → derecha.
- 1 menor que 8, a la izquierda; menor que 3, izquierda de 3.
- 6 menor que 8 (izquierda), mayor que 3 (derecha de 3).
- Árbol con raíz 8, subárbol izquierdo 3→1,6→…, derecho 10. Un in-orden daría 1,3,6,8,10.
Los árboles ordenados son lo que usas cuando necesitas a la vez búsqueda rápida Y mantener el orden: índices de bases de datos (B-trees, generalización de esta idea), «¿cuántas claves hay entre a y b?», o el siguiente valor después de uno dado. El hash no puede con eso; el BST, sí.
El BST en ocho ideas
Árboles (repaso formal)
BST, sus operaciones, recorridos y equilibrio con ejemplos.
Una tabla hash da búsqueda O(1) pero no sabe decir «dame todas las claves entre 100 y 200» ni «la clave siguiente». Explica por qué un BST sí puede y en qué situación elegirías el BST (log n) a pesar de ser «más lento» que el hash (O(1)).
VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.