BalancedBinaryTree S

tree.spad line 304 [edit on github]

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

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

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

Aggregate

BasicType

BinaryRecursiveAggregate S

BinaryTreeCategory S

CoercibleTo OutputForm

Evalable S if S has Evalable S

finiteAggregate

Hashable if S has Hashable

HomogeneousAggregate S

InnerEvalable(S, S) if S has Evalable S

RecursiveAggregate S

SetCategory

shallowlyMutable