Top-Down Skiplists

Luis Barba, Pat Morin

We describe todolists (top-down skiplists), a variant of skiplists (Pugh 1990) that can execute searches using at most ${\log }_{2-\epsilon }n+O(1)$ binary comparisons per search…