Question

Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

(a) no they are not preferred

(b) because of resizing issues of hash table and better ordering in redblack trees

(c) because they can be implemented using trees

(d) because they are balanced

My question comes from Red Black Tree in chapter Binary Trees of Data Structures & Algorithms I

This question was addressed to me during an interview for a job.

Answer 1

Correct option is (b) because of resizing issues of hash table and better ordering in redblack trees

For explanation: Redblack trees have O(logn) for ordering elements in terms of finding first and next elements. also whenever table size increases or decreases in hash table you need to perform rehashing which can be very expensive in real time. also red black stores elements in sorted order rather than input order.