Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 8 del tema 4

No sería posible. Se puede demostrar por reducción al absurdo como sigue. Supongamos que existiese un algoritmo con esas características. Utilizándolo, podríamos mejorar el algoritmo de ordenación AVL Sort que vimos en los ejercicios 8 y 12 del tema 3, así:

void ordenar(vector<int> & v) {

   Multiconjunto multiconjunto(v); // A partir de v, construye en tiempo O(n) un
                                   // arbol AVL, o un arbol binario de busqueda,
                                   // utilizando internamente el algoritmo que
                                   // suponemos que existe

   v = multiconjunto.obtenerOrdenados(); // A partir del arbol, obtiene los datos
                                         // ordenados en tiempo O(n) realizando un
                                         // recorrido en inorden como vimos en el tema 3

}

De este modo habríamos resuelto el problema de ordenación en tiempo O(n + n) = O(n), cosa que sabemos que es imposible. Por tanto, a diferencia de lo que pasa con montículos binarios, no existe ningún algoritmo de construcción de un árbol AVL ni de un árbol binario de búsqueda en tiempo O(n).

Ejemplo de solución incorrecta

Es incorrecto decir que la razón por la que no es posible es que "insertar n datos utilizando n veces la operación que inserta un dato cuesta O(n²) con árboles binarios de búsqueda y O(n log n) con árboles AVL". Lo que se está preguntando no es si hacer n inserciones cuesta O(n) sino si existe un algoritmo alternativo. Con montículos binarios, hacer n inserciones también cuesta O(n log n) y sin embargo existe un algoritmo alternativo, diferente de realizar n operaciones de inserción, que construye el montículo binario en tiempo O(n).