skip_lists.cpp

/*
** Skip Lists data structures. Equivalent to Balanced Binary Trees
** Insert: O(LogN)
** Remove: O(LogN)
** Search: O(LogN) on average (worst case: O(N))
*/

#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

class SkipLists
{
	struct node 
	{
		int value;
		vector<node*> next;
		
		node(int v, int level)
		{
			value = v;
			next.resize(level);
			
			for (int i = 0; i < level; ++i)
				next[i] = NULL;
			
		}
	};
	
	node *_head;
	int _level;
	
	public:
	
	/*
	** Random number with 32 bits so 33 levels, every element should be added to 0th level.
	*/
	SkipLists()
	{
		srand(time(NULL));
		
		_head = new node(0, 33);
		_level = 33;
	}
	
	/*
	** Insert element to all levels <= levels
	*/
	void insert(int v)
	{
		int random = rand();
		
		int level = 0;
		for (int r = random; r & 1 == 1; r >>= 1)
			level++;
			
		node *n = new node(v, level+1);
		
		node *curr = _head;
		for (int i = _level-1; i >= 0; --i)
		{
			while (curr->next[i] != NULL)
			{
				if (curr->next[i]->value > v)
					break;
				curr = curr->next[i];
			}
			
			if (i <= level)
			{
				n->next[i] = curr->next[i];
				curr->next[i] = n;
			}
		}
	}
	
	/*
	** Search is similar to Binary search, we move down once the next element is larger than search value
	*/
	bool search(int v)
	{
		node *curr = _head;
		
		for (int i = _level-1; i >= 0; --i)
		{
			while (curr->next[i] != NULL) 
			{
				if (curr->next[i]->value == v) 
					return true;
				if (curr->next[i]->value > v) 
					break;
				curr = curr->next[i];
			}
		}
		
		return false;
	}
	
	/*
	** Remove removes the element from all the levels
	** Calls delete in the end to remove the node completely (from the bottom level also)
	*/
	bool remove(int v)
	{
		node *curr = _head;
		
		bool found = false;
		node *temp;
		
		for (int i = _level-1; i >= 0; --i)
		{
			while (curr->next[i] != NULL)
			{
				if (curr->next[i]->value == v)
				{	
					found = true;
					temp = curr->next[i];
					curr->next[i] = curr->next[i]->next[i];
					break;
				}
				
				if (curr->next[i]->value > v)
					break;
				curr = curr->next[i];
			}
		}
		
		if (found) delete temp;
		
		return found;
	}

};


/*
** Usage:
** 
** SkipLists s;
**
** s.insert(2);
** s.search(2);
** s.remove(2);
**
*/