\documentclass[11pt]{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}


\newcommand{\floor}[1]{\ensuremath{\lfloor\, #1\,\rfloor}}


\begin{document}



\title{Data Structures - Assignment no. 4, March 21, 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 question where you are required to write
     pseudo-code, also explain your solution in words.
\end{itemize} }}


\begin{enumerate}

\item Insert the keys 25, 33, 9 and 35 to the 2-4+ tree depicted in Figure \ref{fig:24tree}. Then delete keys 10 and 20. Now draw the resulting tree.

\item \begin{enumerate}

\item Give an algorithm that is given a binary tree $T$ of $n$
vertices with keys at the nodes, and determines whether $T$ is
a binary search tree. The algorithm should run in time $O(n)$.
Give: (i) pseudo-code; (ii) an explanation of the algorithm; (iii) an
explanation why it is correct; and (iv) an explanation why
the running time is indeed $O(n)$.

\item Describe an algorithm that given a sorted array of size $n$
builds a 2-4+ tree that contains the same keys as the array.
The algorithm should run in time $O(n)$.
Give: (i) a description of the algorithm; (ii) an
explanation why it is correct; and (iii) an explanation
why the running time is indeed $O(n)$.

\end{enumerate}

\item Consider a 2-4 search tree, where instead of having up to 4 children 
for every node, you have up to $\log n$ children for every node. Suppose 
that each node is kept by a small data structure that can do whichever 
manipulations you like, in constant time.

\begin{enumerate}

\item What is the depth of this tree?

\item What are the running times of the usual operations (insert, 
delete, find) for this tree?

\end{enumerate}

\underline{Note 1:} The assumption that a node can do whichever 
manipulations you like in $O(1)$ time is not very realistic. One way to 
justify it is considering the case where you have a very fast 
subprocessor, capable of handling small amounts of data, but very quickly. 
You program it in advance to perform all the manipulations you like on 
$\log n$-sized nodes.


\underline{Note 2:} You might want to use the 
fact that $\log_a b = \frac{\log a}{\log b}$, so $\log_{\log n} n = 
\frac{\log n}{\log \log n}$.

\item \begin{enumerate}

\item You are given a 2-4+ search tree where the root
has exactly two children, $u$ and $v$. Let $X$ be the
number of descendants of $v$, and $Y$ be the number of
descendants of $u$. (In other words, $X$ is the size of the subtree
of $v$, and $Y$ is the size of the subtree of $u$).
Is it necessarily true that $X \le 2006 \cdot Y$?
Explain your answer.

\item Solve the same question for an R-B tree

%\item Solve the same question for a BB tree, as defined in 
%question \ref{q_size_balanced_tree}.

\end{enumerate}

\item
\label{q_size_balanced_tree}
\textbf{Challange Question. Not to be Submitted.}\\
\textbf{Bounded-Balance Trees.} In a binary tree, define the 
\emph{size} of a vertex $v$, denoted by $S_v$, as the 
number of vertices in $v$'s subtree. A binary search tree is called a 
\emph{bounded-balance (BB)} tree, if for every vertex $v$, it holds that 
$S_{v.left} \ge \floor{\frac{S_v}{10}}$ and $S_{v.right} \ge
\floor{\frac{S_v}{10}}$, where $v.left$ is $v$'s left child, and $v.right$ 
is $v$'s right child.

\begin{enumerate}

\item Prove that if $T$ is a BB tree containing $n$ nodes, 
then the depth of $T$ is $O(\log n)$.

\item We define a BB tree data structure as follows: The 
data structure is a normal binary search tree, with an additional field 
\emph{size} at each vertex. The field $v.size$ holds $S_v$.\\

Consider a sub-tree with root $v$, where $v.left$ and $v.right$ are both 
BB trees, and also $S_v=10x, S_v.right=x-1,S_v.left=9x$. Thus, $v$'s 
subtree is not a BB tree, but there is just one small violation. Show how 
to perform rotations that will correct this violation. (Note: a little 
case-analysis is needed. In a certain case, you may need to perform two 
rotations, not just one).

\item Conclude from the last section that you can perform lookup, 
insertion and deletion in a BB tree, all in time $O(\log n)$.

\end{enumerate}

\end{enumerate}

\begin{figure}[h]
\begin{center}
\scalebox{0.5}{\includegraphics{24tree.eps}} \caption{A 2-4+ tree. (Recall
that a 2-4+ tree is a 2-4 tree where the real set elements
are only the keys that are at the leaves, and the rest of the elements are
just pivot elements to aid in searching.) \label{fig:24tree}}
\end{center}
\end{figure}


\end{document}
