Algoritmos y Estructuras de Datos (VJ1215)

Si la operación de inserción tiene coste temporal amortizado O(log n) entonces una secuencia de n operaciones de inserción consecutivas partiendo de un árbol vacío tiene coste temporal en el peor caso O(n log n).

El recorrido en inorden se realiza igual en cualquier árbol binario de búsqueda y tiene el mismo coste temporal en el peor caso: O(n).

Por tanto, el coste temporal total en el peor caso es O(n log n + n) = O(n log n).