% 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}
%