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.
RBTree is avaliable at [L1 ] with source code at [L2 ]. 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).