skiplist - Create and manipulate skiplists
package require Tcl 8.2
package require struct ?1.3?
|
The ::struct::skiplist command creates a new skiplist object with an associated global Tcl command whose name is skiplistName. This command may be used to invoke various operations on the skiplist. It has the following general form:
Skip lists are an alternative data structure to binary trees. They can be used to maintain ordered lists over any sequence of insertions and deletions. Skip lists use randomness to achieve probabilistic balancing, and as a result the algorithms for insertion and deletion in skip lists are much simpler and faster than those for binary trees.
To read more about skip lists see Pugh, William. Skip lists: a probabilistic alternative to balanced trees In: Communications of the ACM, June 1990, 33(6) 668-676.
Currently, the key can be either a number or a string, and comparisons are performed with the built in greater than operator. The following commands are possible for skiplist objects:
Copyright © 2000 Keith Vetter