
\problemdata     
{computation-9}           
{computation, recursive definitions, search trees}              
{}              
{S02 in-class Week 5} 		
{S02 Meyer}        	
\newcommand{\ms}[1]{\mathop{\text{#1}}}
\providecommand{\ide}{\ms{id}}
\providecommand{\EF}{\ms{F18}}
\providecommand{\T}{\ms{ST}}
\providecommand{\leaves}{\ms{leaves}}
\providecommand{\nodes}{\ms{nodes}}
\providecommand{\makeb}{\ms{makeboth}}
\newcommand{\membern}{\ms{member}}
\newcommand{\makeleft}{\ms{makeleft}}
\newcommand{\makeright}{\ms{makeright}}
\newcommand{\deriv}{\frac{d}{dx}}
\renewcommand{\paren}[1]{\left(#1\right)}
\newcommand{\setl}{\mathbb{L}}
\newcommand{\setlone}{\mathbb{\ell}_1}
\newcommand{\setltwo}{\mathbb{\ell}_2}




\begin{problem} 
We define the family $\T$ of \emph{search trees} as follows:
\begin{enumerate}
\item  Any single number $x$ is in $\T$.
\item  If $T$ and $T'$ are in $\T$, and a number $x$ is larger than every
number in $T$ but smaller than every number in $T'$, then the structure
$\makeb(T,x,T')$ formed by attaching a left-pointing arrow from $x$ to
$T$ and a right-pointing arrow from $x$ to $T'$ is also in $\T$. See
Figure \ref{fig:searchtree}
\end{enumerate}

\begin{figure}[h]
\begin{center}
\input{../figures/cp5F-searchtree.latex}
\end{center}
\caption{Creating a new search tree by applying rule 2}
\label{fig:searchtree}
\end{figure}


The number $x$ is called the \emph{root} of the tree that is formed.

\begin{problemparts}

\problempart Draw all the different search trees in $\T$ that have nodes
1, 2, 3, 4, 5.


\solution{
See Figure \ref{fig:possibilities}
%(1 2 (4 3 5)) and ((1 3 2) 4 5).

\begin{figure}[h]
\begin{center}
\input{../figures/cp5F-st.latex}
\end{center}
\caption{The two possible search trees}
\label{fig:possibilities}
\end{figure}

}

\ppart
Define a function $\membern:\naturals \cross \T \to \set{0,1}$
recursively as follows:
\begin{eqnarray}
\membern(n,n)  & \eqdef & 1,\\
\membern(n,m)  & \eqdef & 0, \text{ for } n \neq m \in \naturals,\\
\membern(n,\makeb(T,n,T')) & \eqdef & 1,\\
\membern(n,\makeb(T,m,T')) & \eqdef & \membern(n,T)) \text{ for } n < m,\label{mn<}\\
\membern(n,\makeb(T,m,T')) & \eqdef & \membern(n,T')) \text{ for } n > m.
\end{eqnarray}

Prove that
\[
\membern(n,T) = 1 \iff n \in \nodes(T).
\]

\solution{
\begin{proof}
Note that we are asked to prove \emph{both} directions! ($\iff$). The
proof will be by structural induction on the definition of $\T$. 
\begin{description}
\item[Base Case:] $|T|=1$. The tree has only one node
representing a natural number $t$. 
\begin{description}
\item[($\Longleftarrow$)]If $n\in \nodes(T)$ then $n=t$ and so by rule
(1), $\membern(n,t)=1$.
\item[($\Longrightarrow$)]If $\membern(n,t)=1$ then, by rule (2), it is
impossible to have  $n\neq t$ because in that case
$\membern(n,t)=0$. Therefore, $n=t$ and so $n \in \nodes(T)$
\end{description}

\item[Induction Step:] There is only one operation to consider, namely $\makeb(T,x,T')$. Assume that
\begin{eqnarray*}
\membern(n,T) = 1 \iff n \in \nodes(T),\label{mnT}\\
\membern(n,T') = 1 \iff n \in \nodes(T')
\end{eqnarray*}
to prove
\begin{equation*}
\membern(n,\makeb(T,x,T')) = 1 \iff n \in \nodes(\makeb(T,x,T')).
\end{equation*}
\begin{description}
\item[Case 1: ($n = x$)] Then, by the definiton of ``nodes'' $n \in
\nodes(\makeb(T,x,T'))$. At the same time, $\membern(n,\makeb(T,x,T')) = 1$ by definition of
$\membern$. Notice that there is no if-then statement here. If $n=x$
then both sides of the double implication ($\iff$) have to be true.

\item[Case 2: ($n < x$)] Then $n \in \nodes(\makeb(T,x,T'))$ iff $n \in \nodes(T)
\union \nodes(T')$ by definition of $\nodes$.  But since $\makeb(T,x,T')
\in \T$, we know $x < \min(\nodes(T'))$, so $n \notin \nodes(T')$.
Therefore, $n \in \nodes(\makeb(T,x,T'))$ iff $n \in \nodes(T)$.
By~(\ref{mnT}), $n \in \nodes(T)$ iff $\membern(n,T) =1$.  But
$\membern(n,\makeb(T,x,T')) = \membern(n,T)$ by~(\ref{mn<}), completing
the proof.

\item[Case 3: ($n > x$)] Symmetric to Case 2.
\end{description}
\end{description}
\end{proof}
}

\end{problemparts}
\end{problem}

