\documentstyle[11pt,handout]{article}
\begin{document}
\input{localmacros}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{21 October 1998}{12}

\begin{center}
\Large{\bf Problem of the Week -- 5}
\end{center}

This exercise concerns two new operations on red-black trees.  In both of
these problems, assume that all of the keys are distinct.
\begin{Enumerate}
\item[{\bf (a)}]
Given two red-black trees $T_1$ and $T_2$, consisting of $n$ and $m$ nodes,
respectively, the {\em merge}\/ operation returns a new red-black tree $T =
T_1 \cup T_2$ consisting of $n + m$ nodes.  Design and analyze an
asymptotically efficient algorithm for implementing the merge operation.  

\item[{\bf (b)}] 
Suppose we are given a red-black tree $T$ and a node $x$ in $T$, and we wish
to compute the set $S$ of nodes in $T$ whose keys are less than $\key[x]$.
Consider the path $P$ from the root of $T$ to the node $x$.  Show that $P$
breaks $S$ into a set of trees $\{T_0, T_1, \ldots, T_k\}$ and a set of nodes
$\{x_1, x_2, \ldots, x_k\}$, where, for $i = 1, 2, \ldots, k$, we have
$\key[y] < \key[x_i] < \key[z]$ for any keys $y \in T_{i-1}$ and $z \in T_i$.
What is the relationship among the black heights of the $T_i$'s?
\end{Enumerate}

\end{document}