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







struct::skiplist - Create and manipulate skiplists








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












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:



  

  
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:



  

  
Remove the specified nodes from the skiplist.

  

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

  

  
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.

  

  
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.

  

  
Return a count of the number of nodes in the skiplist.

  

  
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.










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://sourceforge.net/tracker/?group_id=12883]. Please also report any
    ideas for enhancements you may have for either package and/or
  documentation.








skiplist








Data structures








Copyright (c) 2000 Keith Vetter








  

    1.3
    struct