# Skip Lists: A Probabilistic Alternative to Balanced Trees

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com

SourceSkip lists are a data structure that can be used in place of balanced trees.

Skip lists use probabilistic balancing rather than strictly enforced balancing

and as a result the algorithms for insertion and deletion in skip lists are

much simpler and significantly faster than equivalent algorithms for

balanced treesA node that has k forward pointers is called a level k node.

If every (2i)th node has a pointer 2i nodes ahead, then levels

of nodes are distributed in a simple pattern: 50% are level 1,

25% are level 2, 12.5% are level 3 and so on. What would

happen if the levels of nodes were chosen randomly, but in the

same proportions (e.g., as in Figure 1e)? A node’s i’th forward

pointer, instead of pointing 2i–1 nodes ahead, points to the

next node of level i or higher. Insertions or deletions would

require only local modifications; the level of a node, chosen

randomly when the node is inserted, need never change. Some

arrangements of levels would give poor execution times, but

we will see that such arrangements are rare. Because these

data structures are linked lists with extra pointers that skip

over intermediate nodes, I named them skip lists.

November 19, 2017 2:14 pm

From lawrence on Complexity emerges when a system has transitions that demand a different kind of math

"This is a branch of math that I hope to study a lot more. These transitions. Fractal math and dynamic systems...."