/usr/share/axiom-20170501/src/algebra/BSTREE.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | )abbrev domain BSTREE BinarySearchTree
++ Author: Mark Botch
++ Description:
++ \spad{BinarySearchTree(S)} is the domain of
++ a 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
++ right and left which are both \spad{BinaryTree(S)}
++ Elements are ordered across the tree.
BinarySearchTree(S) : SIG == CODE where
S : OrderedSet
SIG ==> BinaryTreeCategory(S) with
shallowlyMutable
finiteAggregate
binarySearchTree : List S -> %
++ binarySearchTree(l) is not documented
++
++X binarySearchTree [1,2,3,4]
insert_! : (S,%) -> %
++ insert!(x,b) inserts element x as leaves into binary search tree b.
++
++X t1:=binarySearchTree [1,2,3,4]
++X insert!(5,t1)
insertRoot_! : (S,%) -> %
++ insertRoot!(x,b) inserts element x as a root of binary search tree b.
++
++X t1:=binarySearchTree [1,2,3,4]
++X insertRoot!(5,t1)
split : (S,%) -> Record(less: %, greater: %)
++ split(x,b) splits binary tree b into two trees, one with elements
++ greater than x, the other with elements less than x.
++
++X t1:=binarySearchTree [1,2,3,4]
++X split(3,t1)
CODE ==> BinaryTree(S) add
Rep := BinaryTree(S)
binarySearchTree(u:List S) ==
null u => empty()
tree := binaryTree(first u)
for x in rest u repeat insert_!(x,tree)
tree
insert_!(x,t) ==
empty? t => binaryTree(x)
x >= value t =>
setright_!(t,insert_!(x,right t))
t
setleft_!(t,insert_!(x,left t))
t
split(x,t) ==
empty? t => [empty(),empty()]
x > value t =>
a := split(x,right t)
[node(left t, value t, a.less), a.greater]
a := split(x,left t)
[a.less, node(a.greater, value t, right t)]
insertRoot_!(x,t) ==
a := split(x,t)
node(a.less, x, a.greater)
|