¿Cuál es el tiempo de búsqueda en el peor caso de un BST sin balancear creado con entrada ordenada?
Opciones
- O(1)
- O(log n)
- O(n) (Opción correcta)
- O(n log n)
Respuesta
O(n)
Por qué
Insertar 1, 2, 3, 4, 5 en orden en un BST simple hace que cada clave nueva sea el hijo derecho de la anterior. El 'árbol' es en realidad una línea recta, como una linked list.
Buscar visita entonces todos los nodos: O(n).
Los árboles autobalanceados (AVL, red-black) se reorganizan para mantener una altura de cerca de log n, lo que garantiza O(log n).
Recuerda
Un BST sin balancear puede degradarse a O(n).