(pfds bounded-balance-tree)

Note: For all procedures which take a key as an argument, the key must be comparable with the ordering procedure of the bbtree. bbtree? : any -> bool returns #t if the argument is a bbtree, #f otherwise bbtree-ordering-procedure : bbtree -> (any any -> bool) returns the ordering procedure used internally to order the bbtree.

(make-bbtree <)

make-bbtree : (any -> any -> boolean) -> bbtree returns an empty bbtree. bbtrees derived from this one will use the procedure argument for ordering keys.

(bbtree-size bbtree)

bbtree-size : bbtree -> non-negative integer returns the number of elements in a bbtree

(bbtree-ref . args)

bbtree-ref : bbtree any [any] -> any returns the value associated with the key in the bbtree. If the value is not in the tree, then, if the optional third argument is passed, it is returned, otherwise an error is raised.

(bbtree-set bbtree key value)

bbtree-set : bbtree any any -> bbtree returns a new bbtree with the key associated with the value. If the key is already in the bbtree, its associated value is replaced with the new value in the returned bbtree.

(bbtree-update bbtree key proc default)

bbtree-update : bbtree any (any -> any) any -> bbtree returns a new bbtree with the value associated with the key updated according to the update procedure. If the key was not already in the bbtree, the update procedure is called on the default value, and the association is added to the bbtree.

(bbtree-delete bbtree key)

bbtree-delete : bbtree any -> bbtree returns a new bbtree with the key and its associated value removed. If the key is not in the bbtree, the returned bbtree is a copy of the original

(bbtree-contains? bbtree key)

bbtree-contains? : bbtree any -> boolean returns #t if there is association for key in the bbtree, false otherwise

(bbtree-traverse traverser base bbtree)

bbtree-traverse : (any any (any -> any) (any -> any) any) any bbtree -> any A general tree traversal procedure. Returns the value of applying the traverser procedure to the current node's key, value, a procedure to traverse the left subtree, a procedure to traverse the right subtree, and a base value. The subtree traversal procedures both take a base argument, and call bbtree-traverse recursively on the appropriate subtree. It is mostly useful for implementing other, more specific tree traversal procedures. For example, (define (l-to-r-pre-order cons base bbtree) (bbtree-traverse (lambda (key value left right base) (right (left (cons key value base)))) base bbtree)) implements a left-to-right pre-order traversal variant of bbtree-fold

(bbtree-fold combine base bbtree)

bbtree-fold : (any any any -> any) any bbtree -> any returns the value obtained by the iterating the combine procedure over each node in the tree. The combine procedure takes three arguments, the key and value of the current node, and an accumulator value, and its return value is used as the accumulator value for the next node. The initial accumulator value is provided by the base argument. bbtree-fold performs an left-to-right in-order traversal or "minimum key to maximum key".

(bbtree-fold-right combine base bbtree)

bbtree-fold-right : (any any any -> any) any bbtree -> any like bbtree-fold, but it performs a right-to-left in-order traversal instead (i.e. maximum to minimum).

(bbtree-map mapper bbtree)

bbtree-map : (any -> any) bbtree -> bbtree returns the tree obtained by updating the value of each node with the result of applying the procedure to its value.

(bbtree->alist bbtree)

bbtree->alist : bbtree -> Listof(Pairs) returns the key value associations of the bbtree as a list of pairs. The list returned is in sorted order according to the ordering procedure of the bbtree. A consequence of this is that one could write a sort procedure for lists of pairs as (define (alist-sort alist <) (bbtree->alist (alist->bbtree alist <)))

(alist->bbtree lst <)

alist->bbtree : Listof(Pairs) -> (any any -> boolean) -> bbtree returns the bbtree containing each of the key value pairs in the alist, using the < argument as the ordering procedure.

(bbtree-keys bbtree)

bbtree-keys : bbtree -> Listof(any) returns a list containing all the keys of the bbtree. The keys are sorted according to the bbtree's ordering procedure.

(bbtree-union bbtree1 bbtree2)

bbtree-union : bbtree bbtree -> bbtree returns a bbtree containing the union of the associations in bbtree1 and bbtree2. Where the same key occurs in both, the value in bbtree1 is preferred.

(bbtree-difference bbtree1 bbtree2)

bbtree-difference : bbtree bbtree -> bbtree returns a bbtree containing the all the associations in bbtree1, which do not occur in bbtree2.

(bbtree-intersection bbtree1 bbtree2)

bbtree-intersection : bbtree bbtree -> bbtree returns a bbtree containing all the associations which appear in both bbtree1 and bbtree2. The value in bbtree1 are preferred over those in bbtree2.

(bbtree-index bbtree key)

bbtree-index bbtree any -> non-negative integer returns the index of the key in the bbtree. Index is an integer between 0 and size - 1, with the a key having a lower index than another if first-key < second-key, according to the bbtree ordering procedure.

(bbtree-ref/index bbtree idx)

bbtree-ref/index bbtree non-negative-integer -> any any returns the key and value of the association in the bbtree at the given index.