I need an efficient data structure for maintaining a set of values. Here, $n_1$

Question

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?

Explanation / Answer

Depending on how limited the memory is, the best choice for 1 could be a sorted array: Binary search is fast, insertions and deletions are rare and memory overhead is negligible.

For number 2 a (unsorted) singly linked list is better than a doubly linked one, since we (presumably) don't perform any operations that benefit from the backlinks and thus can save the memory (and maintenance time) required for them.

For number 3, unless the hash function and data don't play nicely with each other, the hash table will likely be faster than a tree. If the load factor does not get too low, it will also be more space efficient, since a binary tree with $n$ keys needs $sim 2n$ pointers.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.