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

KEYWORDS

81       skiplist
82

84       Copyright (c) 2000 Keith Vetter
85
86
87
88
89struct                                1.3                  struct::skiplist(n)
Impressum