Module skiplist::level_generator
source · Expand description
SkipLists use a probabilistic distribution of nodes over the internal
levels, whereby the lowest level (level 0) contains all the nodes, and each
level n > 0
will contain a random subset of the nodes on level n - 1
.
Most commonly, a geometric distribution is used whereby the chance that a
node occupies level n
is p
times the chance of occupying level n-1
(with 0 < p < 1
).
It is very unlikely that this will need to be changed as the default should suffice, but if need be custom level generators can be implemented.
Structs
- A level generator which will produce geometrically distributed numbers.
Traits
- Upon the insertion of a new node in the list, the node is replicated to high levels with a certain probability as determined by a
LevelGenerator
.