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:
(+ 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)