\documentstyle[11pt,epsf,fullpage]{article}

\title{15-451 Algorithms, Spring 1997\\
{\bf Solutions and Comments for Assignment 2}}
\author{Marius Minea}

\begin{document}
\maketitle

{\bf Problem 1} This was supposed to be a very simple problem. The key is
to notice that it doesn't matter where and how you insert an element into
the data structure, and it also doesn't matter what element you remove.
Therefore, either a stack (where you insert and remove from the same end)
or a FIFO queue (where you insert at the tail and remove at the head)
will do the job. Both can be implemented using a linked list or an array,
although the latter requires the maximum size to be known in advance. It
is also clear that in either of these cases {\em Insert} and {\em Remove}
only perform a constant number of pointer or index manipulations, and
therefore take $O(1)$ time.  Statements similar to the above were
sufficient to ensure full credit.  Writing additional pseudocode was
fine, but not required.

{\bf Problem 2} Since we already know that for AVL trees {\em Insert} and
{\em Delete} take $O(log\;n)$ time, this is a good starting point.
To implement {\em Find\_rank} it is also natural to try to keep some
sort of counter for each node that will aid in computing the rank
efficiently.

We also assume that the data structure will not hold duplicates, i.e.
{\em Insert(x)} will do nothing if $x$ is already in the tree (``the
usual meaning''). If we wish to handle duplicates, the easiest way is to
keep a count of the number of times each element appears.

Recall that in a binary search tree with distinct keys, if the root has
key $x_r$, all nodes in the left subtree will have keys less than $x_r$,
and all those in the right subtree have keys greater than $x_r$.
Therefore, in the particular case of the root node, the rank of $x_r$ is
equal to the size (i.e. number of nodes) of the left subtree plus 1 (to
account for the key itself, since we require ``less than or equal'').
Suppose now that we had each node in the tree store in a field {\em
count} the size of its left subtree plus 1. Then, if $x = x_r$ {\em
Find\_rank} can just return the value of {\em count} for the root node.
We continue the reasoning recursively for a key $x \neq x_r$: if $x$ is
in the tree, and $x < x_r$, it has to be in the left subtree. The nodes
in the right subtree don't affect the rank of $x$, since they all have
keys greater than $x$, so we can return the result of {\em Find\_rank(x)}
for the left subtree.  If $x > x_r$, and $x$ is present, it has to be in
the right subtree. Its rank in the main tree will be its rank in the right
subtree, plus the {\em count} field of the root node (which accounts for the
root and the left subtree, where all nodes have keys less than $x$). In
pseudocode:

\begin{tabbing}
12\=12\=12\=12\kill
{\em Find\_rank}(root, x)\\
{\bf if} (root = nil) {\bf return} {\em not\_present};\\
{\bf else if} (x = root.key) {\bf return} root.count;\\
{\bf else if} (x $<$ root.key) {\bf return} {\em Find\_rank}(root.left, x);\\
{\bf else} /* x $>$ root.key */\\
\>result := {\em Find\_rank}(root.right, x);\\
\>{\bf if} (result = {\em not\_present}) {\bf return} {\em not\_present};\\
\>{\bf else} {\bf return} root.count + result;
\end{tabbing}

This outlines the basic idea, but there are more details involved in
giving a complete (and correct) solution. Consider then an AVL tree where
each node has an additional field {\em count} that stores the number of
nodes in its left subtree plus 1. (Storing the size of the entire subtree
also gives a similar solution). Let us see how we have to modify the
{\em Insert} and {\em Delete} procedures to maintain the {\em count} field
for each node.

We can start with the standard AVL {\em Insert}, but we note that each
time we go down a left branch of a node, it means we will insert a node
in its left subtree, so we have to increment its {\em count} field by 1.
When moving down a right branch, we need not do anything additional.
When we finally insert the new node, we give it an initial {\em count}
value of 1.  This works fine except for one case: when the key $x$ is
already in the tree, {\em Insert(x)} will not modify the tree, so the
counters should not be changed. We fix this by either backtracking and
decrementing the counters we just increased, or by simply doing the
increments on the way back to the root instead, when we know that a new
node has been inserted.

{\em Delete} is modified similarly: perform a standard AVL deletion.
If the key is found, then on the way back to the root decrement all
{\em count} fields of the nodes from which a left branch was followed
on the way down.

Assuming {\em Insert} and {\em Delete} both return {\em success} if a
node has been added to/removed from the tree, we can succintly represent
the described algorithms in psedocode as follows:

\begin{tabbing}
12\=12\=12\=1234567890123456789012345678901234567890\=12\=12\=12\=\kill
{\em Insert}(root, x)			\>\>\>\>{\em Delete}(root, x)\\
{\bf if} (root = nil)			\>\>\>\>{\bf if} (root = nil)\\
\>root := new\_node();			\>\>\>\>{\bf return} {\em not\_present};\\
\>root.left := nil; root.right := nil;	\>\>\>{\bf else if} (x = root.key)\\
\>root.key := x;			\>\>\>\>{\em perform deletion}\\
\>root.count := 1;			\>\>\>\>{\em rebalance if needed}\\
\>{\bf return} {\em success};		\>\>\>\>{\bf return} {\em success};\\
{\bf else if} (x = root.key)		\>\>\>\>{\bf else}\\
\>{\bf return} {\em duplicate};		\>\>\>\>{\bf if} (x $>$ root.key)\\
{\bf else}				\>\>\>\>\>\>result := {\em Delete}(root.right, x);\\
\>{\bf if} (x $>$ root.key)		\>\>\>\>{\bf else} /* x $<$ root.key */\\
\>\>result := {\em Insert}(root.right, x);\>\>\>\>result := {\em Delete}(root.left, x);\\
\>{\bf else} /* x $<$ root.key */	\>\>\>\>\>{\bf if} (result = success)\\
\>\>result := {\em Insert}(root.left, x);\>\>\>\>\>root.count := root.count - 1;\\
\>\>{\bf if} (result = {\em success})	\>\>\>{\em rebalance if needed}\\
\>\>\>root.count := root.count + 1;	\>\>{\bf return} result;\\
\>{\em rebalance if needed}\\		
\>{\bf return} result;			
\end{tabbing}

(Again, pseudocode was not required if your explanation was sufficiently
clear one could extract pseudocode from it.)

Both {\em Insert} and {\em Delete} potentially require rebalancing the
tree. The rebalancing procedure has to be modified as well, to ensure that
the counters stay up to date. For a single rotation (Figure 4.14 of the
textbook) we need to update:\\
\hspace*{2in}A.count := A.count -- B.count\\
and for a double rotation (Figure 4.15 of textbook)
we need:\\
\hspace*{2in}A.count := A.count -- B.count -- D.count\\
\hspace*{2in}D.count := D.count + B.count\\

To argue that both {\em Insert} and {\em Delete} still take $O(log\;n)$,
we note that at each level in the tree, we only have to spend $O(1)$ time
to increment or decrement the ${\em count} field$. Updating the counters
during a rebalancing operation also takes only a constant number of
steps, and therefore does not increase complexity. Since an AVL tree of
size $n$ has height $O(log\;n)$, this means both {\em Insert} and {\em
Delete} will take time $O(log\;n)$. {\em Find\_rank} as described above
needs to perform a constant number of operations at each level in the
tree as well, and therefore takes time $O(log\;n)$ for the same reason.

{\bf Common errors:}
\begin{itemize}
\item Attempting to keep the actual rank as a field in each node.
This doesn't work. For instance, if you insert a key smaller than all keys
currently in the tree, you'd have to increment the rank of each node, which
is clearly $\Theta(n)$.

\item The rank of a node in a tree is {\em not} the number of nodes
in its left subtree plus 1. This is only true for nodes that are reached
from the root by going only left.

\item Having an {\em Insert} operation that will incorrectly increment
counters when called with a duplicate.

\item Allowing duplicates, but imposing invariants which cannot be
maintained. For example, always inserting duplicates in the left subtree
of the similar element. Rotations will change the tree structure and the
property may no longer hold. This brings up a more general point: when
your data structure relies on a certain invariant, always check that the
invariant is maintained by all operations.

\item Having a {\em Delete} operation which will incorrectly decrement
counters when called with a nonexisting element.

\item Failing to consider that counters have to be updated during
rebalancing.

\item Failure to argue that the changes introduced to the AVL tree
do not affect the complexity of the operations. This has to be done
always when modifying a known algorithm. It can be easy to introduce a
change that increases complexity.

\end{itemize}



\end{document}