NAME¶
struct::skiplist - Create and manipulate skiplists
SYNOPSIS¶
package require
Tcl 8.2
package require
struct::skiplist ?1.3?
skiplistName option ?
arg arg ...?
skiplistName delete node ?
node...?
skiplistName destroy
skiplistName insert key value
skiplistName search node ?
-key key?
skiplistName size
skiplistName walk cmd
DESCRIPTION¶
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:
- skiplistName option ?arg arg ...?
- Option and the args determine the exact behavior of the
command.
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:
- skiplistName delete node ?node...?
- Remove the specified nodes from the skiplist.
- skiplistName destroy
- Destroy the skiplist, including its storage space and associated
command.
- skiplistName insert key value
- Insert a node with the given key and value into the
skiplist. If a node with that key already exists, then the that node's
value is updated and its node level is returned. Otherwise a new node is
created and 0 is returned.
- skiplistName search node ?-key
key?
- Search for a given key in a skiplist. If not found then 0 is returned. If
found, then a two element list of 1 followed by the node's value is
retuned.
- skiplistName size
- Return a count of the number of nodes in the skiplist.
- skiplistName walk cmd
- Walk the skiplist from the first node to the last. At each node, the
command cmd will be evaluated with the key and value of the current
node appended.
BUGS, IDEAS, FEEDBACK¶
This document, and the package it describes, will undoubtedly contain bugs and
other problems. Please report such in the category
struct :: skiplist
of the
Tcllib Trackers [
http://core.tcl.tk/tcllib/reportlist]. Please
also report any ideas for enhancements you may have for either package and/or
documentation.
KEYWORDS¶
skiplist
CATEGORY¶
Data structures
COPYRIGHT¶
Copyright (c) 2000 Keith Vetter