Computer Science basics : Skip List
Skip list is the first data structure that I encountered which uses randomization during elements allocation. Quite interesting to implement as well, check code samples here
Linked list is a great structure for many tasks, but finding an element in it requires time complexity O(n), which is far from the best.
Skip list is a data structure that decreases the average cost of search at the expense of how the data is stored.
Here, the data is added in “layers” — linked lists on top of each other. Imagine you have one sorted list at the “bottom” level having all your data. Then another one is added “on top”, but elements are included into it based on some uniform distribution rule. Let’s say we flip a coin and probability is 50%, that’s what you might obtain:
The search in this structure is performed as follows:
- you search the top list for the element
- once the current element of the list is bigger than the searched element, you go one layer down and continue the search
So in the worst case we go through all elements of the upper layer, then switch to bottom and go through the remaining members.
If we take n as number of elements in the initial list and l1 as number of elements in added layer, we will have the following search complexity:
This is easily explained via an example. Let’s set our initial list is of size 16, which gives us worst search complexity O(16). If we decide, for example, that added layer will have every second element of the original list, we reduce worst case complexity search to O(10). In worst case you will have to go through all nodes of the top list O(8), then switch to bottom and go through the remaining members O(2).
To decide on the best uniform distribution rule we have to minimize search function:
This basically says that instead of selecting every second element we should take every sqrt(n) element instead, so for our example with 16 elements we should take each 4th. We will then get better results:
Then in our function of search complexity l1 + n/l1 we substitute l1 with sqrt(n) and receive:
So if we add one new layer and put every sqrt(n) element in there, we will improve search complexity of the data structure from O(n) to O(sqrt(n))
More optimizations can be made. If we continue adding layers, the complexity will continue to decrease, but up to a certain point.
Complexity of k layers will be:
By minimizing this function we obtain optimal number of layers:
This means that for 16-element dataset we are going to need 3 additional layers with worst case search complexity distributed as follows:
Substituting k, we obtain the desired best average search complexity:
Now how should we distribute elements if we have log(n) layers?
We have n elements in the bottom list and log(n) layers. In order to distribute evenly we should have a distribution ratio r such so
This is solved when r = 2, see our case for n = 16:
So if we evenly distribute every second element to an upper list up to log(n) lists, we will ensure search complexity log(n), which is best possible in our case
There is only one trick left: adding elements to this structure.
If you have only one element to add, how do you promote every second element to keep the structure intact?
Answer is simple and beautiful: we are back to tossing the coin. Every time we have an element to add, we add it to the bottom list and then based on 50% probability “promote” the element to the upper layer. If the odds are that it is promoted, we flip the coin again and promote again until the log(n) level is reached. So that’s where randomization comes in handy.
Wrapping this up, time complexity goes as follows:
- Search average -> O(log n), worst -> O(n)
- Insert average -> O(log n), worst -> O(n)
- Delete average -> O(log n), worst -> O(n)
There may be a confusion about search O(n) worst case in this table. It happens only in case if you always get tails from the coin and never promote the added element. The more elements you add, the less probable this case is. See events with high probability
