\documentstyle [11pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{9.5 in}
\setlength{\textwidth}{6.5 in}
\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}
\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\ceiling}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}

\newtheorem{defi}{Definition}[section] % Specify Definition
\newtheorem{problem}[defi]{Problem}      % Specify Lemma


\begin{document}
{\large
\noindent
Algorithms Core 15-750 \hfill PROBLEM SET \# 2 \hfill Spring 1999
\begin{center}
DUE: 1:00PM Monday February 15 1999 \\
\end{center}}

\section{Randomly Balanced Search Trees}

In this problem set we shall consider another approach to using
randomization to maintain a balanced tree.

We consider the {\bf random insertion model} which assigns a
probability to each $n$-node binary tree $T$ equal to the probability
of producing $T$ by inserting the elements by a random permutation of
$\{1, \ldots, n\}$ into an initially empty tree(no rotations). A tree
is called {\bf random} if it is drawn from all $n$-nodes trees
according to this distribution.

Start by proving the following fact about random trees. Let the {\bf size}
of a node in a tree be the number of nodes in its subtree.

\begin{problem}
Let the sizes of the nodes in a random tree $T$ be $s_1, \ldots ,s_n$
show that $Prob(T)= \prod 1/s_k$. 
\end{problem}


What is the relationship between $Prob(T)$ and the potential of $T$
used in the Splay tree algorithms?


Consider the following insertion scheme: INSERT(w): While inserting $w$
as a new leaf, at each node $v$ on the list of ancestors of $w$,
flip a coin and mark $v$ with probability $1/(size(v)+1)$. Rotate $w$
up the tree to the highest node marked including a rotation with
the highest marked node.
   
We would like to show that this algorithm generates random trees. That
is, the probability that INSERT generates a tree is the same as the
random insertion model. We shall do this by taking a tree $T$ and
computing the probability that INSERT generates this tree.

We start with a useful combinatorial fact. Let $T$ be a tree of size
$n$ with root $w$ and Left and Right subtrees $T_L$ and $T_R$,
respectively.  Let $Join(T_L,T_R)$ be the set of all tree obtainable
by combining the two trees, i.e., all tree obtained from $T$ by
rotating $w$ to a leaf and deleting $w$.  Thus, $Join(T_L,T_R)$ is
precisely the maximal set of trees $\hat{T'}$ such that inserting $w$
into $T' \in \hat{T'}$ using INSERT would return $T$, with some
positive probability.

The probability of a distinct set of
trees is just the sum of the probabilities of the individual trees.

Prove the following fact:
\begin{problem}
$
Prob(T)\cdot n = Prob(T_L)\cdot Prob(T_R) = Prob(Join(T_L,T_R))
$
\end{problem}

\begin{problem}
Uses the above two Problems to show that INSERT generates random trees.
\end{problem}

Hint: Let $T\\w$, where $w$ is not necessarily the root, be the set of
all tree obtained from $T$ by rotating $w$ to a leaf a deleting
$w$. Write formula which relates the probability of $T$ to that of
$T\\w$.

 

\begin{problem} 
Give a similar algorithm for DELETION. Show that your algorithm
generates random trees. 
\end{problem}



\section{Updates in splay trees}

Obtain amortized bounds on the number of rotations done for the
following operations on splay trees.  Write your answers in terms of the
sizes of the relevant trees.  (For insertion and deletion, let n
be the number of nodes in the tree before the operation.  For join, let
the numbers of nodes in these trees be n and m respectively.)  Do not
use asymptotic (big oh notation).
\begin{verbatim}
  Insertion (type 1): Perform insertion in the usual way (the new node
                      has no children).  Splay the new node to the root.

  Insertion (type 2): Find the node that would be the parent of the new
                      node in the usual insertion.  Call this node x.
                      Now splay x to the root of the tree.  Now add the
                      new node y above x, to create one of the following
                      trees:

                                y                       y
                               / \                     / \
                              x   B                   A   x
                             /                             \
                            A                               B

                       Where A and B are the subtrees of x after x is
                       splayed to the root.

  Join two trees:      Let the two trees be A and B.  If A is empty
                       return B.  Otherwise find the leftmost node in A
                       (call it x) and splay it to the root.  Now attach
                       B as the left child of x.

  Delete:              To delete a node, splay it to the root, then join
                       the two subtrees of that node to form a new tree.

\end{verbatim}

Hint: You may find it easier to analysis type 2 insertions first.

\end{document}
