Info Node: (slib.info)Construction of Weight-Balanced Trees
(slib.info)Construction of Weight-Balanced Trees
Construction of Weight-Balanced Trees
-------------------------------------
Binary trees require there to be a total order on the keys used to
arrange the elements in the tree. Weight balanced trees are organized
by _types_, where the type is an object encapsulating the ordering
relation. Creating a tree is a two-stage process. First a tree type
must be created from the predicate which gives the ordering. The tree
type is then used for making trees, either empty or singleton trees or
trees from other aggregate structures like association lists. Once
created, a tree `knows' its type and the type is used to test
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.
- procedure+: make-wt-tree-type key<?
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':
(key<? a a) => #f
(and (key<? a b) (key<? b a)) => #f
(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'.
- variable+: number-wt-type
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 <))
- variable+: string-wt-type
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<?))
- procedure+: make-wt-tree wt-tree-type
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.
- procedure+: singleton-wt-tree wt-tree-type key datum
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 weight balanced tree type
obtained by calling `make-wt-tree-type'; the returned tree has
this type.
- procedure+: alist->wt-tree tree-type alist
Returns a newly allocated weight-balanced tree that contains the
same associations as ALIST. This procedure is equivalent to:
(lambda (type alist)
(let ((tree (make-wt-tree type)))
(for-each (lambda (association)
(wt-tree/add! tree
(car association)
(cdr association)))
alist)
tree))