Árboles binarios de búsqueda
Mapa conceptual
- Estructuras de Datos
- Lineales
- Arrays
- Listas enlazadas
- Pilas y Colas
- No lineales
- Arboles BST
- Heaps
- Grafos
- Hash
- Funcion hash
- Colisiones
- Rehashing
- Algoritmos
- Ordenamiento
- Busqueda binaria
- BFS DFS
- Optimizacion
- Big-O
- Dinamica
- Voracidad
- Lineales
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¿8 15? sí, a la derecha
Descartamos toda la izquierda (los menores que 8).
- Nodo = 12¿12 15? sí, a la derecha
Otra mitad eliminada.
- Nodo = 16¿16 15? sí, a la izquierda
Casi lo tenemos.
- Nodo = 15¡encontrado!
Tres comparaciones para un árbol de 7 nodos: ≈ log₂(7).
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.
f(x) = log(x)/log(2) · f(x) = x · f(x) = 1
¿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
Toca una tarjeta para ver la respuesta.
Á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)).
Tu texto se guarda sólo en este dispositivo.
VisuAlgoVisualizaciones animadas de estructuras de datos y algoritmos.
Comentarios
Inicia sesión para comentar.
Todavía no hay comentarios. Sé la primera persona en opinar.