Data structures

Not really C++, since it's about data structures, but meh. There is no other "general" programming forum, anyway.

Anyhow, I'm looking for information about some data structures, more namely:
- Splay trees
- Deterministic skip lists
- AA trees
- Treaps
- Pairing heaps
(And btw, no Wikipedia links, please; I already know of THOSE!)

I've done a little research on them, mostly via Wikipedia pages, but some google, too. What I'm most interested in is mostly details about how they operate and what situations they might be useful.

From what I gather, splay trees are basically your ordinary self-balancing binary search trees, with the exception that it always pushes up whatever information you access to the top of the tree. Hence, the data accessed most commonly will stay near the top and thus get speed boosts. Splay trees are bad for sequentially accessed data, though.

Deterministic skip lists are basically a skip list with enforced rules of a maximum gap size to make it deterministic, and make it easy to set a fixed worst-case performance bound.
What I'm still fuzzy about is balancing binary search tree vs skip list. It seems like it's a trade-off of performance vs memory footprint? It seems like skip lists and search trees are just basically two different ways of achieving the same thing. Yet, there are two different structures, so there must be some disadvantages and advantages of both.

AA trees are just another (simpler) variant of red-black trees. From what I gather, AA trees can be slower than red-black trees (if the red-black trees are implemented properly; but that is no small feat), but can be faster in practice due to simpler implementation (easier to optimize). I also believe I found something that mentioned delete operations in AA trees are faster? Is there a reason why AA trees are not always used over red-black trees?

Ah yes. Treaps. I get that they carry a priority and, of course, data. They are heap-ordered by the priority and then sorted by data? But this is a heap, which is basically a binary tree, so wouldn't they always be sorted by their priorities? I haven't found any good source to properly explain treaps. Any ideas?

I also haven't had any time to look at priority heaps a lot. But they should basically be a queue that allows items to be sorted by a priority, and compared to a normal priority queue, it also allows for efficient decrease key (priority) operations?

Info on my doubts and good sources would be very welcome.
Thanks.