Skip lists
Skip lists are a probabilistic list-based data structure that
are a simple and efficient substitute for balanced trees.
Probabilistic balancing can also be used for tree-based data structures.
Skip lists can be used to implement a dictionary abstract data type
(i.e. implementing searches, insertions and deletions).
In William Pugh's "Cookbook" paper, below, he shows skip lists are
as versatile as balanced trees.
-
Overview of skiplists
-
- A Skiplist Cookbook by William
Pugh (.ps.gz)
-
Kym Horsell /
Kym@KymHorsell.COM
ADVISORY:
Email to these sites is filtered. Unsolicited email may
be automajically re-directed to the relevant postmaster.