# BinarySearchTree SΒΆ

tree.spad line 230 [edit on github]

S: OrderedSet

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

- any?: (S -> Boolean, %) -> 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

- 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

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

- map: (S -> S, %) -> %
from HomogeneousAggregate S

- max: % -> S
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
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

- 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

Evalable S if S has Evalable S

InnerEvalable(S, S) if S has Evalable S