Estructuras de datos | Árboles de búsqueda binarios equilibrados

El tiempo de ejecución del peor de los casos para buscar un elemento en un árbol de búsqueda binario equilibrado con n2^n elementos es

(A) $\Theta(n log n)$
(B) $\Theta (n2^n)$
(C) $\Theta (n)$
(D) $\Theta (log n)$

(A) A
(B) B
(C) C
(D) D

Respuesta: (C)
Explicación: El tiempo necesario para buscar un elemento es $\Theta (h)$ donde h es la altura del árbol de búsqueda binaria (BST). El crecimiento de la altura de un BST equilibrado es logertímico en términos de número de Nodes. Entonces, el peor momento para buscar un elemento sería $\Theta (Log(n*2^n))$ cuál es $\Theta (Log(n) + Log(2^n))$ Cuál es $\Theta (Log(n) + n)$ cuál se puede escribir como $\Theta (n)$ .
Cuestionario de esta pregunta