Skiplists

Skiplists are probabilistic data structures with many of the same properties as balanced binary search trees. They are analogous to express and local passenger trains and have O(log N) insert and search complexities.

I implemented a skiplist container class in C++ to have the same semantics as STL's std::map<>. Here are some results for insertion of unique integers in random order:

iteration and search tests pass.

N = 25000
avg insert: 13.1927
log_2(N): 14.6096

N = 25000
avg search: 14.503
log_2(N): 14.6096

Another neat property is there isn't an expensive re-balancing operation as seen in red-black and AVL trees. The insert() and delete() operations simply need to update at most log_2(N) pointers. Haven't looked at actual performance of my implementation but I thought it was an interesting exercise.


Here is an example skiplist after 11 inserts (after the jump).

[header]
 |         |         |        
 -> [0]   -> [1]   -> [2]  

[0] = 0
 |        
 -> [1]  

[1] = 10
 |         |        
 -> [2]   -> [2]  

[2] = 20
 |         |         |        
 -> [3]   -> [6]   -> [6]  

[3] = 30
 |        
 -> [4]  

[4] = 40
 |        
 -> [5]  

[5] = 50
 |        
 -> [6]  

[6] = 60
 |         |         |        
 -> [7]   -> null   -> null  

[7] = 70
 |        
 -> [8]  

[8] = 80
 |        
 -> [9]  

[9] = 90
 |        
 -> [10]  

[10] = 100
 |        
 -> null  

Searching for key [9] would consist of visiting the following sequence of nodes: (header, 2, 6, 7, 8, 9). Searching for key [3] would consist of visiting (header, 2, 3).