Questions tagged [skip-lists]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8 votes
3 answers
674 views

Proving skip-lists strongly weight-balanced in expectation

Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor? In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are ...
jbapple's user avatar
  • 11.2k
11 votes
1 answer
401 views

Strongly weight-balanced deterministic skip lists

In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are defined as: For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants. They claim: ...
jbapple's user avatar
  • 11.2k