\documentstyle[12pt]{report}
\pagestyle{myheadings}
\def\headlineaux{\sc Math 220/317: Programming II/Data Structures 
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\newcommand{\assignmentNumber}{6}
\newcommand{\outdate}{30 September, 1993}
\newcommand{\duedate}{8 October, 1993}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Problem Set \assignmentNumber \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Out: \outdate
     \\ Due: \duedate\end{flushright}}}}

\subsection*{Goals}
Learning about Trees and Recursion.

\subsection*{Reading Assignment}
Read Chapters 4 and 5 from {\em Algorithms,}
and Chapter 17 from {\em Oh! Pascal!}

\subsection*{Programming Assignment}

Write a program that takes words from an input file
and looks for them in a binary search tree. If found,
a count associated with the word is incremented. If not
found, the word is added to the tree (maintaining the
important search tree order).

Recall that this search tree order is that for any node
$n$ and its left and right children $l$ and $r$, the
word in $l$ comes before the word in $n$ in dictionary
ordering, and the word in $r$ comes after the word in $n$
in dictionary ordering.

Write out the tree using an {\em in-order traversal}. It
could be a recursive routine or a stack based routine ---
your choice. The words will be printed in increasing
dictionary order. You are also {\em required} to write a routine
which prints the tree out pre-order and with indentation
to show its structure. 
For instance, after the file {\em romeo, romeo, wherefore art thou, 
romeo?}, printing the tree would give:
\begin{verbatim}
1  romeo, 3
2      art, 1
3          -
3          -
2      wherefore, 1
3          thou, 1
3          -
\end{verbatim}
(The numbers in the left hand column relate to node depth,
and null children are shown to help differentiate an
only-left-child from an only-right-child.)
Writing this print function is something you will {\em want} to do,
because it is so much fun watching the tree grow word by word.
The most fun is to write a small main program which asks for
one word, inserts it into the tree, prints the tree in the above
form, then asks for another word. When you type ``.''  the program
prints the tree in-order and exits.

Then modify this to form the off-line version which reads
words from a text file, and prints the tree in-order on completion.

\newcommand{\prettysymbol}{\Diamond}
\[ \prettysymbol \hspace{1in} \prettysymbol \hspace{1in} \prettysymbol \]

{\sc Extra Credit:}
Implement deletion for you binary tree. Figuring out a good
way to delete from a binary tree is the most interesting
part of this extra credit.

A ``good'' deletion algorithm will require only small
restructurings of the tree. That is, the run time for a good
deletion algorithm will be proportional to the height of
the tree. 
As an example of a bad deletion algorithm,
consider rebuilding the tree from scratch.
It is a bad algorithm because
it will take time proportional to the
number of items in the tree, which could be much greater than
the tree's height.

To test your program, have it print the tree after each word is
inserted or deleted. A word in the input text is to be
deleted if it begins with a dash. The dash is stripped, and the word,
if found in the tree, is deleted. It need not be an error to ask
to delete a word not found it the tree.
For instance, {\em romeo, romeo, wherefore art thou, -dumb -romeo?} 
might have final tree:
\begin{verbatim}
1  thou, 1
2      art, 1
3          -
3          -
2      wherefore, 1
3          -
3          -
\end{verbatim}
(This is an example, but it is also a hint!)

\end{document}
