There's probably no way to know what they were looking for, short of asking them directly. But you have at least two options: (a) roll your eyes at anyone who tells you that you need more knowledge about red-black trees or hash tables to be an excellent engineer, or (b) realize it's a game, and play it with a passion.
Both routes are perfectly valid, and personally I prefer route (a). But if you're deciding to do route (b), you could study as much as you can on the subjects, quiz yourself on various trivia related to red-black trees, look up related interview questions, etc.
This is a bit of a tangent, but from a motivation standpoint, I've found it's optimal to think of interviews as a lottery ticket with 10% chance of winning regardless of your ability, rather than an as an obstacle that can be failed due to lack of ability. There's no reason to be discouraged when someone rejects you in a world where people reject engineers for reasons that are essentially random.
Your hash table knowledge is perfectly fine. So is your red-black tree knowledge. Roughly zero percent of programmers implement those during the course of their job, so knowing their characteristics is more than enough.