\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{fullpage}

\setlength{\textwidth}{6.5in} \setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in} \setlength{\headsep}{0.0in}
%\setlength{\topsep}{0in}
\setlength{\textheight}{9in} \setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}


%\documentstyle[11pt]{article}
%\usepackage{fullpage}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\pagestyle{empty} \setlength{\textwidth}{6.5in}
%\setlength{\evensidemargin}{0.0in}
%\setlength{\oddsidemargin}{0.0in} \setlength{\topmargin}{-0.25in}
%\setlength{\textheight}{9.0in}
%\setlength{\baselineskip}{1.3\baselineskip}
%\setlength{\parindent}{0in}
%
%\newcommand\qed{\hspace*{\fill} {\large$\Box$}}
%\newcommand\set[1]{\left\{#1\right\}}
%\newcommand\ang[1]{\left\langle #1 \right\rangle}
%\newcommand\brac[1]{{\left[ {#1} \right]}}
%\newcommand\card[1]{\left| #1 \right|}
%\newcommand\inR{{~\in_{\rm R}~}}


\begin{document}



\title{Data Structures - Assignment no. 3, March 14, 2007}

\date{}

\maketitle


\def\lim{\mathop{\rm lim}\nolimits }
\def\true{ {\small\bf TRUE } }
\def\false{ {\small\bf FALSE } }

\vspace{-1.5cm}

 {\small {\bf Remarks:
\begin{itemize}
\item Write both your name and your ID number very clearly on the
top of the exercise. Write your exercises in pen, or in clearly
visible pencil. Please write \emph{very} clearly.

\item Recall that 80\% of the theoretical exercises must be submitted. The
exercises can and must be worked on and submitted alone.

    \item  Give correctness and
        complexity proofs for every algorithm you write.
     \item For every problem, find the most
     efficient algorithm. A non efficient algorithm will be
     considered as an incomplete answer.
     \item For every question where you are required to write
     pseudo-code, also explain your solution in words.
\end{itemize} }}



\begin{enumerate}

\item Define the vertex-depth of a tree to be the distance between its
root and the furthest leaf, measured in vertices, not in edges.
For example, the depth of a tree which contains a single vertex is 1. The 
depth of an empty tree is 0.

A binary search tree is called a \emph{valid AVL tree} if for each
node $v$ the following condition holds: Let $v_1,v_2$ be $v$'s
children. Then we require that the difference between the depth of
the subtree whose root is $v_1$ and the depth of the subtree whose
root is $v_2$ is $-1$, $0$, or $+1$. For example, Figure \ref{fig:avl}
depicts a valid AVL tree (the keys are not listed).

%\footnote{AVL trees are a type
%of balanced search tree. If you are curious, perform a google
%search to get information on this kind of balanced search trees.
%Specifically, for details on how to perform insert and delete
%operations see \cite{avl}. For this question you only need the
%definitions that we gave here.}

\begin{enumerate}

\item \label{item1} Prove that a valid AVL tree of depth $d$ always has at least
$F_d$ vertices, where $F_d$ is the $d$'th Fibonacci number.
($F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}$). (Hint: use induction on $d$).

\item  Let $T$ be a valid AVL tree with $n$ vertices. Prove that the depth 
of $T$ is $O(\log n)$. You may use item $(a)$.

\end{enumerate}

\item The pre-order read of a binary tree is the sequence of elements that are printed by
the following procedure:

\small

\begin{tabbing}
xx \= \kill
\underline{PRE-ORDER(v)}\\
IF (v = null) RETURN\\
ELSE\\
\>   PRINT v.key\\
\>   PRE-ORDER(v.left)\\
\>   PRE-ORDER(v.right)\\
\>   RETURN\\
\end{tabbing}

% \vspace{-0.05cm}


\normalsize

The post-order read of a binary tree is the sequence of elements
that are printed by the following procedure:

\small

\begin{tabbing}
xx \= \kill
\underline{POST-ORDER(v)}\\
IF (v = null) RETURN\\
ELSE\\
\>   POST-ORDER(v.left)\\
\>   POST-ORDER(v.right)\\
\>   PRINT v.key\\
\>   RETURN\\
\end{tabbing}

% \vspace{-0.05cm}

\normalsize

The in-order read of a binary tree is the sequence of elements
that are printed by the following procedure:

\small

\begin{tabbing}
xx \= \kill
\underline{IN-ORDER(v)}\\
IF (v = null) RETURN\\
ELSE\\
\>   IN-ORDER(v.left)\\
\>   PRINT v.key\\
\>   IN-ORDER(v.right)\\
\>   RETURN\\
\end{tabbing}

% \vspace{-0.05cm}

\normalsize

\begin{enumerate}



\item Give a tree with at least 3 nodes (all nodes must have different keys) such that both its
in-order read and its pre-order read are the same, or prove that
there is no such tree.

\item Give a tree with at least 3 nodes (all nodes must have different keys) such that both its
in-order read and its post-order read are the same, or prove that
there is no such tree.

\item Give a tree with at least 3 nodes (all nodes must have different keys) such that both its
pre-order read and its post-order read are the same, or prove that
there is no such tree.

\end{enumerate}

\item In Figure \ref{fig:rbt2_revised} you are shown a Red-Black Tree, 
whose elements are stored at the leaves. (Recall that the values in the 
inner nodes are ``pivot'' elements which are not really elements of the 
data structure, and whose purpose is to allow searching).

In this question, we ask you to insert the keys 20 and 26 to the tree,
then delete key 19, then insert 21,24 and delete 17, and finally
insert 14. Now draw the resulting tree. 

\item Suppose that we start from an empty Red-Black tree, and that
we perform $n$ insert operations, where $n>1$. Prove that we
necessarily end up with a Red-Black tree which has at least one
red vertex. Assume that we are dealing with a Red-Black tree that 
stores its elements at the leaves.\\
(Hint: One way to prove this is: (1) prove that the
second insert operation creates a red node; (2) then prove that
for any insert operation, if there is a red node before applying
it, then there is also a red node after applying it. Note that
there may be other ways to prove the claim.)

\item \textbf{Riddle. Not to be turned in.} Let $T_1,T_2$ be two unlabeled 
binary trees with $n$ nodes each. Prove that there exists a sequence of 
$O(n)$ rotations that tranforms $T_1$ to $T_2$. Is it possible that for 
any two such trees there exists a sequence of $o(n)$ rotations that 
transforms one to the other?\\
\underline{Note:} Remember that in a binary tree there is a difference 
between a left son and a right son -- they are not interchangable. For 
example, a tree consisting of two nodes -- a root and its left son, is 
different from a tree consisting of two nodes -- a root and its right son.

\end{enumerate}

%\begin{thebibliography}{10}
%
%\bibitem{avl}
%\newblock Web page about AVL Trees.
%\newblock http://www.eli.sdsu.edu/courses/fall96/cs660/notes/avl/avl.html.
%
%\end{thebibliography}

\begin{figure}[h]
\begin{center}
\scalebox{0.3}{\includegraphics{avl.eps}}
\end{center} \caption{A valid AVL Tree \label{fig:avl}}
\end{figure}

\vspace{-6cm}

\begin{figure}[h]
\begin{center}
\scalebox{0.35}{\includegraphics{rbt2_revised.eps}} \caption{A red-black
tree with elements at the leaves. (the white nodes are considered red. 
Recall that all leaves are considered black). 
\label{fig:rbt2_revised}}
\end{center}
\end{figure}


\end{document}
