We've now seen three different was to implement efficient search structures: AVL Trees, Skip Lists, and Hash Tables. All three of these data structures solve fundamentally the same problem: organizing pieces of information based on a unique key used to find it later. Sometimes, they're basically interchangeable; it doesn't always matter which choice we make. Sometimes, one or more of them should be disqualified from consideration, because it doesn't meet a requirement that's met by at least one of the others.

In each of the scenarios listed below, briefly explain whether it matters which of these three data structures we use. If so, list which ones you've disqualified from consideration and briefly explain why.

You'll be storing information about students, keyed by a student ID. The most important operations will be looking up a student based on their ID and printing a list of students sorted by their last names.

You'll be storing calendar information for one person, keyed by the date (i.e., on each date, you'll keep track of what's on their schedule). The most important operation will be finding out what's on their schedule for the next n days (i.e., today and the next n - 1 days), where n might potentially be as much as 365.
You'll be storing information about the songs in a media collection, keyed by a combination of an artist and a title, which are both strings, and the combination of which are assumed to be unique. The most important operation will be starting with a song and finding other songs that are similar-sounding.

Answer rating: 100% (QA)

The hash sort algorithm has a linear time complexity factor even in the worst case where... View the full answer