$SPAD/src/input bstree.input

Timothy Daly December 3, 2016

Abstract

Contents

2

1 License

— license —

--Copyright The Numerical Algorithms Group Limited 1991.

———-

— * —

)set break resume
)spool bstree.output
)set message test on
)set message auto off
)clear all
--S 1 of 12
lv := [8,3,5,4,6,2,1,5,7]
--R
--R
--R   (1)  [8,3,5,4,6,2,1,5,7]
--R                                                  Type: List(PositiveInteger)
--E 1
--S 2 of 12
t := binarySearchTree lv
--R
--R
--R   (2)  [[[1,2,.],3,[4,5,[5,6,7]]],8,.]
--R                                      Type: BinarySearchTree(PositiveInteger)
--E 2
--S 3 of 12
emptybst := empty()$BSTREE(INT)
--R
--R
--R   (3)  []
--R                                              Type: BinarySearchTree(Integer)
--E 3
--S 4 of 12
t1 := insert!(8,emptybst)
--R
--R
--R   (4)  8
--R                                              Type: BinarySearchTree(Integer)
--E 4
--S 5 of 12
insert!(3,t1)

--R
--R
--R   (5)  [3,8,.]
--R                                              Type: BinarySearchTree(Integer)
--E 5
--S 6 of 12
leaves t
--R
--R
--R   (6)  [1,4,5,7]
--R                                                  Type: List(PositiveInteger)
--E 6
--S 7 of 12
split(3,t)
--R
--R
--R   (7)  [less= [1,2,.],greater= [[.,3,[4,5,[5,6,7]]],8,.]]
--IType: Record(less: BinarySearchTree PositiveInteger,greater: ...
--E 7
--S 8 of 12
insertRoot: (INT,BSTREE INT) -> BSTREE INT
--R
--R                                                                   Type: Void
--E 8
--S 9 of 12
insertRoot(x, t) ==
    a := split(x, t)
    node(a.less, x, a.greater)
--R
--R                                                                   Type: Void
--E 9
--S 10 of 12
buildFromRoot ls == reduce(insertRoot,ls,emptybst)
--R
--R                                                                   Type: Void
--E 10
--S 11 of 12
rt := buildFromRoot reverse lv
--R
--R   Compiling function buildFromRoot with type List(PositiveInteger) ->
--R      BinarySearchTree(Integer)
--R   Compiling function insertRoot with type (Integer,BinarySearchTree(
--R      Integer)) -> BinarySearchTree(Integer)
--R

--R   (11)  [[[1,2,.],3,[4,5,[5,6,7]]],8,.]
--R                                              Type: BinarySearchTree(Integer)
--E 11
--S 12 of 12
(t = rt)@Boolean
--R
--R
--R   (12)  true
--R                                                                Type: Boolean
--E 12
)spool
)lisp (bye)

———-

References^{[1] nothing}

6