Next: Advanced Operations on Weight-Balanced Trees, Previous: Construction of Weight-Balanced Trees, Up: 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.
Returns
#t
if wt-tree contains no associations, otherwise returns#f
.
Returns the number of associations in wt-tree, an exact non-negative integer. This operation takes constant time.
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.
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.
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.
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.
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.