GNU Info

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

---

Next: Advanced Operations on Weight-Balanced Trees Prev: Construction of Weight-Balanced Trees Up: Weight-Balanced Trees

---

Enter node , (file) or (file)node

Basic Operations on Weight-Balanced Trees
-----------------------------------------

  This section describes the basic tree operations on weight balanced
trees.  These operations are the usual tree operations for insertion,
deletion and lookup, some predicates and a procedure for determining the
number of associations in a tree.

 - procedure+: wt-tree? object
     Returns `#t' if OBJECT is a weight-balanced tree, otherwise
     returns `#f'.

 - procedure+: wt-tree/empty? wt-tree
     Returns `#t' if WT-TREE contains no associations, otherwise
     returns `#f'.

 - procedure+: wt-tree/size wt-tree
     Returns the number of associations in WT-TREE, an exact
     non-negative integer.  This operation takes constant time.

 - procedure+: wt-tree/add wt-tree key datum
     Returns a new tree containing all the associations in WT-TREE and
     the association of DATUM with KEY.  If WT-TREE already had an
     association for KEY, the new association overrides the old.  The
     average and worst-case times required by this operation are
     proportional to the logarithm of the number of associations in
     WT-TREE.

 - procedure+: wt-tree/add! wt-tree key datum
     Associates DATUM with KEY in WT-TREE and returns an unspecified
     value.  If WT-TREE already has an association for KEY, that
     association is replaced.  The average and worst-case times
     required by this operation are proportional to the logarithm of
     the number of associations in WT-TREE.

 - procedure+: wt-tree/member? key wt-tree
     Returns `#t' if WT-TREE contains an association for KEY, otherwise
     returns `#f'.  The average and worst-case times required by this
     operation are proportional to the logarithm of the number of
     associations in WT-TREE.

 - procedure+: wt-tree/lookup wt-tree key default
     Returns the datum associated with KEY in WT-TREE.  If WT-TREE
     doesn't contain an association for KEY, DEFAULT is returned.  The
     average and worst-case times required by this operation are
     proportional to the logarithm of the number of associations in
     WT-TREE.

 - procedure+: wt-tree/delete wt-tree key
     Returns a new tree containing all the associations in WT-TREE,
     except that if WT-TREE contains an association for KEY, it is
     removed from the result.  The average and worst-case times required
     by this operation are proportional to the logarithm of the number
     of associations in WT-TREE.

 - procedure+: wt-tree/delete! wt-tree key
     If WT-TREE contains an association for KEY the association is
     removed.  Returns an unspecified value.  The average and worst-case
     times required by this operation are proportional to the logarithm
     of the number of associations in WT-TREE.