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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
\begin{patch}{BinarySearchTreeXmpPagePatch1}
\begin{paste}{BinarySearchTreeXmpPageFull1}{BinarySearchTreeXmpPageEmpty1}
\pastebutton{BinarySearchTreeXmpPageFull1}{\hidepaste}
\tab{5}\spadcommand{lv := [8,3,5,4,6,2,1,5,7]\bound{lv }}
\indentrel{3}\begin{verbatim}
(1) [8,3,5,4,6,2,1,5,7]
Type: List PositiveInteger
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty1}
\begin{paste}{BinarySearchTreeXmpPageEmpty1}{BinarySearchTreeXmpPagePatch1}
\pastebutton{BinarySearchTreeXmpPageEmpty1}{\showpaste}
\tab{5}\spadcommand{lv := [8,3,5,4,6,2,1,5,7]\bound{lv }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch2}
\begin{paste}{BinarySearchTreeXmpPageFull2}{BinarySearchTreeXmpPageEmpty2}
\pastebutton{BinarySearchTreeXmpPageFull2}{\hidepaste}
\tab{5}\spadcommand{t := binarySearchTree lv\free{lv }\bound{t }}
\indentrel{3}\begin{verbatim}
(2) [[[1,2,.],3,[4,5,[5,6,7]]],8,.]
Type: BinarySearchTree PositiveInteger
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty2}
\begin{paste}{BinarySearchTreeXmpPageEmpty2}{BinarySearchTreeXmpPagePatch2}
\pastebutton{BinarySearchTreeXmpPageEmpty2}{\showpaste}
\tab{5}\spadcommand{t := binarySearchTree lv\free{lv }\bound{t }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch3}
\begin{paste}{BinarySearchTreeXmpPageFull3}{BinarySearchTreeXmpPageEmpty3}
\pastebutton{BinarySearchTreeXmpPageFull3}{\hidepaste}
\tab{5}\spadcommand{emptybst := empty()$BSTREE(INT)\bound{e }}
\indentrel{3}\begin{verbatim}
(3) []
Type: BinarySearchTree Integer
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty3}
\begin{paste}{BinarySearchTreeXmpPageEmpty3}{BinarySearchTreeXmpPagePatch3}
\pastebutton{BinarySearchTreeXmpPageEmpty3}{\showpaste}
\tab{5}\spadcommand{emptybst := empty()$BSTREE(INT)\bound{e }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch4}
\begin{paste}{BinarySearchTreeXmpPageFull4}{BinarySearchTreeXmpPageEmpty4}
\pastebutton{BinarySearchTreeXmpPageFull4}{\hidepaste}
\tab{5}\spadcommand{t1 := insert!(8,emptybst)\free{e }\bound{t1 }}
\indentrel{3}\begin{verbatim}
(4) 8
Type: BinarySearchTree Integer
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty4}
\begin{paste}{BinarySearchTreeXmpPageEmpty4}{BinarySearchTreeXmpPagePatch4}
\pastebutton{BinarySearchTreeXmpPageEmpty4}{\showpaste}
\tab{5}\spadcommand{t1 := insert!(8,emptybst)\free{e }\bound{t1 }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch5}
\begin{paste}{BinarySearchTreeXmpPageFull5}{BinarySearchTreeXmpPageEmpty5}
\pastebutton{BinarySearchTreeXmpPageFull5}{\hidepaste}
\tab{5}\spadcommand{insert!(3,t1)\free{t1 }}
\indentrel{3}\begin{verbatim}
(5) [3,8,.]
Type: BinarySearchTree Integer
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty5}
\begin{paste}{BinarySearchTreeXmpPageEmpty5}{BinarySearchTreeXmpPagePatch5}
\pastebutton{BinarySearchTreeXmpPageEmpty5}{\showpaste}
\tab{5}\spadcommand{insert!(3,t1)\free{t1 }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch6}
\begin{paste}{BinarySearchTreeXmpPageFull6}{BinarySearchTreeXmpPageEmpty6}
\pastebutton{BinarySearchTreeXmpPageFull6}{\hidepaste}
\tab{5}\spadcommand{leaves t\free{t }}
\indentrel{3}\begin{verbatim}
(6) [1,4,5,7]
Type: List PositiveInteger
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty6}
\begin{paste}{BinarySearchTreeXmpPageEmpty6}{BinarySearchTreeXmpPagePatch6}
\pastebutton{BinarySearchTreeXmpPageEmpty6}{\showpaste}
\tab{5}\spadcommand{leaves t\free{t }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch7}
\begin{paste}{BinarySearchTreeXmpPageFull7}{BinarySearchTreeXmpPageEmpty7}
\pastebutton{BinarySearchTreeXmpPageFull7}{\hidepaste}
\tab{5}\spadcommand{split(3,t)\free{t }}
\indentrel{3}\begin{verbatim}
(7)
[less= [1,2,.],greater= [[.,3,[4,5,[5,6,7]]],8,.]]
Type: Record(less: BinarySearchTree PositiveInteger,greater: BinarySearchTree PositiveInteger)
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty7}
\begin{paste}{BinarySearchTreeXmpPageEmpty7}{BinarySearchTreeXmpPagePatch7}
\pastebutton{BinarySearchTreeXmpPageEmpty7}{\showpaste}
\tab{5}\spadcommand{split(3,t)\free{t }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch8}
\begin{paste}{BinarySearchTreeXmpPageFull8}{BinarySearchTreeXmpPageEmpty8}
\pastebutton{BinarySearchTreeXmpPageFull8}{\hidepaste}
\tab{5}\spadcommand{insertRoot: (INT,BSTREE INT) -> BSTREE INT\bound{x }}
\indentrel{3}\begin{verbatim}
Type: Void
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty8}
\begin{paste}{BinarySearchTreeXmpPageEmpty8}{BinarySearchTreeXmpPagePatch8}
\pastebutton{BinarySearchTreeXmpPageEmpty8}{\showpaste}
\tab{5}\spadcommand{insertRoot: (INT,BSTREE INT) -> BSTREE INT\bound{x }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch9}
\begin{paste}{BinarySearchTreeXmpPageFull9}{BinarySearchTreeXmpPageEmpty9}
\pastebutton{BinarySearchTreeXmpPageFull9}{\hidepaste}
\tab{5}\spadcommand{insertRoot(x, t) ==
a := split(x, t)
node(a.less, x, a.greater)
\bound{x1 }\free{x }}
\indentrel{3}\begin{verbatim}
Type: Void
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty9}
\begin{paste}{BinarySearchTreeXmpPageEmpty9}{BinarySearchTreeXmpPagePatch9}
\pastebutton{BinarySearchTreeXmpPageEmpty9}{\showpaste}
\tab{5}\spadcommand{insertRoot(x, t) ==
a := split(x, t)
node(a.less, x, a.greater)
\bound{x1 }\free{x }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch10}
\begin{paste}{BinarySearchTreeXmpPageFull10}{BinarySearchTreeXmpPageEmpty10}
\pastebutton{BinarySearchTreeXmpPageFull10}{\hidepaste}
\tab{5}\spadcommand{buildFromRoot ls == reduce(insertRoot,ls,emptybst)\bound{x2 }\free{x1 e }}
\indentrel{3}\begin{verbatim}
Type: Void
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty10}
\begin{paste}{BinarySearchTreeXmpPageEmpty10}{BinarySearchTreeXmpPagePatch10}
\pastebutton{BinarySearchTreeXmpPageEmpty10}{\showpaste}
\tab{5}\spadcommand{buildFromRoot ls == reduce(insertRoot,ls,emptybst)\bound{x2 }\free{x1 e }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch11}
\begin{paste}{BinarySearchTreeXmpPageFull11}{BinarySearchTreeXmpPageEmpty11}
\pastebutton{BinarySearchTreeXmpPageFull11}{\hidepaste}
\tab{5}\spadcommand{rt := buildFromRoot reverse lv\bound{rt }\free{lv x2 }}
\indentrel{3}\begin{verbatim}
(11) [[[1,2,.],3,[4,5,[5,6,7]]],8,.]
Type: BinarySearchTree Integer
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty11}
\begin{paste}{BinarySearchTreeXmpPageEmpty11}{BinarySearchTreeXmpPagePatch11}
\pastebutton{BinarySearchTreeXmpPageEmpty11}{\showpaste}
\tab{5}\spadcommand{rt := buildFromRoot reverse lv\bound{rt }\free{lv x2 }}
\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPagePatch12}
\begin{paste}{BinarySearchTreeXmpPageFull12}{BinarySearchTreeXmpPageEmpty12}
\pastebutton{BinarySearchTreeXmpPageFull12}{\hidepaste}
\tab{5}\spadcommand{(t = rt)@Boolean\free{rt t }}
\indentrel{3}\begin{verbatim}
(12) true
Type: Boolean
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}
\begin{patch}{BinarySearchTreeXmpPageEmpty12}
\begin{paste}{BinarySearchTreeXmpPageEmpty12}{BinarySearchTreeXmpPagePatch12}
\pastebutton{BinarySearchTreeXmpPageEmpty12}{\showpaste}
\tab{5}\spadcommand{(t = rt)@Boolean\free{rt t }}
\end{paste}\end{patch}
|
