RBTree

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 [L1 ] with source code at [L2 ]. Versions 1.1.2 and later are 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.

Lars H (10 Jun 2003): Is this a correct description from the script point of view, or is it just what things look like from the C point of view? In general Tcl strings, nulls are encoded so that they don't terminate the C string. Is there some exception from this with respect to array indices?

The RBTree documentation is just a little out of date. In TCL 8.0 about 90% of the TCL core could use strings with embedded nulls. You could not use embedded nulls in array keys, and a few other places. Newer versions of TCL work better with embedded nulls.

• 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).