\begin{slide}{Abstrakter Datentyp \emph{Menge}}

Schnittstelle
\begin{verbatim}
interface Set<E>  {
    boolean isEmpty ();
    void add (E o);
    void remove (E o);
    boolean contains (E o);
}
\end{verbatim}
mit Eigenschaften: z. B.
\begin{verbatim}
(1) nach s.add (o)  gilt  s.isEmpty() == false.
(2) wenn  s.add (o), 
       dann danach  s.contains(o) == true
\end{verbatim}
\end{slide}

\begin{slide}{Konkrete Datentypen für Mengen}

Vorüberlegungen:
  \begin{itemize}
  \item ungeordnete Liste (verkettet, zusammenhängend)?
  \item geordnete Liste (verkettet, zusammenhängend)?
  \end{itemize}
Lösungen:
\begin{itemize}
\item Suchbaum (benötigt Ordnungsrelation)
  \item Hashtabelle (benötigt Hashfunktion)
  \end{itemize}

\begin{verbatim}
class TreeSet<E> implements Set<E> { ... };
class HashSet<E> implements Set<E> { ... };
\end{verbatim}

\end{slide}
