This patch implements splay trees. Splay trees are self adjusting binary search trees that have several advantages over other trees: *) They are faster for skewed access patterns since they contain a kind of builtin cache. *) They do not use any memory for balancing information. I will write reference documentation for them if the patch is accepted into GLib. The patch is made with diff -Pur. Søren Sandmann