Se requiere una estructura de datos para almacenar un conjunto de enteros de modo que cada una de las siguientes operaciones se pueda realizar en tiempo O (log n), donde n es el número de elementos en el conjunto.
I. Supresión del elemento menor
II. Inserción de un elemento si aún no está presente en el conjunto
¿Cuál de las siguientes estructuras de datos se puede utilizar para este propósito?
(A) Se puede usar un montón, pero no un árbol de búsqueda binario balanceado
(B) Se puede usar un árbol de búsqueda binario balanceado, pero no un montón
(C) Se pueden usar tanto el árbol de búsqueda binario balanceado como el montón
(D) Ni el árbol de búsqueda balanceado ni heap puede ser utilizado
Respuesta: (B)
Explicación: Un árbol de búsqueda binaria de autoequilibrio que contiene n elementos permite la búsqueda, inserción y eliminación de un elemento en O (log n) en el peor de los casos. Dado que es un BST autoequilibrado, podemos encontrar fácilmente el elemento mínimo en el tiempo O (inicio de sesión), que siempre es el elemento más a la izquierda.
Dado que Heap es un árbol binario equilibrado (o un árbol binario casi completo), la complejidad de inserción para el montón es O (logn). Además, la complejidad para obtener el mínimo en un montón mínimo es O (logn) porque la eliminación del Node raíz hace que una llamada se acumule (después de eliminar el primer elemento de la array) para mantener la propiedad del árbol del montón. Pero un montón no se puede usar para el propósito anterior como dice la pregunta: inserte un elemento si aún no está presente. Para un montón, no podemos averiguar en O(logn) si un elemento está presente o no.
Entonces, la opción (B) es correcta.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA