Skip List - a probabilistic data structure as alternative to balanced search trees

Binary search trees can be great used for search in O(logN) time. However the problem with it is that the tree needs to be balanced otherwise the search can be degenerated to a linear search on a linked list. Balanced search tree like red-back tree or splay tree can help to maintain the tree balanced. However the extra effort and caution have to be taken to make it work. Skip lists are about as fast as highly optimized balanced tree and substantially faster than casually implemented binary search tree.

Skip list is a probabilistic data structure in the way that level of each node is randomly choose as a number below the predefined maximum height.

class Node {

        int data;

Node[] next;

        //l is randomly generated number between 1 and max height

public Node(int l){

this.next = new Node[l];

}

}

Here is one simple coin-flipping algorithm to generate the number:

public int randomLevel(int max){

int level = 1;

while(Math.random()<0.5 && level < max)

level++;

return level;

}

another efficient way to do that and we assume the max <= 32:

public int randHeight(int max){

 int random = new Random().nextInt(); //generate int with 32 bits

 boolean found = false;

 int h = 1;

 while(!found && random > 0){

 if( (random & 1) > 0)

found = true;

 else{

h++;

random = random >>1;

 }

 }

 return Math.max(h, max-1);

}

And search is to compare the next key's value with search value, simply go down the level until we hit bottom level.

//return the value itself if found otherwise -1

public int find(Node head, int v){
Node curr = head;
for(int l = level-1; l>=0; l--){
for(; curr.next[l]!=null && curr.next[l].data<v; curr = curr.next[l]){}
}
return curr.next[0]!=null && curr.next[0].data == v? curr.next[0].data : -1;
}