\documentstyle[12pt,fullpage]{article}
%\textwidth 15cm
%\textheight 22cm
\topmargin -1cm
\oddsidemargin -0.2cm
\begin{document}
\parskip
\baselineskip
\bigskip

\begin{center}
{\Large {\bf Data Structures}}
\end{center}
\begin{center}
{\Large {\bf Exercise 3, part 1}}
\end{center}
{\bf Submition deadline: May 22}
\begin{enumerate}
\item
\begin{description}
\item{(a)} Write a program in theJava language that performs operations under
binary search trees. You should implement the operations $Insert(T, key)$,
$Delete(T, key)$ and $Search(T, key)$, where $T$ is the current binary tree and
$key$ is the element that we want to insert, delete or search for in $T$.
Also write a method $height(T)$ that returns the height of $T$.
Demonstrate the performance of your program on sequence of operations: \\
$1i, 2i, 3i, 4i, 2d, 3i, 10i, 2d, 10d, 7i, 6i, 6i, 13i, 13d$ (when $i$ - for insert, $d$ - for delete).
The output should be the height of the final binary search tree.
\item{(b)} Now perform a loop of $200$ random delete/insert operations (with keys in range $1, \ldots, 1000$
and check the height of $T$.
\item{(c)} Write a new $Delete2(T, key)$ operation that is ``symmetric'' to $Delete(T, key)$,
i.e., instead of switching key with its inorder successor, we now switch
it with its inorder predecessor and rebuild $T$.
\item{(d)} Redo (a) on the same sequence but now using $Delete2(T, key)$.
Explain what happens?
\item{(e)} Redo (b) , but now choose the operation delete randomly.
Explain what happens?
\end{description}
\item Assume that each edge in binary tree $T$ has some positive weight.
Define the weight of a
binary tree as the sum of the weights of all of the edges in the tree.
Finally, define a binary tree $T$ {\em totally balanced} for a given parameter
$\delta > 0$ if $|weight(T_1) - weight(T_2)| \leq \delta$ and
$T_1$ and $T_2$ are also totally balanced for $\delta$, where $T_1$ and $T_2$
are the left and right subtrees of $T$.
Write a program which creates random binary tree $T$ with keys as integers
in the range
from $1$ to $n$ (part of input) and check whether $T$ is totally balanced.
Random binary tree means that we insert
any given tree either in left or in right subtree of $T$ with a probability
$\frac{1}{2}$.  Define the weight of an
edge $(u, v)$ in $T$ as $|u - v|$, where
$u = father(v)$. After creating $T$, the program asks for $\delta$ (integer),
then checks whether $T$ is totally balanced for $\delta$ and prints
``yes'' or ``no''.
Pay attention that the keys are inserted into $T$ also randomly. That is,
we begin to take some key from ${1,\ldots, n}$ (for example $7$), insert it
to $T$, delete $7$ from ${1,\ldots, n}$, take another key from the rest and so
on.
\item Define the {\em diameter} of a binary tree $T$ with $n$ nodes
as the maximum number of
edges on the path between any two nodes in $T$. Design an $o(n\log{n})$ algorithm for
finding the diameter of a given tree $T$.
Note that the path that defines a diameter does not necessarily contain
the root of $T$.
\item You are given some tree $T$ with $n$ nodes (not necessarily binary).
Of course the tree is given by a pointer to its root $r$. We want to find an
adge $(u,v) \in T$, such that each one of the the subtrees rooted at $u$
and rooted at $v$ contains at most $\frac{2}{3}n$ nodes.
Design an $O(n)$ algorithm for finding such $(u,v)$.
\end{enumerate}
\begin{center}
{\Huge {\bf Good Luck!}}
\end{center}
\end{document}