# BalancedBinaryTree S¶

tree.spad line 304 [edit on github]

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

- 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

- 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

- 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: % -> %
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.

- 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: % -> %
from BinaryRecursiveAggregate S

- 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