PUERTA | PUERTA-CS-2003 | Pregunta 63

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 árbol ni montón

Respuesta: (B)
Explicación:
Primero discutiremos sobre el montón y el bst balanceado y sus complejidades de tiempo para operaciones básicas como

inserción, eliminación, búsqueda.

Montón:-

Considerémoslo como un montón mínimo

1) Inserción: O (inicio de sesión)

2) Eliminar Min: O (logn) (Simplemente reemplace root con INT_MAX y heapify)

3) Hallar: O(n)

BST equilibrado:-

1) Inserción: O (inicio de sesión)

2) Eliminar Min: O (inicio de sesión)

3) Buscar: O (inicio de sesión)

Declaración 1:

1) La eliminación del elemento más pequeño se puede hacer en O (logn) en ambas estructuras de datos

Declaración 2:

1) Inserción de un elemento si aún no está presente en el conjunto

En el montón, podemos realizar esta operación en O (n) porque tenemos que realizar una búsqueda lineal aquí, mientras que en BST podemos realizar esto en O (logn)

Consulte la pregunta 4 de https://www.geeksforgeeks.org/data-structures-and-algorithms-set-3/

Esta solución es aportada por Anil Saikrishna Devarasetty
Cuestionario de esta pregunta