Algoritmos y Estructuras de Datos (VJ1215)

Ambas soluciones resuelven el problema correctamente pero su coste temporal en el peor caso es O(n²), siendo n la talla del conjunto. Son mejores, por ser más eficientes, estas soluciones propuestas en el ejercicio 2.i, cuyo coste temporal es O(n).

Suponiendo que la eliminación de un nodo con dos hijos consiste en sustituirlo por el mínimo de su subárbol derecho, en la primera solución el peor caso se da cuando la raíz tiene dos hijos y su hijo derecho es a su vez la raíz de un subárbol degenerado hacia la izquierda en forma de lista enlazada de talla n - 2, como ilustra el siguiente ejemplo.

En la segunda solución, el peor caso se da cuando ningún nodo del árbol tiene subárbol derecho.