Buenas tardes,
Estaba haciendo este ejercicio y me surgieron algunas dudas. La primera es respecto a la parte en la que te pide que sugieras una implementación que te permita cumplir con lo ordenes solicitados. Dado que la impresión tiene que ser O(n) pero caso y la inserción/eliminación es O(log(n)) caso promedio se podría implementar con un ABB.
Ademas pensé en agregarle un arreglo cuyos indices sean los puntajes acotados que pueden obtener las agrupaciones. Esto con el fin de que el resultado de la función 'ListaPuntos' sea O(1) compartiendo memoria con los nodos del ABB.
Lo que me genera duda es que el insertar, que creo yo es como la función que especificas en la parte anterior 'Asociar', la cual en el peor caso según esta implementación no seria O(log(n)).
La situación es la siguiente:
Si tengo que todas las agrupaciones en el ABB tienen el mismo puntaje y decido asociar una agrupación con este mismo puntaje e inmediatamente después se lo cambio (actualizo). Entonces encontrarla en el ABB es O(log(n)) pero para cambiarla de una lista a la otra (a la lista que salga de la posición del arreglo que se corresponde al nuevo puntaje) tengo que recorrer toda una lista con agrupaciones que tienen el mismo puntaje que en este caso son n-1 agrupaciones. Luego no podría cumplir con los ordenes solicitados.
No se si se entiende, o si hay algo que no estoy viendo, pero eso seria todo. Tal vez la implementación no es la correcta.
Saludos.