RBTree is an extension that implements Red-Black trees, roughly a cross between an ordered list while having direct access features similar to array. RBTree was written by [Philip Smolen].  See also: [Complex data structures]

RBTree is avaliable at [http://www.trade-ideas.com/home/phil/RBTree/RBTree.html] with source code at [http://www.trade-ideas.com/home/phil/RBTree/RBTree-1.1.2.zip].  Version 1.1.2 is distributed under a Tcl BSD-style license.


From the README


   RBTree is a TCL extension which adds a new data type to TCL.

   The new data type is a red-black tree.  Roughly speaking, this is a cross
   between an array and an ordered list.  It can efficiently find a value in
   the tree, like an array.  But it can also find the closest value to value
   that is not in the tree, or all the values between two values, like an
   ordered list.  Most operations are O(log(n)).  It can provide an
   alternative to lsort which more appropriate in interactive programs.  The
   red-black tree works correctly with keys with embedded nulls; built in TCL
   arrays do not.

   This data type is implemented as a new TCL data type.  It may be stored in
   a variable, passed to or from a procedure, converted to a string, etc.

   New procedures are added to access this data type.  They can give the
   appearance of a map (i.e. an array, or a keyed list), a multimap, a set,
   or a multiset (i.e. a bag).


----
[Category Package] |
[Category Data Structure]