\documentstyle[12pt]{article}

\pagestyle{myheadings}
\def\headlineaux{\sc Math 220/317: Programming II/Data Structures\hrulefill}
\markboth{\headlineaux}{\headlineaux}


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

\section*{Quiz\hfill{\parbox{3in}
    {\small\sc\begin{flushright} December 14, 1992. 
       2:00--2:50 PM\end{flushright}}
}}

There are four problems for a total of 100 points.
Show all your work, partial credit will be awarded.
Write in the provided blue books, write and sign your name
on each one. No notes, no collaboration.  Good luck.
\\[.5in]
{\Large Name: \hrulefill}
\\[.5in]

\center{
{\Large
\begin{tabular}{c|c}
Problem & Credit \\ \hline\hline
 1 & \\ \hline
 2 & \\ \hline 
 3 & \\ \hline 
 4 & \\ \hline\hline
 Total & \end{tabular} }}

\begin{enumerate}

\newpage
\item{\samepage (25 Points.)
A {\em single rotation} is a tree operation which has many uses.
This and the following two problems will explore a sample application.
Be sure to take the time to understand the following picture:

\vspace{2.2in}

Pictured is a {\em single rotation} at node $y$. The starting configuration is
on the left. The node $x$ has right child $y$, and
the entire sub-tree to its left is labeled $A$. The entire sub-tree to the
left of $y$ is labeled $B$, the entire sub-tree to the right of $y$ is labeled $C$.
After the rotation, $y$ has been brought up into the position where $x$ was,
$x$ becomes the left child of $y$, and sub-tree $B$ is disconnected from $y$ and
reconnected as the right child of $x$.

A rotation maintains search tree order in the tree.
If you don't see why, don't worry --- we will not need this fact anyway.

There is another form of single rotation when $y$ is the left child of some node:

\vspace{2.2in}

\begin{itemize}
\item Write a program that implements single rotation.
\end{itemize}
You can write carefully composed pseudo-code or full Pascal. If you write pseudo-code,
make sure to address all the relevant data-structure issues.

{\sc Hint: } To rotate at some node $w$, you will need to know the parent of
$w$. You might also need to know the grandparent of $w$. You might want to pass all
these things to your procedure.
}

\newpage
\item (25 Points.)
After single rotation, we naturally go on to {\em double rotation}.
There are two forms of double rotation, {\em zig-zag} and {\em zig-zig}.
Fortunately, double rotation can be implemented in terms of two single
rotations, but you must tell me which two single rotations.
\begin{enumerate}
\item Here is a zig-zag at $z$:

\vspace{3.3in}

How do you do this with two single rotations?

\newpage
\item Here is zig-zig at $z$:

\vspace{3.5in}

How do you do this with two single rotations?
\end{enumerate}


\newpage
\item{\samepage (25 Points.)
Suppose we have a nice, binary search tree $T$. For simplicity, all the elements of
the tree are distinct. Given a node $x$ in the tree,
we want to {\em split the tree at $x$}. This means, starting with $T$ and $x$, we
end up with two trees, $T_1$ and $T_2$, such that all nodes with labels less than
the label of $x$ are in
$T_1$ and all nodes with labels greater than the label of $x$ are in $T_2$.

This is simple to do when $x$ is the root.
In this case we just delete the root leaving two trees, the left sub-tree
of the root and the right sub-tree of the root. These would be $T_1$ and $T_2$,
respectively.
\begin{itemize}
\item Given a tree $T$ and a node $x$ in the tree, how do you split the tree
$T$ at $x$ even if $x$ is not the root.
\end{itemize}
{\sc Hint: } Use zig-zig, zig-zag and single rotation.

 }

\newpage
\item{\samepage (25 Points.)
What is the result of two consecutive delete-min's from the following heap:

\newcommand{\heapinPlace}{\center{\Huge{\begin{tabular}{*{8}{|p{.4in}|}}
 \hline  & & & & & & & \\ \hline \end{tabular}}}}
\newcommand{\downto}{\center{$\Downarrow$ {\em delete-min} }}

\heapinPlace

\downto

\heapinPlace

\downto

\heapinPlace

\bigskip\bigskip
The dash means that the array position is empty.
}


\end{enumerate}
\end{document}
