Bäume

Termminologie

Binäre Bäume

Binäre Suchbäume

Einfügen eines Elementes

Einfügen eines Duplikates

Finden eines Elementes

Finden des Minimums

Finden des Maximums

Finden des Nachfolgers

Sortierte Ausgabe des Baumes

Löschen eines Elementes

Mit einem Sohn

Mit zwei Söhnen

Rot-Schwarz-Bäume

Komponenten der Knoten

• Farbe
• Schlüssel
• Adresse des Eleternknotens
• Adresse des linken Kindknotens
• Adresse des rechten Kindknotens

Eigenschaften

1. Jeder Konten ist entweder rot oder schwarz
2. Die Wurzel ist schwarz
3. Jedes Blatt( null/ nil ) ist schwarz
4. Die Kind-Knoten eines Roten Knotens sind jeweils schwarz
5. Alle Pfade die von einem bestimmten Knoten ausgehen und in einem Blatt dieses Teilbaums enden, haben die gleiche Anzahl an schwarzen Knoten

Rotationen

Durch die Einfüge- und Löschoperationen kann es dazu kommen, das eine oder mehrere Eigenschaften des Rot-Schwarzbaumes verletzt werden. Um die Zeigerstruktur des Baumes zu "reparieren" bedient man sich der Rotation.

Linksrotation

Rechtsrotation

Einfügen

Fall 1

Fall 2

Fall 3

Fall 4

Fall 5

Löschen

Fall 1

Fall 2

Fall 3

Fall 4

Fall 5