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 (log n) tiempo, donde n es el número de elementos en el conjunto.
o Delection of the smallest element o Insertion of an element if it is not already present in the set
¿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 la búsqueda binaria balanceada no se puede usar ni un árbol ni un montón
Respuesta: (B)
Explicación: Un árbol de búsqueda binaria de equilibrio automático 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, podemos encontrar fácilmente el elemento mínimo en O (nlogn). Consulte nuestra publicación Encuentre el elemento mínimo en un árbol de búsqueda binaria para obtener más información.
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. Gracias al juego por proporcionar la solución 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