Previous: Red-Black Trees, Up: Associations

Balanced binary trees are a useful data structure for maintaining large sets of ordered objects or sets of associations whose keys are ordered. MIT/GNU Scheme has a comprehensive implementation of weight-balanced binary trees which has several advantages over the other data structures for large aggregates:

- In addition to the usual element-level operations like insertion, deletion and lookup, there is a full complement of collection-level operations, like set intersection, set union and subset test, all of which are implemented with good orders of growth in time and space. This makes weight-balanced trees ideal for rapid prototyping of functionally derived specifications.
- An element in a tree may be indexed by its position under the ordering of the keys, and the ordinal position of an element may be determined, both with reasonable efficiency.
- Operations to find and remove minimum element make weight-balanced trees simple to use for priority queues.
- The implementation is
*functional*rather than*imperative*. This means that operations like `inserting' an association in a tree do not destroy the old tree, in much the same way that`(+ 1 x)`

modifies neither the constant 1 nor the value bound to`x`

. The trees are referentially transparent thus the programmer need not worry about copying the trees. Referential transparency allows space efficiency to be achieved by sharing subtrees.

These features make weight-balanced trees suitable for a wide range of applications, especially those that require large numbers of sets or discrete maps. Applications that have a few global databases and/or concentrate on element-level operations like insertion and lookup are probably better off using hash tables or red-black trees.

The *size* of a tree is the number of associations that it
contains. Weight-balanced binary trees are balanced to keep the sizes
of the subtrees of each node within a constant factor of each other.
This ensures logarithmic times for single-path operations (like lookup
and insertion). A weight-balanced tree takes space that is proportional
to the number of associations in the tree. For the current
implementation, the constant of proportionality is six words per
association.

Weight-balanced trees can be used as an implementation for either
discrete sets or discrete maps (associations). Sets are implemented by
ignoring the datum that is associated with the key. Under this scheme
if an association exists in the tree this indicates that the key of the
association is a member of the set. Typically a value such as
`()`

, `#t`

or `#f`

is associated with the key.

Many operations can be viewed as computing a result that, depending on
whether the tree arguments are thought of as sets or maps, is known by
two different names. An example is `wt-tree/member?`

, which, when
regarding the tree argument as a set, computes the set membership
operation, but, when regarding the tree as a discrete map,
`wt-tree/member?`

is the predicate testing if the map is defined at
an element in its domain. Most names in this package have been chosen
based on interpreting the trees as sets, hence the name
`wt-tree/member?`

rather than `wt-tree/defined-at?`

.

The weight-balanced tree implementation is a run-time-loadable option. To use weight-balanced trees, execute

(load-option 'wt-tree)