# BalancedBinaryTree S¶

- S: SetCategory

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
- from CoercibleTo 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) -> %
- from BinaryRecursiveAggregate S
- elt: (%, right) -> %
- from BinaryRecursiveAggregate S
- elt: (%, value) -> S
- from RecursiveAggregate S
- empty: () -> %
- from Aggregate
- empty?: % -> Boolean
- 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
- from SetCategory
- hashUpdate!: (HashState, %) -> HashState
- from SetCategory
- latex: % -> String
- from SetCategory
- leaf?: % -> Boolean
- from RecursiveAggregate S
- leaves: % -> List S
- from RecursiveAggregate S
- left: % -> %
- from BinaryRecursiveAggregate S
- 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.- member?: (S, %) -> Boolean
- from HomogeneousAggregate S
- members: % -> List S
- from HomogeneousAggregate S
- more?: (%, NonNegativeInteger) -> Boolean
- from Aggregate
- node: (%, S, %) -> %
- from BinaryTreeCategory S
- node?: (%, %) -> Boolean
- from RecursiveAggregate S
- nodes: % -> List %
- from RecursiveAggregate S
- parts: % -> List S
- from HomogeneousAggregate S
- right: % -> %
- from BinaryRecursiveAggregate S
- sample: %
- from Aggregate
- setchildren!: (%, List %) -> %
- from RecursiveAggregate S
- setelt!: (%, left, %) -> %
- from BinaryRecursiveAggregate S
- setelt!: (%, right, %) -> %
- from BinaryRecursiveAggregate S
- 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!: (%, %) -> %
- from BinaryRecursiveAggregate S
- setright!: (%, %) -> %
- from BinaryRecursiveAggregate S
- setvalue!: (%, S) -> S
- from RecursiveAggregate S
- size?: (%, NonNegativeInteger) -> Boolean
- from Aggregate
- value: % -> S
- from RecursiveAggregate S

Evalable S if S has Evalable S

InnerEvalable(S, S) if S has Evalable S