Los BST tienen una complejidad de tiempo promedio de ϴ (log (n)) para insertar, eliminar y encontrar, pero en el peor de los casos, todas estas operaciones tienen una complejidad de tiempo de O (n).
No se garantiza que los BST sean equilibrados, por lo que un BST podría ser el siguiente:
- Suponiendo que todos estos algoritmos resuelven el mismo tipo de problema, ¿cuál se recomienda? ¿Y por qué?
- ¿Puedo aprender algoritmos en mis vacaciones de verano si doy 8-10 horas cada día?
- ¿Quién sabe qué hay detrás de la API de Google Nearby Search? ¿Qué algoritmo usan? ¿Cómo encuentra Google una estación de servicio cercana?
- ¿Cuál es el mejor sitio en línea para aprender estructuras de datos y algoritmos?
- ¿Por qué es difícil estimar el tiempo de ejecución exacto de un algoritmo?
En la primera imagen, insertar un nodo con un valor mayor que 5 requeriría que el BST atraviese cada nodo hasta finalmente insertar el nuevo nodo mayor como el hijo derecho del nodo que contiene 5. Insertar un nodo con un valor menor que 1 requeriría un proceso similar en la segunda imagen. En ambos casos, cada nodo tenía que iterarse y, por lo tanto, la operación estaría en una escala de O (n).
La complejidad del tiempo se puede mejorar para garantizar O (log (n)); sin embargo, esto requeriría que el usuario inserte y elimine nodos con cuidado o que se implementen inserciones y eliminaciones más costosas para mantener un BST de equilibrio automático.
