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 as well. However, there are better ways to generate the required distribution, and this is left for you to explore further. For this task, the first external crate is going to be used: rand.
