11.7.2 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.