BinarySearchTree(S)

tree.spad line 233 [edit on github]

BinarySearchTree(S) is the domain of binary trees where elements are ordered across the tree. A binary search tree is either empty or has a value which is an S, and a left and a right which are both BinarySearchTree(S).

# : % -> NonNegativeInteger
from Aggregate
= : (%, %) -> Boolean
from BasicType
any? : (Mapping(Boolean, S), %) -> Boolean
from HomogeneousAggregate(S)
binarySearchTree : List(S) -> %

binarySearchTree(l) constructs a binary search tree with elements from list l.

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
insert! : (S, %) -> %

insert!(x, b) inserts element x as a leave into binary search tree b.

insertRoot! : (S, %) -> %

insertRoot!(x, b) inserts element x as the root of binary search tree b.

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)
max : % -> S
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
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)
setleft! : (%, %) -> %
from BinaryRecursiveAggregate(S)
setright! : (%, %) -> %
from BinaryRecursiveAggregate(S)
setvalue! : (%, S) -> S
from RecursiveAggregate(S)
size? : (%, NonNegativeInteger) -> Boolean
from Aggregate
split : (S, %) -> Record(less : %, greater : %)

split(x, b) splits binary search tree b into two trees, one with elements less than x, the other with elements greater than or equal to x.

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)