11.7.1 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 that 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))