Which data structures books would you recommend as must reads?
 

Though I am not looking for any specific language
but you may assume CPP if needed.

Note- I am not referring to algorithms, just to
data structures. So, no Knuth please.

Any of them.

Algorithms + Data Structures = Programs should also be required reading, as should The Elements of Programming Style.

Realistically speaking, you can find (in any C++ standard-library, say ...) robust implementations of all of these data-structues. Therefore, you don't per se need to know how to write them yourself. What you do need to understand is basically how they work, what things they make easier-to-do, and what costs they accept in order to do it.

For instance: "Name three data structures that could be used in the implementation of a spelling-correction dictionary. Briefly describe (without giving actual code examples) how each one might be used, given that a known-good software implementation of each is presumed to exist. Briefly discuss at least two factors that would be in-favor of, and two more that would be against, the use of each data structure in this scenario." (30 pts.) ;)

Have I ever been a ...? Aww, how did you know??

That is exactly the reason why I have created this thread.
I exactly need a book which would tell me in plain English
why and how (for example) Red Black Trees and Recursion work.
That is all I need. I don't need the code. Hence this thread.

Now don't tell me to go to any local library because I
haven't heard of any closer to where I live.

The Algorithm Design Manual tends to get good reviews.

http://www.algorist.com/

Reviews lie.
"This newly expanded and updated second edition continues to take the "mystery" out of designing algorithms..."
Whoever said that has at best wishful thinking, where are the B-trees, no pseudo-code, no code, no nothing, are you telling me that the most important data structure doesn't deserve a few pages!?
Also, text compression topic, just awful.
As for the string hashing, there is nothing except this wisdom:
"Hashing has a variety of clever applications beyond just speeding up search. I
once heard Udi Manber—then Chief Scientist at Yahoo—talk about the algorithms
employed at his company. The three most important algorithms at Yahoo, he said,
were hashing, hashing, and hashing."

It is always good when some author tries to shed light, sadly when speaking of most BASIC important structures/etudes I see no good resource.
Several of my friends asked me the same question as the TS did, unfortunately I failed to recommend any book, just knowing how all books that I saw are far from the practical usage not to mention high-performance computing.

To me, not feeling the beauty of B-tree + string hashing + LempelZiv is a DISASTER.