Before You Start
Let's consider the operation getMin()
, which returns the smallest key in a set.
To find the minimum key, we need to start at the root and then keep going left until we can't go any further.
This process will follow a single path from the root down to a leaf which, in a balanced tree, we know has length \( \Theta(\log n) \).
We have no idea where the minimum key is stored in a hash table, so we have no choice but to look at all the keys!
Worse than that, we also have to look at the empty buckets just to see that they are empty.
So, for an open-addressing hash table with \( M \) buckets, this search takes \( \Theta(M) = \Theta( n\, / \lambda ) = \Theta(n) \) time.
Probably there is a clever way to avoid looking at the empty buckets, but doing so would make the code more complicated.
And more to the point, it would still be \( \Theta(n) \) time, just with a smaller constant factor.
(When logged in, completion status appears here.)