Go to the previous, next section.
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
Returns the 0-based indexth association of wt-tree in the
sorted sequence under the tree's ordering relation on the keys.
wt-tree/index
returns the indexth key,
wt-tree/index-datum
returns the datum associated with the
indexth key and wt-tree/index-pair
returns a new pair
(key . datum)
which is the cons
of the indexth
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 a condition of type
condition-type:bad-range-argument
if index<0
or if
index is greater than or equal to the number of associations in
the tree. If the tree is empty, they signal an anonymous error.
Indexing can be used to find the median and maximum keys in the tree as follows:
median: (wt-tree/index wt-tree (quotient (wt-tree/size wt-tree) 2)) maximum: (wt-tree/index wt-tree (- (wt-tree/size wt-tree) 1))
procedure+: wt-tree/rank wt-tree key
Determines the 0-based position of key in the sorted sequence of
the keys under the tree's ordering relation, or #f
if the tree
has no association with for key. 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
Returns the association of wt-tree that 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-tree except 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/min wt-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/min wt-tree))
Go to the previous, next section.