Structure de données pour une recherche efficace, lorsque les insertions et les suppressions ne sont que unilatérales

J'ai besoin d'une structure de données pour stocker un numéro $n$ d'éléments, dont chacun est associé à un moment différent $t_i$. $n$ varie et même si elle a une limite supérieure théorique, elle est de plusieurs ordres de grandeur supérieure à ce qui est généralement utilisé.

Grâce à ma candidature, je peux m'assurer que:

• Les éléments insérés sont toujours plus récents que tous les éléments existants, c'est-à-dire si un élément associé à un temps $\check{t}$est inséré, puis . Les éléments sont insérés un par un.$\check{t}>t_i ∀ i ∈ {1,…,n}$

• Seuls les éléments les plus anciens sont supprimés, c'est-à-dire que si l'élément est supprimé, alors . Les suppressions se produisent principalement une par une, mais il n'y a pas de préjudice direct si la suppression d'un élément est retardée, tant que la fraction des éléments stockés de manière erronée reste inférieure à 1.$j$$t_j < t_i ~∀ i ∈ \lbrace 1,…,n \rbrace \setminus \lbrace j \rbrace$

• Hormis l'insertion et la suppression, la seule chose que je dois faire est de trouver les deux éléments voisins pour un certain temps avec . Avec d'autres mots je dois trouver les deux éléments j  et  k tels que t_j <\ tilde {t} <t_k et ∄ 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$

Mes critères pour la structure des données sont:

1. La recherche des éléments décrits ci-dessus doit être aussi rapide que possible.
2. L'insertion et le retrait doivent être rapides.
3. La structure de données est relativement simple à mettre en œuvre.

Tant que nous ne parlons pas d'un petit décalage d'exécution, chaque critère est prioritaire sur le suivant.

Jusqu'à présent, mes recherches ont montré que la réponse est probablement une sorte d'arbre de recherche auto-équilibré, mais je n'ai trouvé aucune information qui soit la meilleure pour le cas de l'insertion ou de la suppression unilatérale, et cela me coûtera probablement un beaucoup de temps pour me découvrir. De plus, je n'ai trouvé que des informations incomplètes sur la façon dont les arbres s'organisent et à quelle vitesse (par exemple, les arbres AVL s'organisent de manière plus rigide que les arbres rouge-noir), sans parler de la façon dont cela est affecté par l'insertion ou la suppression unilatérale.

Stockez les éléments sous forme de séquence, triés en augmentant l'horodatage. Utilisez la recherche binaire pour trouver l'emplacement où se produirait s'il était dans le tableau; alors vous pouvez facilement trouver les deux éléments voisins. La recherche des deux éléments voisins peut se faire en temps .$\tilde{t}$$O(\lg n)$

Vous devrez également pouvoir ajouter à la fin de la séquence et supprimer depuis le début. Ainsi, vous avez essentiellement besoin d'une file d'attente.

Il existe des constructions standard pour une file d'attente. Par exemple, vous pouvez les stocker dans un tableau, avec des opérations d'insertion et de suppression amorties . Fondamentalement, vous avez un tableau pour les éléments de la séquence, et un index de début (pour le début de la séquence) et un index de fin (pour la fin de la séquence). Pour supprimer depuis le début, incrémentez l'index de démarrage. Pour ajouter à la fin, incrémentez l'index de fin; si cela dépasse la fin du tableau existant, allouez un nouveau tableau de la taille double et copiez-le dans le nouveau tableau.$O(1)$

Alternativement: vous pouvez stocker les éléments dans un arbre binaire équilibré. Cela permettra d'obtenir le temps défavorable pour toutes les opérations.$O(\lg n)$