Comment by sznurek

I would recommend "Purely Functional Data Structures" by Chris Okasaki. It's not only for functional programmers - there is also a bunch of structures useful in imperative languages.