Initial population.

1 files changed, 104 insertions, 0 deletions

diff --git a/src/hyper/pages/BSTREE.ht b/src/hyper/pages/BSTREE.ht
new file mode 100644
index 00000000..8ae762dc
--- /dev/null
+++ b/src/hyper/pages/BSTREE.ht
@@ -0,0 +1,104 @@
+% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
+% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
+\newcommand{\BinarySearchTreeXmpTitle}{BinarySearchTree}
+\newcommand{\BinarySearchTreeXmpNumber}{9.5}
+%
+% =====================================================================
+\begin{page}{BinarySearchTreeXmpPage}{9.5 BinarySearchTree}
+% =====================================================================
+\beginscroll
+\spadtype{BinarySearchTree(R)} is the domain of binary trees with
+%-% \HDindex{tree!binary search}{BinarySearchTreeXmpPage}{9.5}{BinarySearchTree}
+elements of type \spad{R}, ordered across the nodes of the tree.
+%-% \HDindex{binary search tree}{BinarySearchTreeXmpPage}{9.5}{BinarySearchTree}
+A non-empty binary search tree has a value
+of type \spad{R}, and \spadfun{right} and \spadfun{left}
+binary search subtrees.
+If a subtree is empty, it is displayed as a period (``.'').
+
+\xtc{
+Define a list of values to be placed across the tree.
+The resulting tree has \spad{8} at the root;
+all other elements are in the left subtree.
+}{
+\spadpaste{lv := [8,3,5,4,6,2,1,5,7]\bound{lv}}
+}
+\xtc{
+A convenient way to create a binary search tree is to
+apply the operation \spadfun{binarySearchTree} to a list of elements.
+}{
+\spadpaste{t := binarySearchTree lv\free{lv}\bound{t}}
+}
+\xtc{
+Another approach is to first create an empty binary search tree of integers.
+}{
+\spadpaste{emptybst := empty()\$BSTREE(INT)\bound{e}}
+}
+\xtc{
+Insert the value \spad{8}.
+This establishes \spad{8} as the root of the binary search tree.
+Values inserted later that are less than \spad{8} get stored in
+the \spadfun{left} subtree, others in the \spadfun{right} subtree.
+}{
+\spadpaste{t1 := insert!(8,emptybst)\free{e}\bound{t1}}
+}
+\xtc{
+Insert the value \spad{3}. This number becomes the root of the
+\spadfun{left} subtree of \spad{t1}.
+For optimal retrieval, it is thus important to insert the
+middle elements first.
+}{
+\spadpaste{insert!(3,t1)\free{t1}}
+}
+\xtc{
+We go back to the original tree \spad{t}.
+The leaves of the binary search tree are those which have empty
+\spadfun{left} and \spadfun{right} subtrees.
+}{
+\spadpaste{leaves t\free{t}}
+}
+\xtc{
+The operation
+\spadfun{split}\spad{(k,t)} returns a \spadgloss{record} containing
+the two subtrees: one with all elements ``less'' than \spad{k},
+another with elements ``greater'' than \spad{k}.
+}{
+\spadpaste{split(3,t)\free{t}}
+}
+\xtc{
+Define \userfun{insertRoot} to insert new elements by
+creating a new node.
+}{
+\spadpaste{insertRoot: (INT,BSTREE INT) -> BSTREE INT\bound{x}}
+}
+\xtc{
+The new node puts the inserted value between its
+``less'' tree and ``greater'' tree.
+}{
+\begin{spadsrc}[\bound{x1}\free{x}]
+insertRoot(x, t) ==
+    a := split(x, t)
+    node(a.less, x, a.greater)
+\end{spadsrc}
+}
+\xtc{
+Function \userfun{buildFromRoot} builds
+a binary search tree from a list of elements \spad{ls}
+and the empty tree \spad{emptybst}.
+}{
+\spadpaste{buildFromRoot ls == reduce(insertRoot,ls,emptybst)\bound{x2}\free{x1 e}}
+}
+\xtc{
+Apply this to the reverse of the list \spad{lv}.
+}{
+\spadpaste{rt := buildFromRoot reverse lv\bound{rt}\free{lv x2}}
+}
+\xtc{
+Have \Language{} check that these are equal.
+}{
+\spadpaste{(t = rt)@Boolean\free{rt t}}
+}
+\endscroll
+\autobuttons
+\end{page}
+%