Back to Deterministic skip list
This section contains notes on the implementation of the skip-list in Pastel. It helps to understand the corresponding code.
We implement the deterministic 1-2-skip-list, using the array-implementation. From now on, we will refer to this variant as a skip-list.
We allow the skip-list to contain equivalent elements, i.e. keys x and y such that !(x < y) and !(y < x). This divides the set of elements in the skip-list into equivalence classes. We let the first element of each equivalence class work as a representative.
To avoid degrading the performance of the skip-list because of equivalent elements, we will organize the levels of the skip-list as follows:
We call the levels > 0 skip levels. The idea is that whenever a search is done for an element, the interest is always on the first or the last matching element. When the non-representatives are linked only on the basic level, they are invisible to the skip-levels, and thus we are able to search exclusively in the set of representatives.
When a given search is started from a non-representative, we need a way to obtain the representative of its equivalence class in constant time. We could store a link to the representative with each element. However, this would lead to linear complexity updates when a representative is removed from the skip-list. To avoid this, we represent the equivalence classes explicitly. Each equivalence class points to its representative, and each element points to its equivalence class. Thus when a representative is removed, we may simply replace the representative pointer in the equivalence class.
We will use the array-implementation of the skip-list. The array-implementation takes less memory than the linked-list implementation because it need not store the vertical pointers.
Each node stores the skip-links for every level of its height in an array, as well as the height of the node.
The physical size of the link-array is always the logical height of the node rounded up to the next power of two, so it need not be stored. Growing the physical size exponentially is also needed to achieve logarithmic updates.
We do not store the link-array in an std::vector, because it
also stores the physical size.
It is fast to find out the next power of two. But it is even faster to test if an integer is a power of two. It is sufficient to use the the latter exclusively; when the logical size hits a power of two, the next physical size is the double of this.
bool isPowerOfTwo(integer that)
{
return (that & (that - 1)) == 0;
}
An alternating skip-list is an implementation strategy where every skip-link is unidirectional, but alternates at every level.
Alternation saves memory (by a constant) over bidirectional linking, but sacrifices efficiency (by a constant) in finger searches.
We do not implement alternation because we favor finger-search efficiency over memory use.
Inserting a node may require several skip-link arrays to be reallocated to greater physical sizes.
To guarantee strong exception safety, a skip-link array of every height of the form 2^i, up to the current maximum, is allocated before the insertion, and these are then used when required.
When rebalancing, a link-set may be replaced by a bigger link-set. In this case the old link-set is put pack in the pre-allocation set, rather than deleted.
Find the correct place to insert the new element.
If the insertion results in 3 subsequent elements with the same level, raise the level of the middle one, and recurse to rebalance the middle element, repeatedly raising the middle of 3 subsequent elements with the same level.
Removal from a skip-list works as follows:
If the element is not of height 2, pass its link-set to its successor or predecessor, whichever is present.
Remove the node.
Let n = 2.
If an element of height n is present, then we are done.
Otherwise, there must be an element with height n + 1, which we shorten to height n.
If there are now three subsequent elements of height n, raise the middle one, and we are done.
Otherwise, the shortening may have removed the only element of height n + 1. Repeat the previous with height n + 1.
The probabilistic skip-list was introduced in
Skip Lists: A Probabilistic Alternative to Balanced Trees, W. Pugh, Communications of the ACM, vol. 33, no. 6, June 1990, pp. 668-676.
The deterministic skip-list was introduced in
Deterministic Skip Lists, J. Ian Munro, Thomas Papadakis, Robert Sedgewick, Proceedings of the ACM-SIAM Third Annual Symposium on Discrete Algorithms, January 1992.
The alternating skip-list was introduced in
Alternating Skip Lists, Laurence Marrie, Dr Dobbs Journal, August 2000.