The binomial transform and the analysis of skip lists

DOI10.1016/J.TCS.2005.10.041zbMATH Open1086.68153OpenAlexW2006059832MaRDI QIDQ818124FDOQ818124

Authors: Patricio V. Poblete, J. Ian Munro, Thomas Papadakis 

Publication date: 24 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.041

Recommendations

• The binomial transform and its application to the analysis of skip lists
• Skip lists - some results on a recent data structure
• Average search and update costs in skip lists
• Biased skip lists
• A limit theory for random skip lists

zbMATH Keywords

analysis of algorithmsbinomial transformskip lists

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Factorials, binomial coefficients, combinatorial functions (05A10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Mellin transforms and asymptotics: Harmonic sums
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Linear probing and graphs
• The analysis of linear probing sort by the use of a new mathematical transform
• Combinatorics of geometrically distributed random variables: Left-to-right maxima
• Automatic average-case analysis of algorithms
• Average search and update costs in skip lists
• A limit theory for random skip lists
• Approximating functions by their Poisson transform
• Some observations on skip-lists
• Yet another application of a binomial recurrence. Order statistics
• The binomial transform and its application to the analysis of skip lists

Cited In (3)

• Fair priority scheduling (FPS): a process scheduling algorithm based on skip ring data structure
• Skip lists - some results on a recent data structure
• The binomial transform and its application to the analysis of skip lists

This page was built for publication: The binomial transform and the analysis of skip lists

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q818124)