PUERTA | Puerta TI 2008 | Pregunta 12

¿Cual de los siguientes es verdadero?

(A) El costo de buscar un árbol AVL es θ (log n) pero el de un árbol binario de búsqueda es O(n)
(B) El costo de buscar un árbol AVL es θ (log n) pero el de un binario completo el árbol es θ (n log n)
(C) El costo de buscar un árbol binario de búsqueda es O (log n ) pero el de un árbol AVL es θ(n)
(D) El costo de buscar un árbol AVL es θ (n log n) pero el de un árbol de búsqueda binaria es O(n)

Respuesta: (A)
Explicación: el árbol AVL es un árbol equilibrado.
Complejidad de tiempo de búsqueda del árbol AVL = θ(logn)

Pero un árbol de búsqueda binario, puede ser un árbol sesgado, por lo que en el peor de los casos BST tiempo de búsqueda = θ(n)
Cuestionario de esta pregunta