\documentclass[10pt]{article}

\usepackage{ngerman,a4,amssymb,amsmath}
\usepackage[latin1]{inputenc}
\usepackage{listings}
\usepackage{enumerate}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\Inv}[1]{\ensuremath{\frac{1}{#1}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}

\thispagestyle{empty}

\title{Programmierung 2 - Übungsblatt 10 \\
	Di, 9-11 Uhr \\
	Andreas Augustin}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
  Andreas Steinel (Matrikelnummer 2029984) \\
  Manuel Gorius (Matrikelnummer 2030845) \\
  Robert Vollmann (Matrikelnummer 2030097)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}
Beim einem (2,5)-Baum hat jeder innere Knoten mindestens 2 und höchstens 5 Kinder.
\subsubsection*{Spalten}
Die Operation Spalten wird durchgeführt, wenn ein Knoten infolge einer Einfüge-Operation sechs Kinder hat. Es werden zwei neue
Knoten generiert, wobei der erste dieser Knoten als Kinder die ersten drei Kinder des alten Knotens hat und der zweite Knoten
die letzten drei. Der alte Knoten wird entfernt und die beiden neuen Knoten als Kinder des Vaters des alten Knotens eingetragen.
Da ein Kind des Vaters durch zwei neue Kinder ersetzt wird, kann es passieren, dass auch der Vater jetzt sechs Kinder hat.
Tritt dieser Fall ein, wird die Spaltung rekursiv für den Vater wiederholt. Dies kann sich im schlimmsten Fall bis zur Wurzel
fortsetzen. Sollte die Wurzel durch die Spaltungen nun sechs Kinder haben werden diese Kinder wie oben beschrieben auf zwei
neue Knoten verteilt und die Wurzel durch einen Knoten, der nur die beiden neuen Knoten als Kinder hat, ersetzt. In diesem Fall
erhöht sich die Tiefe des Baumes um 1. Die Markierungen des Baums müssen jeweils angepaßt werden, unter Umständen über die gesamte
Tiefe.
\subsubsection*{Verschmelzen}
Die Operation Verschmelzen wird durchgeführt, wenn durch eine Löschung eines Elements ein Knoten nur noch ein Kind hat und einer
seiner Nachbarn genau zwei Kinder hat. Die drei Kinder werden unter einem neuen Knoten zusammengefasst, die beiden alten Knoten
durch den einen neuen ersetzt. Dadurch reduziert sich die Kinderanzahl des Vaterknotens um eins. Gegebenenfalls muss somit
der Vorgang rekursiv bis zur Wurzel fortgesetzt werden. Schließlich kann es passieren, dass die Wurzel nur noch ein Kind hat.
In diesem Fall wird dieses eine Kind der Wurzel die neue Wurzel, die alte Wurzel wird entfernt und die Tiefe des Baumes reduziert
sich um 1. Die Markierungen des Baumes müssen unter Umständen über die gesamte Tiefe angepaßt werden.
\subsubsection*{Stehlen}
Die Operation Stehlen wird durchgeführt, wenn durch eine Löschung eines Elements ein Knoten nur noch ein Kind hat und einer seiner
Nachnbarn mehr als zwei Kinder hat. In dem Fall, dass ein Kind vom linken Nachbar gestohlen wird, wird dessen äußerst rechtes
Kind gestohlen, im anderes Fall dessen äußerst linkes Kind. Es kann immer nur von einem unmittelbaren Nachbarn ein Kind
gestohlen werden. Das Kind wird aus dem Nachbarn entfernt und in den aktuellen Knoten eingetragen. Es muss nur die Markierung
des betrachteten Knotens oder des Nachbarn geändert werden. Eine Rekursion ist nicht erforderlich. Die Tiefe des Baums kann
sich bei dieser Operation nicht ändern.

\end{document}