%%\RequirePackage{fix-cm}
\documentclass[a4paper,fleqn,ngerman]{scrartcl}
\usepackage{cmap}
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage[ngerman]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
%%\usepackage[nointegrals]{wasysym}
\usepackage{dsfont}
%%\input{fonts}
\usepackage{booktabs}
\usepackage{color}
\usepackage{units}
\usepackage{eule}
\usepackage[activate]{pdfcprot} % optischer Randausgleich mit pdfLaTeX
\usepackage{graphicx}
\usepackage{calc}
\usepackage[bookmarksnumbered,bookmarksopen]{hyperref}
\hypersetup{
 pdftitle={\"Ubungsblatt 9},
 pdfsubject={Programmierung II, Lenhof},
 pdfauthor={Andreas Glitsch, Jan Hendrik Dithmar, Dirk Heine},
 pdfkeywords={Programmierung II, Lenhof},
 pdfstartview={FitH \hypercalcbp{\paperheight-\topmargin-1in-\headheight-\headsep}}
}
\usepackage{listings}
\lstloadlanguages{Pascal,C++}
\lstset{tabsize=4,language=Pascal,basicstyle=\ttfamily}
\lstset{morekeywords={process,par_begin,par_end,monitor,public,from},
morecomment=[l]{//},
morecomment=[s]{/*}{*/}}
\input{macros}
\setcounter{secnumdepth}{0}
%%\renewcommand*{\sectfont}{\bfseries}
\listfiles
\begin{document}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\titlehead{
  \newlength{\calclengthA}
  \newlength{\calclengthB}
  \settowidth{\calclengthA}{\EULE}
  \setlength{\calclengthB}{\linewidth}
  \addtolength{\calclengthB}{-\calclengthA}
  \addtolength{\calclengthB}{-1em}
  \parbox{\calclengthB}{
    \raggedright
    \scshape{
    Universit\"at des Saarlandes\\
    Fachrichtung 6.2 - Informatik\\
    Sommersemester~2004\\
    Gruppe~Andreas~Augustin ~Do~14-16
    }
  }
  \hfill
  \parbox[b]{\calclengthA}{\EULE}
}
\subject{Programmierung II}
\title{Übungsblatt 9}
\author{Andreas Glitsch 2026130 \and Jan Hendrik Dithmar 2031259 \and Dirk Heine 2030941}
\date{\today}

\maketitle

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
1 & 2 & 3 & 4 & 5 & 6 & $\sum$\\
\hline
& & & & & & \\
\hline
\end{tabular}
\end{center}
\section{Aufgabe 3 - Anwendung Hashfunktion}
Algorithmus zum Auswerten der Kosten von Teilnehmern aus einer Log-Datei:\\
Ich lese die Log-Datei ein und beginne mit der ersten Zeile. Die Kosten des dortigen Teilnehmers
werden zusammen mit seinem Namen in einer Zelle gespeichert. Den Namen verwende ich in einer
Suchfunktion. Bevor die Suche beginnt wird die aktuelle Zeile noch gel\"oscht. Ich lasse die Suchfunktion
laufen und bei jedem Treffer die dort gespeicherten Kosten in der Speicherzelle des Namens hinzuz\"ahlen.
Dann wird die Zeile gelöscht und die Suche f\"ahrt fort. Dasselbe Verfahren wende ich bei allen anderen %%@
Treffern an, solange bis ich das EOF erreiche. Name und Kosten werden dann ausgegeben. Dann gehe ich an den %%@
Anfang zur\"uck, an dem jetzt ein neuer Name steht. Bei diesem wende ich dieselbe Vorgehensweise an wie schon %%@
mit dem Vorherigen. Kosten aufsummieren, Zeile l\"oschen, Suche fortf\"uhren bis zum EOF. Die ganze Prozedur %%@
l\"auft solange die erste Zeile kein EOF ist.\\
\\

\section{Aufgabe 5 - Bin\"arer Suchbaum}
Beweis: \\
Sei $x$ Knoten des Baumes, dann gilt f\"ur jeden Knoten $y$
\begin{itemize}
	\item im linken Unterbaum von $x$: $y.key \le x.key$
	\item im rechten Unterbaum von $x$: $y.key \ge x.key$
\end{itemize}
D.h., dass alle Elemente, die kleiner gleich der Wurzel sind, links vom aktuellen Knoten eingef\"ugt werden %%@
und alle Elemente großer gleich der Wurzel rechts davon. \\
Für $n=0$ macht \verb!tree_walk! garnichts. \\
{\bfseries Induktionsanfang:} $n=1$ \\
$n=1 \Leftrightarrow$ Baum besteht nur aus Wurzel. \\
Die Zeiger \verb!left_child! und \verb!right_child! zeigen auf \verb!NULL!, d.h. die Aufrufe von %%@
\verb!tree_walk! für linkes und rechtes Kind machen nichts (vgl. Fall $n=0$). Somit wird
der Baum korrekt sortiert ausgegeben. \\
Bemerkung: Dies ist der Fall, wenn ein (Unter-)Baum keine Kinder hat. \\
{\bfseries Induktionsannahme:} Die Aussage gilt für alle natürlichen Zahlen $n$. \\
{\bfseries Induktionsschluss:} $n \leadsto n+1$ \\
Einem Baum mit $n$ Knoten wird 1 Element hinzugef\"ugt. \verb!tree_insert! aus der Vorlesung beh\"alt die %%@
Eigenschaften des Suchbaums beim Einf\"ugen bei, d.h., der neue Knoten wurde an der richtigen Stelle %%@
eingef\"ugt.
Da \verb!tree_walk! zuerst rekursiv den linken Teilbaum hinabsteigt, bekommt man hier das kleinste Element im %%@
Baum. Falls kein linker Teilbaum (mehr) vorhanden ist,
gibt \verb!tree_walk! den aktuellen Knoten aus (kleinstes Element im linken Teilbaum), steigt auf und geht %%@
rekursiv in den jeweils rechten Teilbaum. Ist in diesem ein linker Unterbaum
vorhanden, so arbeitet die Prozedur wie oben bereits beschrieben. Der rekursive Abstieg im rechten Teilbaum %%@
liefert (am Ende) das gr\"o"ste Element im Baum. Ist kein rechter Teilbaum
(mehr) vorhanden, gibt \verb!tree_walk! das aktuelle Element aus (gr\"o"stes Element im Baum). \\
Somit gilt für jeden ausgegebenen Knoten $k$:
$$k_i \leq k_j \quad \forall i<j$$
und der Baum ist sortiert ausgegeben. \QED
\\

\section{Aufgabe 6 - Kommutativit\"at}
Das L\"oschen im bin\"aren Suchbaum ist kommutativ. \\
{\bfseries Begr\"undung:} \\
Fallunterscheidung:
\begin{enumerate}
	\item Fall: {\bfseries Die zu l\"oschenden Knoten $x$ und $y$ sind Bl\"atter} \\
		Hier ist es offensichtlich, dass die Reihenfolge bei der L\"oschung keine Rolle spielt.
	\item Fall: {\bfseries Einer der Knoten ist ein Blatt, der andere ist Teil eines Teilbaums} \\
		Bei der L\"oschung von einem Knoten wird der Baum so umsortiert, dass vorherige Bl\"atter danach %%@
immernoch Bl\"atter sind. Somit spielt es keine Rolle, ob das Blatt zuerst oder
		an zweiter Stelle gel\"oscht wird. Auf den Teilbaum hat die Reihenfolge ebenfalls keine Auswirkung, %%@
da die Struktur des Teilbaums bis auf das Verschieben des kleinsten Elementes
		an die Stelle der Wurzel ebenfalls erhalten bleibt.
	\item Fall: {\bfseries Beide zu l\"oschenden Knoten $x$ und $y$ sind Teil eines Teilbaums} \\
		Wie oben gesagt wird die Struktur des Teilbaums bis auf das Verschieben des kleinsten Elements an die %%@
Stelle der Wurzel nicht ver\"andert. Ob dabei zuerst
		$x$ und dann $y$ gel\"oscht wird oder umgekehrt spielt keine Rolle, da bei jeder L\"oschung nur das %%@
kleinste Element verschoben wird und ggf. die Kinder dieses Elements
		\glqq nachr\"ucken\grqq .
\end{enumerate}

\end{document}
