Data structure for efficient searching, when insertions and removals are only one-sided

Question

I need a data structure for storing a number $n$ of elements, each of whom is associated with some different time $t_i$. $n$ varies and while it has a theoretical upper limit, this is many orders of magnitude larger than what is typically used.

Through my application I can ensure that:

• Inserted elements are always newer than all existing elements, i.e., if an element associated with a time $\check{t}$ is inserted, then $\check{t}>t_i ∀ i ∈ {1,…,n}$. Elements are inserted one by one.

• Only the oldest elements are removed, i.e., if element $j$ is removed, then $t_j < t_i ~∀ i ∈ \lbrace 1,…,n \rbrace \setminus \lbrace j \rbrace$. Removals happen mostly one by one, but there is no direct harm if an element’s removal is delayed, as long as the fraction of spuriously stored elements remains smaller than 1.

• Apart from inserting and removing, the only thing I need to do is find the two neighbouring elements for some given time $\tilde{t}$ with $\min\limits_i t_i < \tilde{t} < \max\limits_{i} t_i$. With other words I need to find the two elements $j$ and $k$ such that $t_j<\tilde{t}<t_k$ and $∄ l ∈ \{1,…,n\}: t_j<t_l<t_k$.

My criteria for the data structure are:

1. Finding elements as described above should be as quick as possible.
2. Inserting and removing should be quick.
3. The data structure is comparably simple to implement.

As long as we are not talking about a small runtime offset, each criterion has priority over the next.

My research so far has yielded that the answer is likely some kind of self-balancing search tree, but I failed to find any information which of them is best for the case of one-sided inserting or deleting, and it will probably cost me a considerable time to find out myself. Also, I only found incomplete information about how well the trees self-organise and how quickly (e.g., AVL trees self-organise more rigidly than red-black trees), let alone how this is affected by one-sided inserting or deleting.

Answer 1

Store the elements as a sequence, sorted by increasing timestamp. Use binary search to find the location where $\tilde{t}$ would occur if it were in the array; then you can easily find the two neighboring elements. Finding the two neighboring elements can be done in $O(\lg n)$ time.

You'll also need to be able to append to the end of the sequence and delete from the beginning. Thus, basically you need a queue.

There are standard constructions for a queue. For instance, you can store them in an array, with amortized $O(1)$-time insert and delete operations. Basically, you have an array for the elements of the sequence, and a start index (for the beginning of the sequence) and an end index (for the end of the sequence). To delete from the beginning, increment the start index. To add to the end, increment the end index; if this runs past the end of the existing array, allocate a new array of double the size and copy into the new array.

Alternatively: you can store the elements in a balanced binary tree. This will achieve worst-case $O(\lg n)$-time for all operations.