BalancedBinaryTree SΒΆ

tree.spad line 492

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

Aggregate

BasicType

BinaryRecursiveAggregate S

BinaryTreeCategory S

CoercibleTo OutputForm

Evalable S if S has Evalable S

finiteAggregate

HomogeneousAggregate S

InnerEvalable(S, S) if S has Evalable S

RecursiveAggregate S

SetCategory

shallowlyMutable