Buenas, tengo unas consultas de este ejercicio.
Primero, tengo una consulta de letra. Cuando me dicen “Obtener la lista de competidores (para imprimir)...” esa impresion tiene que ser en orden de los codigos como el procedimiento de impresion que se pide a parte? Para resolver el ejercicio supuse que no, no se me ocurre como mantener esta lista ordenada respetando los tiempos de ejecucion pedidos. Como podria hacerlo?
Mirando la clase de teorico, intente replicar la idea que se dio de hacer un ABB ordenado por los codigos de los competidores y que en los datos del competidor este un campo “siguiente” para hacer la lista por posiciones. Luego los comienzos de la lista me las guardo en un arreglo.
La diferencia estaria en que las listas las estaria haciendo doblemente encadenada, porque cuando voy a borrar un nodo, lo buscaria por el arbol, lo borro logicamente del arbol, despues tengo que ajustar la lista, pero para eso tengo que cambiar el nodo anterior en la lista y el siguiente, y si tengo que buscar en la lista de nuevo es algo O(n), entonces para moverme a la posicion anterior se me ocurrio tener el doble enlazado y aprovechar la busqueda que ya hice en el arbol. Como podria hacerlo en O(logn) promedio con listas simplemente enlazadas?
La otra consulta es si en el arbol me conviene guardar directamente el struct de datos, como nodo del arbol, o guardar un puntero a los datos, como en la lista (el siguiente de la lista estaria dentro de los datos). El argumento para guardarme un puntero seria que cuando voy a borrar del arbol , en el caso que tengo que cambiar de lugar un nodo para el borrado, en vez de tener que copiar todos los datos, puedo solo copiar el puntero, que seria mas facil. Hasta que punto es conveniente meter un puntero entre los datos (el struct) y los nodos del arbol?
Luego, en la clase grabada se habla de un ABB si no me equivoco. Hay algun motivo por el cual se elige un ABB en vez de un AVL? Bajo que circunstancias un ABB es mejor que un AVL?
Por ultimo, estaria bien agregar un hash para hacer las consultas mas rapidas (distribuyendo en los buckets segun los codigos) y usar el arbol solo para imprimir los elementos de forma ordenada?