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.

— procedure+: **wt-tree/empty?**` wt-tree`

Returns

`#t`

ifwt-treecontains 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-treeand the association ofdatumwithkey. Ifwt-treealready had an association forkey, 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 inwt-tree.

— procedure+: **wt-tree/add!**` wt-tree key datum`

Associates

datumwithkeyinwt-treeand returns an unspecified value. Ifwt-treealready has an association forkey, that association is replaced. The average and worst-case times required by this operation are proportional to the logarithm of the number of associations inwt-tree.

— procedure+: **wt-tree/member?**` key wt-tree`

Returns

`#t`

ifwt-treecontains an association forkey, otherwise returns`#f`

. The average and worst-case times required by this operation are proportional to the logarithm of the number of associations inwt-tree.

— procedure+: **wt-tree/lookup**` wt-tree key default`

Returns the datum associated with

keyinwt-tree. Ifwt-treedoesn't contain an association forkey,defaultis returned. The average and worst-case times required by this operation are proportional to the logarithm of the number of associations inwt-tree.

— procedure+: **wt-tree/delete**` wt-tree key`

Returns a new tree containing all the associations in

wt-tree, except that ifwt-treecontains an association forkey, 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 inwt-tree.