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