I've just finished my Splaytree ADT and chucked it up on: www.github.com/willemt/CSplaytree
Splaytrees are a binary tree with the useful property that the last retrieved item will propagate to the root of the tree. This allows commonly accessed items to be at the top of the tree and thus quicker to access. Most Pseudo Least Recently Used algorithms use a splaytree as a base ADT because of this property.
Next up: Pseudo LRU