I need an efficient data structure for maintaining a set of values.
Here, $n_1$ is the number of insertions per unit time; $n_2$ is the number of deletions per unit time; $k$ is the number of searches per unit time.
I have 4 possible use cases:
- $k \gg n_1,n_2$ with limited memory
- $n_1 \gg k,n_2$ with limited memory
- $k, n_1, n_2$ are comparable with limited memory
- $k, n_1, n_2$ are comparable with unlimited memory
I have decided to use a doubly linked list for the second case and a direct address table for the fourth case.
My question is about the first and the third cases. Both Hash Table and Tree (AVL or Red-Black) look promising. Should I choose the Hash Table with an amortised constant time or the Tree with a $\log n$ worst case time?