File SkipList.h

↰ Parent directory (ADS/dictionary)

The skip list of Pugh, beyond the book: a sorted list of the keys with express lanes, each node being in the levels 0 to L - 1, L drawn with probability :math:` 2^{-L} , and each level a sorted list of its nodes; a search goes along the highest level and drops a level before passing the key, in :math: O( log n ) ` expected time, and an insertion or a removal links or unlinks the node on its levels.

Definition (ADS/dictionary/SkipList.h)

Detailed Description

It is a DICTIONARY [see File ADT.h] as simple as a list and, with the right levels, as fast as a balanced tree, whose balance is in the random levels rather than in rotations; the generator is SplitMix64 [see File RandomHashing.h], seeded, so that a run is reproducible.

The contracts [see File Contract.h]: insert() ensures that the key is there and remove() that it is not; the invariant is that each level is sorted and a sublist of the level below, an O( n log n ) check at the level 3. The operations are defined in SkipList.tpp.

  1. Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM 33(6), 668-676, 1990, doi:10.1145/78973.78977

    1. Steele, D. Lea, C. H. Flood, Fast splittable pseudorandom number generators, Proceedings of OOPSLA 2014, 453-472, 2014, doi:10.1145/2660193.2660195 (SplitMix64)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes