Apparently, this year is the tenth anniversary of the publication of Chris Okasaki's book Purely Function Data Structures.
I can't say much about the content, because I've only ever skimmed through it once, a couple of years ago. What I can tell you is that it presents data structures from the perspective of purely functional languages (eg Haskell and ML), where values are immutable once they're created.
That sounds very strange to we non-FP developers, because most structures we play with are modified quite a bit. However, it leads to some interesting new forms, some with tantalising names like "bootstrapped heaps".
There's a PDF available if you don't want to spring for the dead tree version.