Download Sections - MIT Computer Science and Artificial Intelligence Laboratory

140
MIT Scheme Reference
compatibility between trees in operations taking two trees. Usually a small number of
tree types are created at the beginning of a program and used many times throughout the
program’s execution.
make-wt-tree-type key<?
procedure+
This procedure creates and returns a new tree type based on the ordering predicate
key<?. Key<? must be a total ordering, having the property that for all key values
a, b and c:
⇒ #f
(key<? a a)
⇒ #f
(and (key<? a b) (key<? b a))
(if (and (key<? a b) (key<? b c))
(key<? a c)
⇒ #t
#t)
Two key values are assumed to be equal if neither is less than the other by key<?.
Each call to make-wt-tree-type returns a distinct value, and trees are only compatible if their tree types are eq?. A consequence is that trees that are intended to be
used in binary-tree operations must all be created with a tree type originating from
the same call to make-wt-tree-type.
number-wt-type
variable+
A standard tree type for trees with numeric keys. Number-wt-type could have been
defined by
(define number-wt-type (make-wt-tree-type
<))
string-wt-type
variable+
A standard tree type for trees with string keys. String-wt-type could have been
defined by
(define string-wt-type (make-wt-tree-type
string<?))
make-wt-tree wt-tree-type
procedure+
This procedure creates and returns a newly allocated weight-balanced tree. The tree
is empty, i.e. it contains no associations. Wt-tree-type is a weight-balanced tree type
obtained by calling make-wt-tree-type; the returned tree has this type.
singleton-wt-tree wt-tree-type key datum
procedure+
This procedure creates and returns a newly allocated weight-balanced tree. The tree
contains a single association, that of datum with key. Wt-tree-type is a weightbalanced tree type obtained by calling make-wt-tree-type; the returned tree has
this type.
alist->wt-tree tree-type alist
procedure+
Returns a newly allocated weight-balanced tree that contains the same associations
as alist. This procedure is equivalent to: