1\begin{patch}{BinarySearchTreeXmpPagePatch1}
2\begin{paste}{BinarySearchTreeXmpPageFull1}{BinarySearchTreeXmpPageEmpty1}
3\pastebutton{BinarySearchTreeXmpPageFull1}{\hidepaste}
4\tab{5}\spadcommand{lv := [8,3,5,4,6,2,1,5,7]\bound{lv }}
5\indentrel{3}\begin{verbatim}
6   (1)  [8, 3, 5, 4, 6, 2, 1, 5, 7]
7                            Type: List(PositiveInteger)
8\end{verbatim}
9\indentrel{-3}\end{paste}\end{patch}
10
11\begin{patch}{BinarySearchTreeXmpPageEmpty1}
12\begin{paste}{BinarySearchTreeXmpPageEmpty1}{BinarySearchTreeXmpPagePatch1}
13\pastebutton{BinarySearchTreeXmpPageEmpty1}{\showpaste}
14\tab{5}\spadcommand{lv := [8,3,5,4,6,2,1,5,7]\bound{lv }}
15\end{paste}\end{patch}
16
17\begin{patch}{BinarySearchTreeXmpPagePatch2}
18\begin{paste}{BinarySearchTreeXmpPageFull2}{BinarySearchTreeXmpPageEmpty2}
19\pastebutton{BinarySearchTreeXmpPageFull2}{\hidepaste}
20\tab{5}\spadcommand{t := binarySearchTree lv\free{lv }\bound{t }}
21\indentrel{3}\begin{verbatim}
22   (2)  [[[1, 2, .], 3, [4, 5, [5, 6, 7]]], 8, .]
23                Type: BinarySearchTree(PositiveInteger)
24\end{verbatim}
25\indentrel{-3}\end{paste}\end{patch}
26
27\begin{patch}{BinarySearchTreeXmpPageEmpty2}
28\begin{paste}{BinarySearchTreeXmpPageEmpty2}{BinarySearchTreeXmpPagePatch2}
29\pastebutton{BinarySearchTreeXmpPageEmpty2}{\showpaste}
30\tab{5}\spadcommand{t := binarySearchTree lv\free{lv }\bound{t }}
31\end{paste}\end{patch}
32
33\begin{patch}{BinarySearchTreeXmpPagePatch3}
34\begin{paste}{BinarySearchTreeXmpPageFull3}{BinarySearchTreeXmpPageEmpty3}
35\pastebutton{BinarySearchTreeXmpPageFull3}{\hidepaste}
36\tab{5}\spadcommand{emptybst := empty()$BSTREE(INT)\bound{e }}
37\indentrel{3}\begin{verbatim}
38   (3)  []
39                        Type: BinarySearchTree(Integer)
40\end{verbatim}
41\indentrel{-3}\end{paste}\end{patch}
42
43\begin{patch}{BinarySearchTreeXmpPageEmpty3}
44\begin{paste}{BinarySearchTreeXmpPageEmpty3}{BinarySearchTreeXmpPagePatch3}
45\pastebutton{BinarySearchTreeXmpPageEmpty3}{\showpaste}
46\tab{5}\spadcommand{emptybst := empty()$BSTREE(INT)\bound{e }}
47\end{paste}\end{patch}
48
49\begin{patch}{BinarySearchTreeXmpPagePatch4}
50\begin{paste}{BinarySearchTreeXmpPageFull4}{BinarySearchTreeXmpPageEmpty4}
51\pastebutton{BinarySearchTreeXmpPageFull4}{\hidepaste}
52\tab{5}\spadcommand{t1 := insert!(8,emptybst)\free{e }\bound{t1 }}
53\indentrel{3}\begin{verbatim}
54   (4)  8
55                        Type: BinarySearchTree(Integer)
56\end{verbatim}
57\indentrel{-3}\end{paste}\end{patch}
58
59\begin{patch}{BinarySearchTreeXmpPageEmpty4}
60\begin{paste}{BinarySearchTreeXmpPageEmpty4}{BinarySearchTreeXmpPagePatch4}
61\pastebutton{BinarySearchTreeXmpPageEmpty4}{\showpaste}
62\tab{5}\spadcommand{t1 := insert!(8,emptybst)\free{e }\bound{t1 }}
63\end{paste}\end{patch}
64
65\begin{patch}{BinarySearchTreeXmpPagePatch5}
66\begin{paste}{BinarySearchTreeXmpPageFull5}{BinarySearchTreeXmpPageEmpty5}
67\pastebutton{BinarySearchTreeXmpPageFull5}{\hidepaste}
68\tab{5}\spadcommand{insert!(3,t1)\free{t1 }}
69\indentrel{3}\begin{verbatim}
70   (5)  [3, 8, .]
71                        Type: BinarySearchTree(Integer)
72\end{verbatim}
73\indentrel{-3}\end{paste}\end{patch}
74
75\begin{patch}{BinarySearchTreeXmpPageEmpty5}
76\begin{paste}{BinarySearchTreeXmpPageEmpty5}{BinarySearchTreeXmpPagePatch5}
77\pastebutton{BinarySearchTreeXmpPageEmpty5}{\showpaste}
78\tab{5}\spadcommand{insert!(3,t1)\free{t1 }}
79\end{paste}\end{patch}
80
81\begin{patch}{BinarySearchTreeXmpPagePatch6}
82\begin{paste}{BinarySearchTreeXmpPageFull6}{BinarySearchTreeXmpPageEmpty6}
83\pastebutton{BinarySearchTreeXmpPageFull6}{\hidepaste}
84\tab{5}\spadcommand{leaves t\free{t }}
85\indentrel{3}\begin{verbatim}
86   (6)  [1, 4, 5, 7]
87                            Type: List(PositiveInteger)
88\end{verbatim}
89\indentrel{-3}\end{paste}\end{patch}
90
91\begin{patch}{BinarySearchTreeXmpPageEmpty6}
92\begin{paste}{BinarySearchTreeXmpPageEmpty6}{BinarySearchTreeXmpPagePatch6}
93\pastebutton{BinarySearchTreeXmpPageEmpty6}{\showpaste}
94\tab{5}\spadcommand{leaves t\free{t }}
95\end{paste}\end{patch}
96
97\begin{patch}{BinarySearchTreeXmpPagePatch7}
98\begin{paste}{BinarySearchTreeXmpPageFull7}{BinarySearchTreeXmpPageEmpty7}
99\pastebutton{BinarySearchTreeXmpPageFull7}{\hidepaste}
100\tab{5}\spadcommand{split(3,t)\free{t }}
101\indentrel{3}\begin{verbatim}
102   (7)
103   [less = [1, 2, .],
104    greater = [[., 3, [4, 5, [5, 6, 7]]], 8, .]]
105Type: Record(less: BinarySearchTree(PositiveInteger),greater: BinarySearchTree(PositiveInteger))
106\end{verbatim}
107\indentrel{-3}\end{paste}\end{patch}
108
109\begin{patch}{BinarySearchTreeXmpPageEmpty7}
110\begin{paste}{BinarySearchTreeXmpPageEmpty7}{BinarySearchTreeXmpPagePatch7}
111\pastebutton{BinarySearchTreeXmpPageEmpty7}{\showpaste}
112\tab{5}\spadcommand{split(3,t)\free{t }}
113\end{paste}\end{patch}
114
115\begin{patch}{BinarySearchTreeXmpPagePatch8}
116\begin{paste}{BinarySearchTreeXmpPageFull8}{BinarySearchTreeXmpPageEmpty8}
117\pastebutton{BinarySearchTreeXmpPageFull8}{\hidepaste}
118\tab{5}\spadcommand{insertRoot: (INT,BSTREE INT) -> BSTREE INT\bound{x }}
119\indentrel{3}\begin{verbatim}
120                                             Type: Void
121\end{verbatim}
122\indentrel{-3}\end{paste}\end{patch}
123
124\begin{patch}{BinarySearchTreeXmpPageEmpty8}
125\begin{paste}{BinarySearchTreeXmpPageEmpty8}{BinarySearchTreeXmpPagePatch8}
126\pastebutton{BinarySearchTreeXmpPageEmpty8}{\showpaste}
127\tab{5}\spadcommand{insertRoot: (INT,BSTREE INT) -> BSTREE INT\bound{x }}
128\end{paste}\end{patch}
129
130\begin{patch}{BinarySearchTreeXmpPagePatch9}
131\begin{paste}{BinarySearchTreeXmpPageFull9}{BinarySearchTreeXmpPageEmpty9}
132\pastebutton{BinarySearchTreeXmpPageFull9}{\hidepaste}
133\tab{5}\spadcommand{insertRoot(x, t) ==
134    a := split(x, t)
135    node(a.less, x, a.greater)
136\bound{x1 }\free{x }}
137\indentrel{3}\begin{verbatim}
138                                             Type: Void
139\end{verbatim}
140\indentrel{-3}\end{paste}\end{patch}
141
142\begin{patch}{BinarySearchTreeXmpPageEmpty9}
143\begin{paste}{BinarySearchTreeXmpPageEmpty9}{BinarySearchTreeXmpPagePatch9}
144\pastebutton{BinarySearchTreeXmpPageEmpty9}{\showpaste}
145\tab{5}\spadcommand{insertRoot(x, t) ==
146    a := split(x, t)
147    node(a.less, x, a.greater)
148\bound{x1 }\free{x }}
149\end{paste}\end{patch}
150
151\begin{patch}{BinarySearchTreeXmpPagePatch10}
152\begin{paste}{BinarySearchTreeXmpPageFull10}{BinarySearchTreeXmpPageEmpty10}
153\pastebutton{BinarySearchTreeXmpPageFull10}{\hidepaste}
154\tab{5}\spadcommand{buildFromRoot ls == reduce(insertRoot,ls,emptybst)\bound{x2 }\free{x1 e }}
155\indentrel{3}\begin{verbatim}
156                                             Type: Void
157\end{verbatim}
158\indentrel{-3}\end{paste}\end{patch}
159
160\begin{patch}{BinarySearchTreeXmpPageEmpty10}
161\begin{paste}{BinarySearchTreeXmpPageEmpty10}{BinarySearchTreeXmpPagePatch10}
162\pastebutton{BinarySearchTreeXmpPageEmpty10}{\showpaste}
163\tab{5}\spadcommand{buildFromRoot ls == reduce(insertRoot,ls,emptybst)\bound{x2 }\free{x1 e }}
164\end{paste}\end{patch}
165
166\begin{patch}{BinarySearchTreeXmpPagePatch11}
167\begin{paste}{BinarySearchTreeXmpPageFull11}{BinarySearchTreeXmpPageEmpty11}
168\pastebutton{BinarySearchTreeXmpPageFull11}{\hidepaste}
169\tab{5}\spadcommand{rt := buildFromRoot reverse lv\bound{rt }\free{lv x2 }}
170\indentrel{3}\begin{verbatim}
171   (11)  [[[1, 2, .], 3, [4, 5, [5, 6, 7]]], 8, .]
172                        Type: BinarySearchTree(Integer)
173\end{verbatim}
174\indentrel{-3}\end{paste}\end{patch}
175
176\begin{patch}{BinarySearchTreeXmpPageEmpty11}
177\begin{paste}{BinarySearchTreeXmpPageEmpty11}{BinarySearchTreeXmpPagePatch11}
178\pastebutton{BinarySearchTreeXmpPageEmpty11}{\showpaste}
179\tab{5}\spadcommand{rt := buildFromRoot reverse lv\bound{rt }\free{lv x2 }}
180\end{paste}\end{patch}
181
182\begin{patch}{BinarySearchTreeXmpPagePatch12}
183\begin{paste}{BinarySearchTreeXmpPageFull12}{BinarySearchTreeXmpPageEmpty12}
184\pastebutton{BinarySearchTreeXmpPageFull12}{\hidepaste}
185\tab{5}\spadcommand{(t = rt)@Boolean\free{rt t }}
186\indentrel{3}\begin{verbatim}
187   (12)  true
188                                          Type: Boolean
189\end{verbatim}
190\indentrel{-3}\end{paste}\end{patch}
191
192\begin{patch}{BinarySearchTreeXmpPageEmpty12}
193\begin{paste}{BinarySearchTreeXmpPageEmpty12}{BinarySearchTreeXmpPagePatch12}
194\pastebutton{BinarySearchTreeXmpPageEmpty12}{\showpaste}
195\tab{5}\spadcommand{(t = rt)@Boolean\free{rt t }}
196\end{paste}\end{patch}
197
198