Weight balanced trees support operations that view the tree as sorted sequence of associations. Elements of the sequence can be accessed by position, and the position of an element in the sequence can be determined, both in logarthmic time.

— procedure+: **wt-tree/index**` wt-tree index`

— procedure+:**wt-tree/index-datum**` wt-tree index`

— procedure+:**wt-tree/index-pair**` wt-tree index`

— procedure+:

— procedure+:

Returns the 0-based

indexth association ofwt-treein the sorted sequence under the tree's ordering relation on the keys.`wt-tree/index`

returns theindexth key,`wt-tree/index-datum`

returns the datum associated with theindexth key and`wt-tree/index-pair`

returns a new pair`(`

key`.`

datum`)`

which is the`cons`

of theindexth key and its datum. The average and worst-case times required by this operation are proportional to the logarithm of the number of associations in the tree.These operations signal an error if the tree is empty, if

index`<0`

, or ifindexis greater than or equal to the number of associations in the tree.Indexing can be used to find the median and maximum keys in the tree as follows:

median: (wt-tree/indexwt-tree(quotient (wt-tree/sizewt-tree) 2)) maximum: (wt-tree/indexwt-tree(-1+ (wt-tree/sizewt-tree)))

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

Determines the 0-based position of

keyin the sorted sequence of the keys under the tree's ordering relation, or`#f`

if the tree has no association with forkey. This procedure returns either an exact non-negative integer or`#f`

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

— procedure+: **wt-tree/min**` wt-tree`

— procedure+:**wt-tree/min-datum**` wt-tree`

— procedure+:**wt-tree/min-pair**` wt-tree`

— procedure+:

— procedure+:

Returns the association of

wt-treethat has the least key under the tree's ordering relation.`wt-tree/min`

returns the least key,`wt-tree/min-datum`

returns the datum associated with the least key and`wt-tree/min-pair`

returns a new pair`(key . datum)`

which is the`cons`

of the minimum key and its datum. The average and worst-case times required by this operation are proportional to the logarithm of the number of associations in the tree.These operations signal an error if the tree is empty. They could be written

(define (wt-tree/min tree) (wt-tree/index tree 0)) (define (wt-tree/min-datum tree) (wt-tree/index-datum tree 0)) (define (wt-tree/min-pair tree) (wt-tree/index-pair tree 0))

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

Returns a new tree containing all of the associations in

wt-treeexcept the association with the least key under thewt-tree's ordering relation. An error is signalled if the tree is empty. The average and worst-case times required by this operation are proportional to the logarithm of the number of associations in the tree. This operation is equivalent to(wt-tree/deletewt-tree(wt-tree/minwt-tree))

— procedure+: **wt-tree/delete-min!**` wt-tree`

Removes the association with the least key under the

wt-tree's ordering relation. An error is signalled if the tree is empty. The average and worst-case times required by this operation are proportional to the logarithm of the number of associations in the tree. This operation is equivalent to(wt-tree/delete!wt-tree(wt-tree/minwt-tree))