# BalancedBinaryTree S¶

BalancedBinaryTree(S) is the domain of balanced binary trees (bbtree). A balanced binary tree of `2^k` leaves, for some `k > 0`, is symmetric, that is, the left and right subtree of each interior node have identical shape. In general, the left and right subtree of a given node can differ by at most one leaf node.

#: % -> NonNegativeInteger

from Aggregate

=: (%, %) -> Boolean

from BasicType

~=: (%, %) -> Boolean

from BasicType

any?: (S -> Boolean, %) -> Boolean

from HomogeneousAggregate S

balancedBinaryTree: (NonNegativeInteger, S) -> %

`balancedBinaryTree(n, s)` creates a balanced binary tree with `n` nodes each with value `s`.

child?: (%, %) -> Boolean

from RecursiveAggregate S

children: % -> List %

from RecursiveAggregate S

coerce: % -> OutputForm
copy: % -> %

from Aggregate

count: (S -> Boolean, %) -> NonNegativeInteger

from HomogeneousAggregate S

count: (S, %) -> NonNegativeInteger

from HomogeneousAggregate S

cyclic?: % -> Boolean

from RecursiveAggregate S

distance: (%, %) -> Integer

from RecursiveAggregate S

elt: (%, left) -> %
elt: (%, right) -> %
elt: (%, value) -> S

from RecursiveAggregate S

empty?: % -> Boolean

from Aggregate

empty: () -> %

from Aggregate

eq?: (%, %) -> Boolean

from Aggregate

eval: (%, Equation S) -> % if S has Evalable S

from Evalable S

eval: (%, List Equation S) -> % if S has Evalable S

from Evalable S

eval: (%, List S, List S) -> % if S has Evalable S

from InnerEvalable(S, S)

eval: (%, S, S) -> % if S has Evalable S

from InnerEvalable(S, S)

every?: (S -> Boolean, %) -> Boolean

from HomogeneousAggregate S

hash: % -> SingleInteger if S has Hashable

from Hashable

hashUpdate!: (HashState, %) -> HashState if S has Hashable

from Hashable

latex: % -> String

from SetCategory

leaf?: % -> Boolean

from RecursiveAggregate S

leaves: % -> List S

from RecursiveAggregate S

left: % -> %
less?: (%, NonNegativeInteger) -> Boolean

from Aggregate

map!: (S -> S, %) -> %

from HomogeneousAggregate S

map: (S -> S, %) -> %

from HomogeneousAggregate S

mapDown!: (%, S, (S, S) -> S) -> %

`mapDown!(t,p,f)` returns `t` after traversing `t` in “preorder” (node then left then right) fashion replacing the successive interior nodes as follows. The root value `x` is replaced by `q` `:=` `f`(`p`, `x`). The mapDown!(`l`, `q`, `f`) and mapDown!(`r`, `q`, `f`) are evaluated for the left and right subtrees `l` and `r` of `t`.

mapDown!: (%, S, (S, S, S) -> List S) -> %

`mapDown!(t,p,f)` returns `t` after traversing `t` in “preorder” (node then left then right) fashion replacing the successive interior nodes as follows. Let `l` and `r` denote the left and right subtrees of `t`. The root value `x` of `t` is replaced by `p`. Then `f`(value `l`, value `r`, `p`), where `l` and `r` denote the left and right subtrees of `t`, is evaluated producing two values `pl` and `pr`. Then `mapDown!(l, pl, f)` and `mapDown!(l, pr, f)` are evaluated.

mapUp!: (%, %, (S, S, S, S) -> S) -> %

`mapUp!(t,t1,f)` traverses `t` in an “endorder” (left then right then node) fashion returning `t` with the value at each successive interior node of `t` replaced by `f`(`l`, `r`, `l1`, `r1`) where `l` and `r` are the values at the immediate left and right nodes. Values `l1` and `r1` are values at the corresponding nodes of a balanced binary tree `t1`, of identical shape at `t`.

mapUp!: (%, (S, S) -> S) -> S

`mapUp!(t,f)` traverses balanced binary tree `t` in an “endorder” (left then right then node) fashion returning `t` with the value at each successive interior node of `t` replaced by `f`(`l`, `r`) where `l` and `r` are the values at the immediate left and right nodes.

max: % -> S if S has OrderedSet

from HomogeneousAggregate S

max: ((S, S) -> Boolean, %) -> S

from HomogeneousAggregate S

member?: (S, %) -> Boolean

from HomogeneousAggregate S

members: % -> List S

from HomogeneousAggregate S

min: % -> S if S has OrderedSet

from HomogeneousAggregate S

more?: (%, NonNegativeInteger) -> Boolean

from Aggregate

node?: (%, %) -> Boolean

from RecursiveAggregate S

node: (%, S, %) -> %

from BinaryTreeCategory S

nodes: % -> List %

from RecursiveAggregate S

parts: % -> List S

from HomogeneousAggregate S

right: % -> %
sample: %

from Aggregate

setchildren!: (%, List %) -> %

from RecursiveAggregate S

setelt!: (%, left, %) -> %
setelt!: (%, right, %) -> %
setelt!: (%, value, S) -> S

from RecursiveAggregate S

setleaves!: (%, List S) -> %

`setleaves!(t, ls)` sets the leaves of `t` in left-to-right order to the elements of `ls`.

setleft!: (%, %) -> %
setright!: (%, %) -> %
setvalue!: (%, S) -> S

from RecursiveAggregate S

size?: (%, NonNegativeInteger) -> Boolean

from Aggregate

value: % -> S

from RecursiveAggregate S

Aggregate

BasicType

Evalable S if S has Evalable S

finiteAggregate

Hashable if S has Hashable

InnerEvalable(S, S) if S has Evalable S

SetCategory

shallowlyMutable