Next: Advanced Operations on Weight-Balanced Trees, Previous: Construction of Weight-Balanced Trees, Up: Weight-Balanced Trees [Contents][Index]

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