Estructura de datos retroactiva
En informática, una estructura de datos retroactiva es una estructura de datos que admite modificaciones eficientes a una secuencia de operaciones que se han realizado en la estructura. Estas modificaciones pueden tomar la forma de inserción, eliminación o actualización retroactiva de una operación que se realizó en algún momento en el pasado. [1]
En el mundo real hay muchos casos en los que a uno le gustaría modificar una operación pasada a partir de una secuencia de operaciones. A continuación se enumeran algunas de las posibles aplicaciones:
No es posible considerar el tiempo como una dimensión espacial adicional. Para ilustrar esto, supongamos que asignamos la dimensión del tiempo a un eje del espacio. La estructura de datos que usaremos para agregar la dimensión de tiempo espacial es un montón mínimo. Deje que el eje y represente los valores clave de los elementos dentro del montón y que el eje x sea la dimensión de tiempo espacial. Después de varias inserciones y operaciones de eliminación mínima (todas realizadas de forma no retroactiva), nuestro montón mínimo aparecería como en la figura 1. Ahora supongamos que insertamos retroactivamente cero al comienzo de la lista de operaciones. Nuestro montón mínimo aparecería como en la figura 2. Observe cómo la operación única produce un efecto en cascada que afecta a toda la estructura de datos. Así podemos ver que mientras el tiempo se puede dibujar como una dimensión espacial,
A primera vista, la noción de estructuras de datos retroactivas parece muy similar a las estructuras de datos persistentes, ya que ambas tienen en cuenta la dimensión del tiempo. La diferencia clave entre las estructuras de datos persistentes y las estructuras de datos retroactivas es cómomanejan el elemento del tiempo. Una estructura de datos persistente mantiene varias versiones de una estructura de datos y se pueden realizar operaciones en una versión para producir otra versión de la estructura de datos. Dado que cada operación produce una nueva versión, cada versión se convierte en un archivo que no se puede cambiar (solo se pueden generar nuevas versiones). Dado que cada versión no cambia, la dependencia entre cada versión tampoco cambia. En las estructuras de datos retroactivas permitimos realizar cambios directamente a versiones anteriores. Dado que ahora cada versión es interdependiente, un solo cambio puede provocar una serie de cambios en todas las versiones posteriores. Las Figuras 1 y 2 muestran un ejemplo de este efecto de ondulación.
Cualquier estructura de datos se puede reformular en un entorno retroactivo. En general la estructura de datos implica una serie de actualizaciones y consultas realizadas a lo largo de un período de tiempo. Sea U = [u t 1 , u t 2 , u t 3 , ..., u t m ] la secuencia de operaciones de actualización de t 1 a t m tal que t 1 < t 2 < ... < t m . La suposición aquí es que como máximo se puede realizar una operación durante un tiempo dado t.
Definimos que la estructura de datos sea parcialmente retroactiva si puede realizar operaciones de actualización y consulta en el momento actual y admitir operaciones de inserción y eliminación en el pasado. Así para parcialmente retroactivos nos interesan las siguientes operaciones:
