GNU Info

(slib.info)Advanced Operations on Weight-Balanced Trees

---

Next: Indexing Operations on Weight-Balanced Trees Prev: Basic Operations on Weight-Balanced Trees Up: Weight-Balanced Trees

---

Enter node , (file) or (file)node

Advanced Operations on Weight-Balanced Trees
--------------------------------------------

  In the following the _size_ of a tree is the number of associations
that the tree contains, and a _smaller_ tree contains fewer
associations.

 - procedure+: wt-tree/split< wt-tree bound
     Returns a new tree containing all and only the associations in
     WT-TREE which have a key that is less than BOUND in the ordering
     relation of the tree type of WT-TREE.  The average and worst-case
     times required by this operation are proportional to the logarithm
     of the size of WT-TREE.

 - procedure+: wt-tree/split> wt-tree bound
     Returns a new tree containing all and only the associations in
     WT-TREE which have a key that is greater than BOUND in the
     ordering relation of the tree type of WT-TREE.  The average and
     worst-case times required by this operation are proportional to the
     logarithm of size of WT-TREE.

 - procedure+: wt-tree/union wt-tree-1 wt-tree-2
     Returns a new tree containing all the associations from both trees.
     This operation is asymmetric: when both trees have an association
     for the same key, the returned tree associates the datum from
     WT-TREE-2 with the key.  Thus if the trees are viewed as discrete
     maps then `wt-tree/union' computes the map override of WT-TREE-1 by
     WT-TREE-2.  If the trees are viewed as sets the result is the set
     union of the arguments.  The worst-case time required by this
     operation is proportional to the sum of the sizes of both trees.
     If the minimum key of one tree is greater than the maximum key of
     the other tree then the time required is at worst proportional to
     the logarithm of the size of the larger tree.

 - procedure+: wt-tree/intersection wt-tree-1 wt-tree-2
     Returns a new tree containing all and only those associations from
     WT-TREE-1 which have keys appearing as the key of an association
     in WT-TREE-2.  Thus the associated data in the result are those
     from WT-TREE-1.  If the trees are being used as sets the result is
     the set intersection of the arguments.  As a discrete map
     operation, `wt-tree/intersection' computes the domain restriction
     of WT-TREE-1 to (the domain of) WT-TREE-2.  The time required by
     this operation is never worse that proportional to the sum of the
     sizes of the trees.

 - procedure+: wt-tree/difference wt-tree-1 wt-tree-2
     Returns a new tree containing all and only those associations from
     WT-TREE-1 which have keys that _do not_ appear as the key of an
     association in WT-TREE-2.  If the trees are viewed as sets the
     result is the asymmetric set difference of the arguments.  As a
     discrete map operation, it computes the domain restriction of
     WT-TREE-1 to the complement of (the domain of) WT-TREE-2.  The
     time required by this operation is never worse that proportional to
     the sum of the sizes of the trees.

 - procedure+: wt-tree/subset? wt-tree-1 wt-tree-2
     Returns `#t' iff the key of each association in WT-TREE-1 is the
     key of some association in WT-TREE-2, otherwise returns `#f'.
     Viewed as a set operation, `wt-tree/subset?' is the improper subset
     predicate.  A proper subset predicate can be constructed:

          (define (proper-subset? s1 s2)
            (and (wt-tree/subset? s1 s2)
                 (< (wt-tree/size s1) (wt-tree/size s2))))

     As a discrete map operation, `wt-tree/subset?' is the subset test
     on the domain(s) of the map(s).  In the worst-case the time
     required by this operation is proportional to the size of
     WT-TREE-1.

 - procedure+: wt-tree/set-equal? wt-tree-1 wt-tree-2
     Returns `#t' iff for every association in WT-TREE-1 there is an
     association in WT-TREE-2 that has the same key, and _vice versa_.

     Viewing the arguments as sets `wt-tree/set-equal?' is the set
     equality predicate.  As a map operation it determines if two maps
     are defined on the same domain.

     This procedure is equivalent to

          (lambda (wt-tree-1 wt-tree-2)
            (and (wt-tree/subset? wt-tree-1 wt-tree-2
                 (wt-tree/subset? wt-tree-2 wt-tree-1)))

     In the worst-case the time required by this operation is
     proportional to the size of the smaller tree.

 - procedure+: wt-tree/fold combiner initial wt-tree
     This procedure reduces WT-TREE by combining all the associations,
     using an reverse in-order traversal, so the associations are
     visited in reverse order.  COMBINER is a procedure of three
     arguments: a key, a datum and the accumulated result so far.
     Provided COMBINER takes time bounded by a constant, `wt-tree/fold'
     takes time proportional to the size of WT-TREE.

     A sorted association list can be derived simply:

          (wt-tree/fold  (lambda (key datum list)
                           (cons (cons key datum) list))
                         '()
                         WT-TREE))

     The data in the associations can be summed like this:

          (wt-tree/fold  (lambda (key datum sum) (+ sum datum))
                         0
                         WT-TREE)

 - procedure+: wt-tree/for-each action wt-tree
     This procedure traverses the tree in-order, applying ACTION to
     each association.  The associations are processed in increasing
     order of their keys.  ACTION is a procedure of two arguments which
     take the key and datum respectively of the association.  Provided
     ACTION takes time bounded by a constant, `wt-tree/for-each' takes
     time proportional to in the size of WT-TREE.  The example prints
     the tree:

          (wt-tree/for-each (lambda (key value)
                              (display (list key value)))
                            WT-TREE))