Balanced binary trees are a useful data structure for maintaining large
sets of ordered objects or sets of associations whose keys are ordered.
MIT Scheme has an comprehensive implementation of weight-balanced binary
trees which has several advantages over the other data structures for
(+ 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 associations exists in the tree this indicates that the key of the
association is a member of the set. Typically a value such as
#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
The weight balanced tree implementation is a run-time-loadable option. To use weight balanced trees, execute
once before calling any of the procedures defined here.