\documentclass[11pt]{article}
\usepackage{program}


\title{6.046 Problem Set 5}
\author{Chris Laas: Section G}
\date{March 14, 2000}

\pagestyle{myheadings}
\markright{Chris Laas: Section G \hfil 6.046J/18.410J \hfil 3/14/2000}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}}
\NumberProgramstrue
\def\RETURN{\keyword{return}\ }
\def\MOD{\mbox{mod}\ }
\def\text#1{\mbox{ #1 }}
\def\AND{\mbox{\bf\ and }}
\def\OR{\mbox{\bf\ or }}



\begin{document}
\maketitle

\section*{Problem 5-1}
\begin{enumerate}

\item%(a)

This does not guarantee that the tree is balanced --- a tree formed by
the recursive rule $tree(n) = node(left=leaf, right=tree(n-2))$,
$tree(1) = leaf$ has this property, but has height $\Theta(n)$.
\vskip 1 in


\item%(b)

Yes.

The condition implies that for any internal node $p$ with left and
right children $l$ and $r$,
\begin{eqnarray*}
2^{k_p} - 1 & = & (2^{k_l} - 1) + (2^{k_r} - 1) + 1 \\
            & = & 2^{k_l} + 2^{k_r} - 1
\end{eqnarray*}
Thus
$$ 2^{k_p} = 2^{k_l} + 2^{k_r} $$
and therefore $k_l = k_r$.  Thus, the left and right subtrees of any
node have the same size.  Thus, the tree is perfectly balanced, and
thus is well balanced.
\vskip 1 in


\item%(c)

Yes.

The condition implies that, if $n(h)$ is the maximum number of nodes
in a tree of height $h$, then
$$ n(h) \geq n(h-1) + \frac{1}{2} n(h-1) = \frac{3}{2} n(h-1) $$
Thus $n(h) \geq \left(\frac{3}{2}\right)^h$, and therefore
$h(n) \leq \log_{3/2} n$.  Thus $h = O(\lg n)$.


\item%(d)

No.  This seems like a trivially ridiculous condition, since it
implies that only one node in the tree may have two children.  (For,
assume that two nodes in the tree have two children.  Then, either one
is a child of the other (in which case it shares a parent with another
node and is not a leaf, contradicting the assumption), or they have a
common ancestor, which clearly has two children which are non-leaves.
Either way, the condition is contradicted.)  Thus, the only possible
trees are ones which are entirely linear, with height $n-1 =
\Theta(n)$.
\vskip 1 in


\item%(e)

No.  The family of counterexamples is constructed thus: for a
parameter $k$, construct the perfectly balanced tree of height $k-1$,
with $2^k - 1$ nodes; then hang a perfectly linear ``tree'' of $k^2$
nodes off of the rightmost tip.  The number of nodes in this tree is
clearly $n = (2^k - 1) + k^2 = \Theta(2^k)$; the height is clearly
$(k-1) + k^2 = \Theta(k^2) = \Theta(\lg^2 n)$, which is clearly not
$O(\lg n)$.

It remains to be shown that a tree in this family has average depth
$O(\lg n)$.  The average depth is equal to

\begin{eqnarray*}
d(n)
  & = &
  \frac{1}{n} \left(\sum_{i=0}^{k} (i 2^i) + \sum_{i=0}^{k^2-1} (k+i)\right) \\
  & \leq &   \frac{1}{n} \left(k \sum_{i=0}^{k} (2^i) + O(k^4) \right) \\
  & \leq &   \frac{1}{n} \left(k 2^{k+1} + O(k^4) \right) \\
  & =    &   \frac{\Theta(k 2^k)}{n} \\
  & =    &   \frac{\Theta(n \lg n)}{n} \\
  & =    &   \Theta(\lg n)
\end{eqnarray*}

Thus the average depth is $O(\lg n)$.
\vskip 1 in


\end{enumerate}
\newpage



\section*{Problem 5-2}
\begin{enumerate}

\item%(a)

The algorithm to do this is the obvious one:  go over every $i$ in
order, and perform an inorder traversal up to that depth (using a
``helper'' traversal routine).  I present the traversal routine first:

\begin{program}
|Cousins-Traverse|(|node|, i)
\quad\tab \IF i = 0
             \THEN |Print|(node)
             \ELSE |Cousins-Traverse|(|left|[node], i-1)
                   |Cousins-Traverse|(|right|[node], i-1)
\end{program}

The precondition on the function is that the input node be the root of
a perfectly balanced subtree of height at least $i$; it promises, as a
postcondition, to pass to the Print routine, in order, all nodes in
its subtree of depth $i$.  Is is easy to see that it does this:  if
$i = 0$, then it need only print out its input, and otherwise, it
recurses over the left and right subtrees in order (satisfying the
preconditions properly).  Termination is guaranteed by the
monotonically decreasing value of $i$.  The recurrence relation for
the runtime is $T_h(i) = 2 T_h(i-1) + \Theta(1)$, giving
$T_h(i) = \Theta(2^i)$.

The ``overall'' algorithm is implemented simply by running the helper
seqentially over all values of $i$.  I let the function $|Height|(T)$
return the height of a tree $T$; in this case, it can be computed as
$|Height|(T) = \lg (n+1) - 1$, although it could also be easily
computed in $\Theta(\lg n)$ time (for a perfectly balanced tree) if we
weren't initially given $n$.

\begin{program}
|Cousins-In-A-Tree|(T)
\quad\tab \FOR i \gets 1 \rdots |Height|(T)
              |Cousins-Traverse|(|root|[T], i)
\end{program}

Correctness is clear by the correctness of $|Cousins-Traverse|$ and
the direct translation of the problem specification into pseudocode;
termination is guaranteed by the finite number of iterations of the
for loop.  The run time of this algorithm is given by
\begin{eqnarray*}
T_{|main|}(n) & = & \sum_{i=1}^{\lg (n+1) - 1} T_h(i) \\
              & = & \sum_{i=1}^{\lg (n+1) - 1} \Theta(2^i) \\
              & = & \Theta(2^{(\lg (n+1) - 1) + 1}) \\
              & = & \Theta(2^{\lg n}) \\
              & = & \Theta(n) \\
\end{eqnarray*}

Thus the algorithm runs in $O(n)$ steps.


\end{enumerate}
\newpage



\section*{Problem 5-3}
\begin{enumerate}

\item%(a)

The algorithm is simple: first insert the node as a leaf, using normal
binary-search-tree insertion; then perform $O(\lg n)$ rotations to
restore the heap property.

\begin{program}
|TREAP-Insert|(T, x)
\quad\tab |score| \gets |Random|()
          |node| \gets |Binary-Tree-Insert|(T, x, |score|)
          \WHILE |node| \neq |root|[T] \AND |score|[|node|] > |score|[|parent|[|node|]]
                |Rotate-Up|(T, |node|)
\end{program}

The $|Rotate-Up|$ operation (which runs in $\Theta(1)$ steps) is
simply a convenient wrapper $|Left-Rotate|$ and $|Right-Rotate|$ that
always performs the rotation that will move the input node ``up'' in
the tree and its parent down.  $|Rotate-Up|$ maintains the binary
search tree property, and restores the local heap property when the
child is out of order with respect to its parent.  At the end of the
$|TREAP-Insert|$ invocation, the binary-search-tree and heap
properties have been restored to the tree.

\item%(b)

We use the result of the previous problem set.  The binary search tree
property defines a unique inorder traversal for the tree, and the heap
property (in addition to the search order to strongly order left/right
children) defines a unique preorder traversal.  The tree structure can
be uniquely reconstructed from these two orderings; thus the binary
tree property and the heap property define a unique tree structure.

\item%(c)

There is a one-to-one correspondence between the space of TREAPs with
equivalent search orderings and the space of randomly build binary
search trees.  A TREAP is identical to a ``normal'' binary search tree
built by first inserting the node with the highest score, then that
with the next-highest, and so on.  But any ordering of the scores on
the nodes is equally likely, since they are randomly generated.  Thus
a TREAP is equivalent to a binary search tree built by inserting
elements in a randomly permuted order, and thus the expected height is
$O(\lg n)$.


\end{enumerate}
\newpage



\section*{Problem 5-4}
\begin{enumerate}

\item%(a)

To find the successor node, begin at the original node.  Then walk up
the parent chain until we are not at the rightmost child of a parent
node; this takes $O(\lg n)$ steps.  Then descend the ``next'' subtree
(the one rooted at the middle or rightmost child of the parent node,
depending on whether we were the leftmost or middle child), following
the leftmost branches until we hit a leaf; this also takes $O(\lg n)$
steps.  This leaf is the successor to the original node.  The
pseudocode for this algorithm looks like this:

\begin{program}
|Successor|(T, |node|)
\quad\tab \WHILE |node| \neq |root|[T] \AND |right|[|parent|[|node|]] = |node|
                |node| \gets |parent|[|node|]
                \untab%
          \IF |node| = |root|[T]
             \THEN \RETURN |nil|
                  \untab%
             \untab%
          \IF |node| = |left|[|parent|[|node|]]
              \THEN |node| \gets |middle|[|parent|[|node|]]
              \ELSE |node| \gets |right|[|parent|[|node|]]
                   \untab%
              \untab%
          \WHILE |left|[|node|] \neq |nil|
                |node| \gets |left|[|node|]
                \untab%
          \RETURN |node|
\end{program}


\item%(b)

We modify the leaf structure to contain a successor pointer, which,
unsurprisingly enough, points to the successor leaf of a given leaf.
The $|Search|$ algorithm need not be modified at all to handle this
change.  The $|Insert|$ operation can be performed as normal, but a
post-pass must be applied to fix up the successor linked list: the
predecessor to the newly-inserted node is found using the above
tree-walking algorithm, in $O(\lg n)$ time, and the new node is
inserted into the linked list in the usual way.  The $|Delete|$
operation requires a pre-pass to remove the to-be-deleted node from
the successor linked list: again, the predecessor is found by walking
the tree, taking $O(\lg n)$ time, and the node is deleted from the
linked list in the usual way (at this point, it is safe to delete the
node from the 2-3 tree in the usual way).

(In case it's not clear, the ``usual way'' of inserting and deleting
nodes in linked lists can be executed in $O(1)$ time if the
predecessor is already known, since it only involves changing the
``next'' pointers of the node and its predecessor.)


\end{enumerate}
\newpage


\section*{Problem 5-5}
\begin{enumerate}

\item%(a)

In general, we want to shuffle $k$ downwards until it is in a leaf.


\end{enumerate}
\newpage



\end{document}
