Tcl Library Source Code

Documentation
Login


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

struct::skiplist - Create and manipulate skiplists

Table Of Contents

SYNOPSIS

package require Tcl 8.5 9
package require struct::skiplist ?1.4?

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:

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:

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. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.

KEYWORDS

skiplist

CATEGORY

Data structures

COPYRIGHT

Copyright © 2000 Keith Vetter