Árboles binarios de búsqueda
Una sola regla: menores a la izquierda, mayores a la derecha.
Cada operación es una caminata hacia abajo por un camino.
El invariante lo hace todo
- Búsqueda / inserción / borrado: bajar comparando — O(altura)
- Cada comparación descarta un subárbol completo
- mínimo = camina a la izquierda · máximo = camina a la derecha · sucesor, rangos
- Recorrido in-order → salida ordenada
Mira a un BST tomar forma
Inserta 5,3,8,1,4,7,9 — cada valor baja (azul) hasta su lugar (verde).
La falla fatal: el balance
Entrada ordenada → árbol degenerado tipo lista ligada → O(n) por operación. 291× más lento con n=8000.
vs hash table
- BST: ordenado — mínimo, máximo, sucesor, rangos, iteración ordenada — O(log n)
- set/dict: pertenencia O(1) pero SIN orden
- Pagas el factor logarítmico para obtener un orden que la hash table no da a ninguna velocidad
Para llevar
Un contenedor ordenado en O(log n) — si se mantiene balanceado.
Desbalanceado, la entrada ordenada lo mata. Sigue: los árboles AVL lo mantienen balanceado.