Skip lists - some results on a recent data structure. Kirschenhofer, Peter (1994) Séminaire Lotharingien de Combinatoire [electronic only]
SOUR graphs for efficient completion. Lynch, Christopher, Strogova Polina (1998) Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Splaying a search tree in preorder takes linear time. Chaudhuri, R., Höft, H. (1991) International Journal of Mathematics and Mathematical Sciences