1 2[//000000001]: # (struct::skiplist \- Tcl Data Structures) 3[//000000002]: # (Generated from file 'skiplist\.man' by tcllib/doctools with format 'markdown') 4[//000000003]: # (Copyright © 2000 Keith Vetter) 5[//000000004]: # (struct::skiplist\(n\) 1\.3 tcllib "Tcl Data Structures") 6 7<hr> [ <a href="../../../../toc.md">Main Table Of Contents</a> | <a 8href="../../../toc.md">Table Of Contents</a> | <a 9href="../../../../index.md">Keyword Index</a> | <a 10href="../../../../toc0.md">Categories</a> | <a 11href="../../../../toc1.md">Modules</a> | <a 12href="../../../../toc2.md">Applications</a> ] <hr> 13 14# NAME 15 16struct::skiplist \- Create and manipulate skiplists 17 18# <a name='toc'></a>Table Of Contents 19 20 - [Table Of Contents](#toc) 21 22 - [Synopsis](#synopsis) 23 24 - [Description](#section1) 25 26 - [Bugs, Ideas, Feedback](#section2) 27 28 - [Keywords](#keywords) 29 30 - [Category](#category) 31 32 - [Copyright](#copyright) 33 34# <a name='synopsis'></a>SYNOPSIS 35 36package require Tcl 8\.2 37package require struct::skiplist ?1\.3? 38 39[__skiplistName__ *option* ?*arg arg \.\.\.*?](#1) 40[*skiplistName* __delete__ *node* ?*node*\.\.\.?](#2) 41[*skiplistName* __destroy__](#3) 42[*skiplistName* __insert__ *key value*](#4) 43[*skiplistName* __search__ *node* ?__\-key__ *key*?](#5) 44[*skiplistName* __size__](#6) 45[*skiplistName* __walk__ *cmd*](#7) 46 47# <a name='description'></a>DESCRIPTION 48 49The __::struct::skiplist__ command creates a new skiplist object with an 50associated global Tcl command whose name is *skiplistName*\. This command may 51be used to invoke various operations on the skiplist\. It has the following 52general form: 53 54 - <a name='1'></a>__skiplistName__ *option* ?*arg arg \.\.\.*? 55 56 *Option* and the *arg*s determine the exact behavior of the command\. 57 58Skip lists are an alternative data structure to binary trees\. They can be used 59to maintain ordered lists over any sequence of insertions and deletions\. Skip 60lists use randomness to achieve probabilistic balancing, and as a result the 61algorithms for insertion and deletion in skip lists are much simpler and faster 62than those for binary trees\. 63 64To read more about skip lists see Pugh, William\. *Skip lists: a probabilistic 65alternative to balanced trees* In: Communications of the ACM, June 1990, 33\(6\) 66668\-676\. 67 68Currently, the key can be either a number or a string, and comparisons are 69performed with the built in greater than operator\. The following commands are 70possible for skiplist objects: 71 72 - <a name='2'></a>*skiplistName* __delete__ *node* ?*node*\.\.\.? 73 74 Remove the specified nodes from the skiplist\. 75 76 - <a name='3'></a>*skiplistName* __destroy__ 77 78 Destroy the skiplist, including its storage space and associated command\. 79 80 - <a name='4'></a>*skiplistName* __insert__ *key value* 81 82 Insert a node with the given *key* and *value* into the skiplist\. If a 83 node with that key already exists, then the that node's value is updated and 84 its node level is returned\. Otherwise a new node is created and 0 is 85 returned\. 86 87 - <a name='5'></a>*skiplistName* __search__ *node* ?__\-key__ *key*? 88 89 Search for a given key in a skiplist\. If not found then 0 is returned\. If 90 found, then a two element list of 1 followed by the node's value is retuned\. 91 92 - <a name='6'></a>*skiplistName* __size__ 93 94 Return a count of the number of nodes in the skiplist\. 95 96 - <a name='7'></a>*skiplistName* __walk__ *cmd* 97 98 Walk the skiplist from the first node to the last\. At each node, the command 99 *cmd* will be evaluated with the key and value of the current node 100 appended\. 101 102# <a name='section2'></a>Bugs, Ideas, Feedback 103 104This document, and the package it describes, will undoubtedly contain bugs and 105other problems\. Please report such in the category *struct :: skiplist* of the 106[Tcllib Trackers](http://core\.tcl\.tk/tcllib/reportlist)\. Please also report 107any ideas for enhancements you may have for either package and/or documentation\. 108 109When proposing code changes, please provide *unified diffs*, i\.e the output of 110__diff \-u__\. 111 112Note further that *attachments* are strongly preferred over inlined patches\. 113Attachments can be made by going to the __Edit__ form of the ticket 114immediately after its creation, and then using the left\-most button in the 115secondary navigation bar\. 116 117# <a name='keywords'></a>KEYWORDS 118 119[skiplist](\.\./\.\./\.\./\.\./index\.md\#skiplist) 120 121# <a name='category'></a>CATEGORY 122 123Data structures 124 125# <a name='copyright'></a>COPYRIGHT 126 127Copyright © 2000 Keith Vetter 128