Estructura de datos para una búsqueda eficiente, cuando las inserciones y eliminaciones son solo unilaterales

Necesito una estructura de datos para almacenar un número  de elementos, cada uno de los cuales está asociado con un tiempo diferente  .  varía y, aunque tiene un límite superior teórico, este es muchos órdenes de magnitud más grande de lo que se usa típicamente.$n$$t_i$$n$

A través de mi aplicación puedo asegurar que:

• Los elementos insertados son siempre más nuevos que todos los elementos existentes, es decir, si se inserta un elemento asociado con un tiempo , entonces . Los elementos se insertan uno por uno.$\check{t}$$\check{t}>t_i ∀ i ∈ {1,…,n}$

• Solo se eliminan los elementos más antiguos, es decir, si se elimina el elemento , entonces . Las eliminaciones ocurren principalmente una por una, pero no hay daño directo si la eliminación de un elemento se retrasa, siempre que la fracción de elementos almacenados espuriosamente sea menor que 1.$j$$t_j < t_i ~∀ i ∈ \lbrace 1,…,n \rbrace \setminus \lbrace j \rbrace$

• Además de insertar y quitar, lo único que necesito hacer es encontrar los dos elementos vecinos durante un tiempo determinado con . Con otras palabras, necesito encontrar los dos elementos j  y  k de manera que t_j <\ tilde {t} <t_k y ∄ l ∈ \ {1, ..., n \}: t_j <t_l <t_k .$\tilde{t}$$\min\limits_i t_i < \tilde{t} < \max\limits_{i} t_i$$j$$k$$t_j<\tilde{t}<t_k$$∄ l ∈ \{1,…,n\}: t_j<t_l<t_k$

Mis criterios para la estructura de datos son:

1. Encontrar elementos como se describió anteriormente debe ser lo más rápido posible.
2. Insertar y quitar debe ser rápido.
3. La estructura de datos es comparablemente simple de implementar.

Mientras no estemos hablando de una pequeña compensación de tiempo de ejecución, cada criterio tiene prioridad sobre el siguiente.

Mi investigación hasta ahora ha arrojado que la respuesta es probablemente algún tipo de árbol de búsqueda de equilibrio automático, pero no pude encontrar ninguna información sobre cuál de ellos es mejor para el caso de inserción o eliminación unilateral, y probablemente me costará un tiempo considerable para descubrirme a mí mismo. Además, solo encontré información incompleta sobre qué tan bien se autoorganizan los árboles y qué tan rápido (por ejemplo, los árboles AVL se autoorganizan de manera más rígida que los árboles rojo-negros), y mucho menos cómo esto se ve afectado por la inserción o eliminación unilateral.

Almacene los elementos como una secuencia, ordenados por marca de tiempo creciente. Use la búsqueda binaria para encontrar la ubicación donde ocurriría si estuviera en la matriz; entonces puedes encontrar fácilmente los dos elementos vecinos. Encontrar los dos elementos vecinos se puede hacer en tiempo .$\tilde{t}$$O(\lg n)$

También deberá poder agregar al final de la secuencia y eliminar desde el principio. Por lo tanto, básicamente necesitas una cola.

Hay construcciones estándar para una cola. Por ejemplo, puede almacenarlos en una matriz, con operaciones de inserción y eliminación de tiempo amortizadas . Básicamente, tiene una matriz para los elementos de la secuencia, y un índice inicial (para el comienzo de la secuencia) y un índice final (para el final de la secuencia). Para eliminar desde el principio, incremente el índice de inicio. Para agregar al final, incremente el índice final; si esto pasa el final de la matriz existente, asigne una nueva matriz del doble del tamaño y copie en la nueva matriz.$O(1)$

Alternativamente: puede almacenar los elementos en un árbol binario equilibrado. Esto logrará el peor tiempo de para todas las operaciones.$O(\lg n)$