1struct::skiplist(n)           Tcl Data Structures          struct::skiplist(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       struct::skiplist - Create and manipulate skiplists
9

SYNOPSIS

11       package require Tcl  8.2
12
13       package require struct::skiplist  ?1.3?
14
15       skiplistName option ?arg arg ...?
16
17       skiplistName delete node ?node...?
18
19       skiplistName destroy
20
21       skiplistName insert key value
22
23       skiplistName search node ?-key key?
24
25       skiplistName size
26
27       skiplistName walk cmd
28
29______________________________________________________________________________
30

DESCRIPTION

32       The  ::struct::skiplist  command  creates a new skiplist object with an
33       associated global Tcl command whose name is skiplistName. This  command
34       may  be  used  to invoke various operations on the skiplist. It has the
35       following general form:
36
37       skiplistName option ?arg arg ...?
38              Option and the args determine the exact behavior of the command.
39
40       Skip lists are an alternative data structure to binary trees. They  can
41       be  used  to maintain ordered lists over any sequence of insertions and
42       deletions. Skip lists use randomness to achieve  probabilistic  balanc‐
43       ing,  and as a result the algorithms for insertion and deletion in skip
44       lists are much simpler and faster than those for binary trees.
45
46       To read more about skip lists see Pugh, William.  Skip lists: a  proba‐
47       bilistic  alternative  to balanced trees In: Communications of the ACM,
48       June 1990, 33(6) 668-676.
49
50       Currently, the key can be either a number or a string, and  comparisons
51       are  performed  with the built in greater than operator.  The following
52       commands are possible for skiplist objects:
53
54       skiplistName delete node ?node...?
55              Remove the specified nodes from the skiplist.
56
57       skiplistName destroy
58              Destroy the skiplist, including its storage space and associated
59              command.
60
61       skiplistName insert key value
62              Insert a node with the given key and value into the skiplist. If
63              a node with that key already exists, then the that node's  value
64              is  updated and its node level is returned. Otherwise a new node
65              is created and 0 is returned.
66
67       skiplistName search node ?-key key?
68              Search for a given key in a skiplist. If not  found  then  0  is
69              returned.   If  found,  then a two element list of 1 followed by
70              the node's value is retuned.
71
72       skiplistName size
73              Return a count of the number of nodes in the skiplist.
74
75       skiplistName walk cmd
76              Walk the skiplist from the first node to the last. At each node,
77              the  command cmd will be evaluated with the key and value of the
78              current node appended.
79

BUGS, IDEAS, FEEDBACK

81       This document, and the package it describes, will  undoubtedly  contain
82       bugs  and other problems.  Please report such in the category struct ::
83       skiplist of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
84       Please  also  report any ideas for enhancements you may have for either
85       package and/or documentation.
86
87       When proposing code changes, please provide unified diffs, i.e the out‐
88       put of diff -u.
89
90       Note  further  that  attachments  are  strongly  preferred over inlined
91       patches. Attachments can be made by going  to  the  Edit  form  of  the
92       ticket  immediately  after  its  creation, and then using the left-most
93       button in the secondary navigation bar.
94

KEYWORDS

96       skiplist
97

CATEGORY

99       Data structures
100
102       Copyright (c) 2000 Keith Vetter
103
104
105
106
107tcllib                                1.3                  struct::skiplist(n)
Impressum