Biased Coin Skip List Visualisations

Fair coin, p(0.5)

This is the default implementation of the skip list. Each coarser linked list (should) have half the references.

_images/doc_insert.png

1:8, p(0.125)

There are very few coarser linked lists here. This is getting closer to a normal linked list with O(n) search behaviour.

_images/doc_insert_12-5_percent.png

1:4, p(0.25)

_images/doc_insert_25_percent.png

3:4, p(0.75)

Each node now participates in many more linked lists. This may/may not improve search performance but it will certainly increase size requirements.

_images/doc_insert_75_percent.png

For the effect of a biased coin on time/space performance see Effect of a Biased Coin