GNU Info

(slib.info)Weight-Balanced Trees

---

Prev: Relational Database Up: Database Packages

---

Enter node , (file) or (file)node

Weight-Balanced Trees
=====================

  `(require 'wt-tree)'

  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 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 associations 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)

once before calling any of the procedures defined here.

Construction of Weight-Balanced Trees

Basic Operations on Weight-Balanced Trees

Advanced Operations on Weight-Balanced Trees

Indexing Operations on Weight-Balanced Trees