Diapositiva PPT
2.7. Estructuras de datos duales.
- Una aplicación almacena información sobre determinados objetos.
- Necesitamos acceder a los objetos de forma ordenada (según determinada propiedad de los mismos) y de forma directa (según otra propiedad).
- Ejemplo:
- Un ranking de tenistas, ordenados según su categoría. Necesitamos acceder según el orden del ranking y según los nombres de los tenistas.
- Cada tenista nuevo es añadido en el último lugar del ranking.
- Un jugador puede retar al anterior en el ranking. Si le gana intercambian sus posiciones en el ranking.
- Operaciones: Agrega(nombre); anterior:= Reta(nombre); Cambia(posición);
- Soluciones posibles:
- Usar un array Escala[i]= nombre_tenista.
Agrega y Cambia son rápidas, O(cte), pero Reta necesita recorrer todo el array para buscar el nombre del tenista, O(n).
- Usar una tabla de dispersión con nombres, indicando la posición.
Agrega tiene O(cte). Reta y Cambia tienen O(n). El acceso por nombres es rápido pero por posiciones es lento, se debe buscar toda la tabla.