Go to the previous, next section.
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.
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.
Go to the previous, next section.