skiplist(n) Tcl Data Structures skiplist(n)

NAME
       skiplist - Create and manipulate skiplists

SYNOPSIS
       package require TTccll  88..22

       package require ssttrruucctt  ??11..33??

       sskkiipplliissttNNaammee option ?arg arg ...?

       skiplistName ddeelleettee node ?node...?

       skiplistName ddeessttrrooyy

       skiplistName iinnsseerrtt key value

       skiplistName sseeaarrcchh node ?-kkeeyy key?

       skiplistName ssiizzee

       skiplistName wwaallkk cmd



DESCRIPTION
       The  ::::ssttrruucctt::::sskkiipplliisstt  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:

       sskkiipplliissttNNaammee 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 balanc-
       ing, 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 proba-
       bilistic 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 ddeelleettee node ?node...?
              Remove the specified nodes from the skiplist.

       skiplistName ddeessttrrooyy
              Destroy the skiplist, including its storage space and associated
              command.

       skiplistName iinnsseerrtt 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 sseeaarrcchh node ?-kkeeyy 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 ssiizzee
              Return a count of the number of nodes in the skiplist.

       skiplistName wwaallkk 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.

KKEEYYWWOORRDDSS
       skiplist

COPYRIGHT       Copyright (c) 2000 Keith Vetter



struct                                1.3                          skiplist(n)