\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment 6\\ Solutions} \\
\end{center}
\vspace{1cm}
\ben
\item
Consider a Binary Search Tree $T$ with vertices $a,b,c,d,e,f,g,h$
and $ROOT[T]=a$ and with the following values ($N$ means NIL)
\begin{center}
\begin{tabular}{r|rrrrrrrr}
vertex & a&b&c&d&e&f&g&h \\
parent & N&e&e&a&d&g&c&a \\
left & h & N & N & e & c & N & f & N \\
right & d & N & g & N & b & N & N & N
\end{tabular}
\end{center}
\ben
\item Draw a nice picture of the tree.
\So
\begin{verbatim}
a
h d
e
c b
g
f
\end{verbatim}
\item Which is the successor of $c$. Illustrate how the
program {\tt SUCCESSOR} will find it.
\So The successor of $c$ is $f$. As $c$ has a right child
$g$, SUCCESSOR will call {\tt MIN[g]} which will go to the
left as long as possible, ending (in one step) at $f$.
\item Which is the minimal element? Illustrate how the
program {\tt MIN} will find it.
\So $h$. Start at root $a$. Go to left: $h$. Go to left: NIL.
Return $h$.
\item Illustrate the program {\tt DELETE[e]}
\So There are two approaches (equally correct) to {\tt DELETE[x]}
when $x$ has two children. One can effectively replace $x$ by
the maximum of its left tree or the minimum of its right tree.
\\ {\tt Solution 1:} $e$ has a left child $c$. Applying {\tt MAX[c]} gives
$g$. $g$ has a left child $f$. So we splice $f$ into $g$'s
place by resetting $right[c]=f$ and $p[f]=c$ and we put
$g$ in $e$'s place, setting $left[d]=g$, $left[g]=c$, $right[g]=b$.
and $p[g]=d$.
\\ {\tt Solution 2:} $e$ has right chils $b$. Applying {\tt MIN[b]} gives
$b$ itself. We splice $b$ into $e$'s place by resetting $p[c]=b$ and
$left[b]=c$ and $p[b]=d$ and $left[d]=e$
\item Now suppose we also have the key values
\begin{center}
\begin{tabular}{r|rrrrrrrr}
vertex & a&b&c&d&e&f&g&h \\
key & 80 & 170 & 140 & 200 & 150 & 143 & 148 & 70
\end{tabular}
\end{center}
Illustrate {\tt INSERT[i]} where {\tt key[i]=$100$}.
\So We start at root $a$ with $key[a]=80$. As $80 < 100$
we replace $a$ by its right child $d$ with $key[d]=200$.
As $100 < 200$ we replace $d$ by its left child $e$ with $key[e]=150$.
As $100 < 150$ we replace $e$ by its left child $c$ with $key[c]=140$.
As $100 < 140$ we replace $c$ by its left child. But its left child is
NIL so we make the new vertex $i$ its left child by setting $p[i]=c$
and $left[c]=i$.
\een
\item Draw binary search trees of height 2,3,4,5,6 on the
set of keys \{1,4,5,10,16,17,21\}.
\So For height 2 with 7 it must be balanced so $10$ is the
root with children $4,17$ which in turn have children
$1,5$ and $16,21$. For height 6 it must be a line. There
are two ways: $1$ as root and then taking right children
go dwon $4,5,10,16,17,21$. (Or take $21$ as root and go
in reverse.) For the other heights there are many solutions.
E.g.: height $3$: $10$ has left child $5$ with left child
$4$ with left child $1$ and $10$ has right child $17$ which
has two children $16,21$. Height 4: root $16$ has left
child $10$ with left child $5$ with left child $4$ with
left child $1$ and $16$ has right child $17$ with right
child $17$. Height 5 would be similar with $17$ as root.
\item What is the difference between the binary-search
property and the heap property? (*) Can the heap property
be used to print out the keys of an $n$-node tree in sorted
order in $O(n)$ time? Explain how or why not.
\So Actually there is not that much the same. In min-heap the
parent is less than both children. In BST the parent is bigger
than the leftchild and less than the right child and moreover
the parent is bigger than all of the left subtree and less than
all of the right subtree.
\par There is no way to get a sorted order from a min-heap
in time $O(n)$. Recall you can build a min-heap from scratch
in time $O(n)$. So is you could then get a sorted order in
further time $O(n)$ then in total $O(n)+O(n)=O(n)$ you would
sort an array from scratch. We can't do that -- sorts take time
$O(n\lg n)$ unless there is additional information about the
data.
\item What would the BST tree look like if you start
with the root $a_1$ with $key[a_1]=1$ (and nothing else)
and then you apply $INSERT[a_2],\ldots,INSERT[a_n]$ in
that order where $key[a_i]=i$ for each $2\leq i\leq n$?
Suppose the same assumptions of starting with $a_1$ and
the key values but the INSERT commands were done in
{\em reverse} order $INSERT[a_n],\ldots,INSERT[a_2]$.
\So In the first case it would be like a line to the
right, with each $a_i$ the right child of the previous
$a_{i-1}$. In the second case $a_n$ would be the right
child of $a_1$ and then it would look like a line to
the left (but always staying to the right of $a_1$)
with $a_{i-1}$ being the left child of $a_i$.
\een
\end{document}