PUERTA | PUERTA CS 2012 | Pregunta 5 – Part 3

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) 

(B) 

(C) 

(D)  

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

Respuesta: (C)
Explicación:

-> El tiempo de búsqueda en un árbol de búsqueda binario depende de la forma del árbol, es decir, del orden en que se insertaron sus Nodes. Un caso patológico: Los n Nodes fueron insertados por orden creciente de las claves, dando algo así como una lista lineal (pero con un peor consumo de espacio), con O(n) tiempo de búsqueda (en el caso de árbol sesgado).

-> Un árbol equilibrado es un árbol en el que cada hoja está «no más de una cierta distancia» de la raíz que cualquier otra hoja. Entonces, en un árbol equilibrado, la altura del árbol está equilibrada para hacer que la distancia entre la raíz y los Nodes de las hojas sea una bajo posible. En un árbol equilibrado, la altura del árbol es log ₂ (n).

-> Entonces, si un árbol de búsqueda binaria balanceada contiene n2n elementos, entonces la complejidad del tiempo para buscar un elemento:

Complejidad de tiempo = log(n2 ⁿ ) = log (n) + log(2 ⁿ )
= log (n) +n = O(n)

Entonces la respuesta es C.

Consulte  https://www.geeksforgeeks.org/data-structures-and-algorithms-set-28/

Esta solución es aportada por Nirmal Bharadwaj
Cuestionario de esta pregunta