Bäume

Termminologie

Binäre Bäume

Binäre Suchbäume

Einfügen eines Elementes

Beim Einfügen eines Elementes macht man sich die Eigenschaft zunutze, dass der Schlüssel des linken Sohns jeweils kleiner oder gleich dem Schlussel ist, den der Knoten selbst enthält. Der rechte Kindknoten dagegen enthält einen echt größeren Schlüssel. Fügt man also einen Schlüssel in den Baum ein so beginnt man beim Vergleich mit der Wurzel. Ist der Einzufügende Schlüssel größer als der Schlüssel der Wurzel, so setzt man den Vergleich im rechten Teilbaum des aktuellen Knotens fort. Andernfalls also wenn der Schlüssel kleiner oder gleich dem Schlüssel der Wurzel ist, setzt man den Vergleich im linken Teilbaum des aktuellen Knotens fort. Trifft man bei diesem Verfahren auf einen Knoten dessen Wertigkeit null entspricht, so wird an dieser Stelle der neue Schlüssel eingefügt. Für den Programmablauf lässt sich also folgendes allgemein formulieren:

1. Abfrage ob der einzufügende Schlüssel größer oder gleich dem Schlüssel von N ist
2. Abfrage ob der sich daraus ergebende Kindknoten dem Wert null entspricht
3. wenn ja, dann erzeuge neuen Knoten mit dem einzufügenden Schlüssel
4. sonst beginne mit Schritt 1 wobei N nun N.links bzw n.rechts ist

Für die Methode zum Einfügen in einen BST ergibt sich zum einen eine rekursive sowie eine iterative Umsetzungsmöglichkeit, die im folgenden durch Pseudocode beschrieben werden.

Rekursive Umsetzung

InsertRek( Schlüssel K, Knoten N )
if Schlüssel < N.Schlüssel do
    if N.links is null do
        N.links = neuer Knoten
        N.links.Schlüssel = K
        N.links.Vater = N
    else do 
        InsertRek( K, N.links )
else
    if N.rechts is null
        N.rechts = neuer Knoten
        N.rechts.Schlüssel = K
        N.rechts.Vater = N
    else do 
        InsertRek( K, N.rechts ) 

Iterative Umsetzung

InsertIt( Schlüssel K )
Knoten p = Wurzel
Knoten o = null
while p not null
    o = p
    if K < p.schlüssel or K is p.schlüssel
        p = p.links
    else if K > p.schlüssel
        p = p.rechts
    else return
p = neuer Knoten
p.Schlüssel = K
if Wurzel is null
    Wurzel = p
else if K < o.schlüssel or K is o.schlüssel
    o.links = p
else o.rechts = p

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

2-3-4-Bäume

Eigenschaften

1. Knoten enthalten mehr als einen Schlüssel
2. 3-Knoten mit 3 ausgehenden Verkettungen sind zugelassen
3. 4-Knoten mit 4 ausgehenden Verkettungen sind zugelassen
4. Binärbaum Eigenschaften vorhanden (2-Knoten)

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