BalancedBinaryTree(S)

tree.spad line 307 [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
any? : (Mapping(Boolean, S), %) -> 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, %) -> NonNegativeInteger
from HomogeneousAggregate(S)
count : (Mapping(Boolean, 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 : (%, S, S) -> % if S has Evalable(S)
from InnerEvalable(S, S)
eval : (%, 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 : (%, List(Equation(S))) -> % if S has Evalable(S)
from Evalable(S)
every? : (Mapping(Boolean, S), %) -> 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 : (Mapping(S, S), %) -> %
from HomogeneousAggregate(S)
map! : (Mapping(S, S), %) -> %
from HomogeneousAggregate(S)
mapDown! : (%, S, Mapping(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, Mapping(List(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. 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! : (%, %, Mapping(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! : (%, Mapping(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 : (Mapping(Boolean, S, S), %) -> 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 : (%, 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)
~= : (%, %) -> Boolean
from BasicType

BinaryRecursiveAggregate(S)

BasicType

RecursiveAggregate(S)

shallowlyMutable

HomogeneousAggregate(S)

SetCategory

Hashable

CoercibleTo(OutputForm)

BinaryTreeCategory(S)

finiteAggregate

InnerEvalable(S, S)

Aggregate

Evalable(S)