Hands-On Data Structures and Algorithms with Rust

Leveling up

Since search in a skip list is very much like search in a binary search tree (the first section in Chapter 5, Robust Trees, will get more into those), it has to retain a certain distribution of nodes to be effective. The original paper by William Pugh proposes a way to create the desired distribution of nodes on a certain level by repeatedly flipping a coin (assuming p = 0.5).

This is the proposed algorithm (William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Figure 5):

randomLevel()    lvl := 1    -- random() that returns a random value in [0...1)    while random() < p and lvl < MaxLevel do        lvl := lvl + 1    return lvl 

Since this is a simple and understandable implementation, the skip list in this chapter will use this ...