\documentstyle [12pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 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{\ignore}[1]{}
\newcommand{\remark}[1]{[{\small{\bf Editorial Remark: }#1}]}


\newcommand{\ceiling}[1]{\lceil #1 \rceil}

\begin{document}
\sloppy

{\large
CMU 15-451 \hfill PROBLEM SET \# 5 \hfill FALL 1993
\begin{center}
DUE: Thursday 7 October 1993 \\
\end{center}}

\section*{Augmenting The Red-Black Tree}

In this problem we augment the three basic operation of {\bf
Search}$(k)$, {\bf Insert}$(k)$, and {\bf Delete}$(k)$ with the
operations {\bf Next}$(k)$ and {\bf Prev}$(k)$.  The operation {\bf
Next}$(k)$ takes the key $k$ and returns a key $k'$ that is the smallest
key strictly larger then $k$. {\bf Prev}$(k)$ is defined similarly.

\begin{enumerate}
\item
Show how to modify the Red-Black tree data structure so that the
operations {\bf Search}, {\bf Insert} and {\bf Delete} are still
$O(logn)$ but you can handle the operations {\bf Next} and {\bf Prev}
in $O(1)$ when ever the operations {\bf Next}$(k)$ and {\bf Prev}$(k)$
follow a {\bf Search}$(k)$.
\item
Can you find a data structure using the idea presented in class such
that the operations {\bf Insert}$(k)$ and {\bf Delete}$(k)$ are
$O(\log n)$ and the operations {\bf Search}$(k)$, {\bf Next}$(k)$, and
{\bf Prev}$(k)$ are expected time $O(1)$?
\end{enumerate}


\end{document}