Страницы справочника OS X

Эта страница руководства для  версии 10.9 Mac OS X

Читать страницы руководства

struct::skiplist(n)                          Tcl Data Structures                         struct::skiplist(n)



____________________________________________________________________________________________________________

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 probabilis-tic probabilistic
       tic  balancing, and as a result the algorithms for insertion and deletion in skip lists are much sim-pler simpler
       pler 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 eval-uated evaluated
              uated 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 SF Trackers [http://source -
       forge.net/tracker/? group_id=12883].  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




struct                                               1.3                                 struct::skiplist(n)