Hashtables and balanced BSTs<br/> <br/> -Insertion and lookup in a balanced binary search trees are guaranteed O(log N), while insertion and lookup in a hashtable is O(1) under ideal conditions

Computer Science Jul 31, 2020

Hashtables and balanced BSTs<br/> <br/> -Insertion and lookup in a

balanced binary search trees are guaranteed O(log N), while insertion and lookup in a hashtable is O(1) under ideal conditions. Assume we are adding N keys into a set, implemented using a balanced BST or a hashtable (assume separate chaining). Describe two different scenarios in which the balanced BST would outperform the hashtable.