[−][src]Module skiplist::level_generator
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
GeometricalLevelGenerator | A level generator which will produce geometrically distributed numbers. |
Traits
LevelGenerator | 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 |