Dados dos árboles de búsqueda binarios equilibrados, B1 con n elementos y B2 con m elementos, ¿cuál es la complejidad temporal del algoritmo más conocido para fusionar estos árboles para formar otro árbol binario equilibrado que contenga m+n elementos?
(A) O(m+n)
(B) O(mlogn)
(C) O(nlogm)
(D) O(m 2 + n 2 )
Respuesta: (A)
Explicación:
O(m+n) ya que podemos realizar primero en orden en ambos árboles y almacenarlos en dos arrays separadas. Ahora tenemos dos secuencias ordenadas y podemos fusionarlas en O(m+n) usando el algoritmo de fusión estándar y en la array ordenada final podemos usar la búsqueda binaria para crear el árbol usando Recursión. Agregando recursivamente el elemento medio en la raíz y repitiendo el mismo proceso para los subarreglos izquierdo y derecho.
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