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
p.Vater = o
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

Finden eines Elementes

Beim suchen eines Elementes wird die spezielle Anordnung der Elemente in einem Baum genutzt. Ist der Baum leer, so ist der Schlüssel nicht enthalten. Ist das zu suchende Element größer als der Schlüssel der Wurzel bzw. des Knotens des aktuellen Teilbaumes so vergleicht man dessen rechten Kindknoten, ist er gleich so wurde das gesuchte Element gefunden ansonsten vergleicht man die Wurzel bzw. den linken Kindknoten des aktuellen Knotens. Beinhaltet der binäre Suchbaum ein oder mehrere Duplikate, so wird immer nur der Schlüssel gefunden, der den gerringsten Weg zu Wurzel des Baumes besitzt, also der Schlüssel mit der geringsten Tiefe. Folgende Schritte sind also beim Einfügen durchzuführen:

• Abfrage ob der Baum leer ist
• Vergleich ob der gesuchte Schlüssel der Schlüssel des Wurzelelementes ist
• Wenn Schlüssel kleiner oder gleich ist, dann suche im linken Teilbaum weiter sonst rechts

Rekursive Implementierung

searchRek( Schlüssel k, Knoten n )
if n is null
    return null
if k is n.schlüssel
    return n 
if k < n.schlüssel
    return searchRek( k, n.links )
else return searchRek( k, n.rechts )	

Iterative Implementierung

searchIt( Schlüssel k, Knoten n )
Knoten nI = n
while nI not null and nI.schlüssel not k
    if k < nI.schlüssel
        nI = nI.links
    else nI = nI.rechts
return nI

Finden des Minimums

Um den minimalsten Schlüssel im Baum zu finden wandert man einfach von der Wurzel beginnend immer am linken Teilbaum entlang, bis der nächst folgende Knoten den Wert null enthält.

Iterative Implementierung

Knoten getMinIt( Knoten wurzel )
if wurzel is null
    return null
while wurzel.links not null
    wurzel = wurzel.links
return wurzel

Rekursive Implementierung

Knoten getMinRek( Knoten wurzel )
if wurzel is null
    return null
else if wurzel.links is null 
    return wurzel
else return getMinRek( wurzel.links )

Finden des Maximums

Um den maximalen Schlüssel im Baum zu finden wandert man einfach von der Wurzel beginnend immer am rechten Teilbaum entlang, bis der nächst folgende Knoten den Wert null enthält.

Iterative Implementierung

Knoten getMaxIt( Knoten wurzel )
if wurzel is null
    return null
while wurzel.rechts not null
    wurzel = wurzel.rechts
return wurzel

Rekursive Implementierung

Knoten getMaxRek( Knoten wurzel )
if wurzel is null
    return null
else if wurzel.rechts is null 
    return wurzel
else return getMaxRek( wurzel.rechts )

Finden des Nachfolgers

Der Nachfolger eines Knotens ist der Knoten, dessen Schlüssel gemäß der Ordnugsrelation größer ist. Existieren Duplikate, so ist der Nachfolger der Vaterknoten. Das Sohnelement muss in diesem Fall notwendigerweise ein linker Sohn sein. Der Nachfolger eines Knotens ist daher entweder das Minimum des rechten Teilbaumes oder, falls dieser nicht vorhanden, der Vaterknoten.

Rekursive Implementierung

Iterative Implementierung

NachfolgerIt( Knoten n )
    if n is null
        return null
    if n.rechts not null
        return getMin( n.rechts )
    Knoten oben = n.vater
    while oben not null and oben.rechts is n
        n = oben
        oben = n.o
    return oben

Sortierte Ausgabe des Baumes

Rekursive Implementierung

AusgabeVorwRek( Knoten n )
if n is null do
    return ""
else return n.toString + lineBreak + AusgabeVorwRek( nachfolger( n ) )

Iterative Implementierung

AusgabeVorwIt( Knoten n )
String retStr = ""
while n not null do
    retString + n.toString + lineBreak
    n = nachfolger( n )

Löschen eines Elementes

Das löschen eines Knotens in einem BST stellt sich als komplexer heraus. So muss eine grundsätzliche Entscheidung vorgenommen werden, ob der zu löschende Knoten höchstens ein oder zwei Kinder hat.

Mit einem Sohn

Wenn der zu löschende Knoten keine Kinder hat kann er bedenkenlos gelöscht werden, hat er allerdings genau ein Kind, so wird der verbleibende Teilbaum einfach eine Etage nach oben geschoben. Man setzt also den Vorgängerknoten des Kindknotens auf den Entsprechenden linken oder rechten Kindknoten des Vorgängerknotens des zu löschenden Elementes sowie den entsprechend linken oder rechten Kindknoten dieses Elementes auf das Kindelement des zu löschenden Knotens. Ist der zu löschende Knoten die Wurzel, so setzen wir den Wurzelzeiger einfach auf den entsprechend folgenden Knoten.

Implementierung

Mit zwei Söhnen

Beinhaltet der zu löschende Knoten zwei nichtleere Kindknoten, so wird zunächst der kleinste Knoten des rechten Teilbaums ermittelt. Dieser ist da er im rechten Teilbaum ist in jedem Falle der Nachfolger von dem zu löschenden Knoten und beinhaltet keinen linken Kindknoten mehr. Somit wird einfach der Inhalt dieses Knotens in den zu löschenden Knoten kopiert und anschließend das ermittelte minimum gelöscht. Man vereinfacht mit dieser Methode also den Fall, dass zwei Söhne existieren, zu dem Fall, dass nur ein Sohn existiert womit die löschfunktion für einen Kindknoten angewand werden kann. Beinhaltet der BST allerdings Duplikate, so würde die oben beschiebene Vorgehensweise zu Komplikationen führen. Würde man also nur das Minimum, welches ein Duplikat im Baum aufweist( dieses Duplikat wäre dann zwangsweise das Elternelement des Minimums ), an den Platz des zu löschenden Knotens kopieren, so würden hierbei Duplikate im rechten Teilbaum des zu gelöschten Elementes übrig bleiben. Diese Fehlplatzierung würde demnach die Invariante binärer Suchbäume verletzen. Um dieses Problem zu beseitigen wird an die Position des zu löschenden Knotens die Liste aller Duplikate des Minimums aus dem rechten Teilbaum eingefügt. Somit wird der Elternknoten-Zeiger der Entsprechenden Kindknoten des zu löschenden Elementes auf das Minimum im linken Teilbaum gesetzt und dessen Kindzeiger auf die Kinder des zu löschenden Knotens. Im folgenden wird dann der Kindzeiger des zu löschenden Knotens auf das Kindelement des Duplikates mit der geringsten Tiefe gesetzt und dessen Elternpointer auf das zu löschende Element. Anschließend wird der Inhalt des im rechten Teilbaum übriggebliebenen Duplikates in das zu löschende Element kopiert. Da das im rechten Teilbaum übriggebliebende Element nun im schlimmsten Fall noch einen rechten Sohn beinhaltet, kann dieses Element nun mit der oben beschriebenen Methode zum Löschen eines Elementes entfernt werden.

Implementierung

2-3-4-Bäume

Eigenschaften

1. Knoten enthalten bis zu 3 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)

Suchen eines Elements

Beim Suchen in 2-3-4-Bäumen verwendet man die Top-Down-Methode. Dabei folgt man ausgehend von dem kleinsten Element des Wurzelknotens der entsprechenden Verkettungen bis zum gesuchten Schlüssel. Im ersten Schritt wird dabei der gesuchte Schlüssel mit dem aktiven Element verglichen. Liefert der Vergleich eine wahre Aussage ist schon an dieser Stelle die Suche beendet. Ist dies nicht der Fall wird geprüft ob der gesuchte Schlüssel kleiner als das aktive Element im aktuellen Knoten ist. Ist dieses Kriterium wahr geht man die Verkettung vor dem aktiven Element weiter entlang und setzt das kleinste Element des Kindknotens als neues aktives Element und beginnt wieder im ersten Schritt. Im Fall, dass das Kriterium nicht erfüllt ist wird im Wurzelknoten das nächstgrößere Element aktiviert und beginnt mit diesem wieder bei Schritt eins. Sollte kein nächstes Element im aktuellen Knoten vorhanden sein wird der Verkettung nach dem zuletzt aktiven Elements zum kleinsten Element des Kindknotens gefolgt und der Erste Schritt wieder ausgeführt.

Einfügen eines Elements

Günstiger Fall

Beim Einfügen wird ein Knoten solange aufgefüllt, bis er 3 Elemente enthält. Soll noch ein viertes Element aufgenommen werden ist dies nur durch ein Spalten des Knotens möglich. Dabei wird der überfüllte Knoten in 3 Teile gesplittet:

• Knoten mit zwei Elementen
• Knoten mit einem Element
• Mittleres Element

Das mittlere Element rutscht bei der Spaltung in den Elternknoten und stellt somit die Verkettung der zwei neuen Knoten dar.

Ungünstiger Fall

Muss der überfüllte Knoten wie im Günstigen Falle gespalten werden und der Elternknoten ist schon mit 3 Elementen belegt, wird das Spalten in Richtung Wurzel solange nach oben gereicht bis man entweder auf kein 4-Knoten mehr trifft oder auf die Wurzel stößt. Bei der Wurzel wird jedoch nach gleicher Aufteilungsregel eine neue Wurzel erzeugt, wenn diese ebenfalls schon voll besetzt ist.

Laufzeit: O(log n)

Split-Operation

Eine alternative Möglichkeit um dem ungünstigen Fall sofort vorzubeugen ist die Split-Operation. Dabei wird anders als bei den oben beschriebenen Methoden, während ein Element in den Baum eingefügt wird beim Durchlauf zusätzlich nach 4-Knoten gesucht, die daraufhin ausgepalten werden. Somit wird die Split-Operation im schlimmsten Fall einmal durchgeführt.

Löschen eines Elements

Das Löschen eines Elements aus einem Knoten lässt sich immer auf das Löschen eines Elements in einem Blatt zurückführen. Dafür ist es zunächst nötig die Position des zu löschenden Elements zu wissen. Neben dieser Position i wird außerdem das Element benötigt, welches sich an der äußersten rechten Stelle befindet um beide Elemente zu tauschen. Nun kann das Element aus dem Blatt gelöscht werden, wobei drei Fälle zu unterscheiden sind:

• mehr als ein Element im Blatt - einfaches Entfernen
• ein Element im Blatt und Nachbarknoten (gleicher Vorgänger) mindestens zwei Elemente - leihen eines Elements aus dem Nachbarknoten - Schlüssel in Vorgängerknoten verschieben - Vorgängerelement des zu löschenden Elements rückt an dessen Position und ersetz dieses
• nur ein Element im Blatt und Nachbarknoten - Element entfernen - Vorgängerelement mit Nachbarelement zusammengefügt
• vorhergehender Fall und Vorgängerknoten nur ein Element - gleihe Operation auf höherer Ebene

A-V-L-Bäume

Eigenschaften

1. balancierte Knoten
2. Höhenunterschied = 1
3. Rotation um mittleres Element

Balancekriterium

Höhenunterschied = HöheRechts - HöheLinks

Suchen

Einfügen

Löschen

B-Bäume

Eigenschaften

• jeder Knoten besteht aus min. k und max. 2k Elemente
• unterschiedliche Anzahl von Elementen in Knoten möglich
• Wurzel besteht aus zwischen 1 und 2k Elementen
• Knoten mit n Elementen besitzt n+1 Verkettungen
• Blätter haben keine bzw. undefinierte Verkettungen

Suchen eines Elements

Der Suchalgorithmus arbeitet nach dem gleichen Schema, wie es bei 2-3-4-Bäumen auftritt.

Einfügen eines Elements

Löschen eines Elements

B*-Bäume

Vergleich B-Bäume und B*-Bäume

Vor- und Nachteile

B+-Bäume

Eigenschaften

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

Der erste Fall beschreibt den Sachverhalt, dass der neu eingefügte Knoten die Wurzel des Baumes darstellt. Dies würde berreits die Eigenschaft, dass die Wurzel des Baumes schwarz sein muss verletzen. Aus diesem Grund wird die noch rote Wurzel schwarz gefärbt wodurch das Gleichgewicht wieder hergestellt ist.

insertCase1( Knoten n )
    if n.parent is null
        n.color = BLACK
    else insertCase2( n )

Fall 2

Ist der Vater des neuen Knotens schwarz, so tritt der zweite Fall ein. In diesem Fall könnte der Gedanke aufkommen, dass die fünfte Eigenschaft, also dass der Baum auf allen Pfaden von der wurzel zu den Blättern die gleiche Schwaarztiefe besitzt. Da allerdings ein schwazknoten( Nil ) beim einfügen gelöscht wird bleibt die Schwarztiefe im Baum erhalten und es ist nichts weiter zu tun.

insertCase2( Knoten n )
if n.parent.color is BLACK
    return
else insertCase3( n )

Fall 3

Ab dem Fall drei beginnent, kann davon ausgegangen werden, dass der einzufügende Knoten einen Großvater besitzt, da der Vater rot sein muss ( sonst wäre bereits Fall eins oder Fall zwei eingetreten ) und damit nicht die Wurzel sein kann. Somit beschreibt der dritte Fall die Situation, dass sowohl der Onkel als auch der Vater rot sind. Da durch das Anhängen eines weiteren roten Knotens nun die Eigenschaft verletzt wird, dass ein roter Knoten immer zwei schwarze Kindknoten haben muss, werden der Onkel sowie der Vaterknoten schwarz und der Großvater rot gefärbt. Mit diesem Verfahren sowie der Hilfe der Verfahren von Fall eins und Fall zwei verschiebt man das Problem also soweit nach oben bis es sich auflöst, andernfalls betrachtet man einen neuen Fall.

insertCase3( Knoten n )
if uncle( n ) not null and uncle( n ).color is RED
    n.parent = BLACK
    uncle( n ).color = BLACK
    grandparent( n ).color = RED
    insertCase1( n )
else insertCase4( n )

Fall 4

Der nächste Fall betrachtet die Situation, dass der Onkel des neuen Knotens schwarz ist( kann also auch Nil sein ) und der neue Knoten das rechte Kind seines roten Vaters ist, welcher jedoch links an seinem Größvater sitzt. Analog dazu kann der neu einzufügende Knoten auch das linke Kind seines roten Vaters sein, welcher rechts an seinem Großvater angebracht ist. Im ersten der beiden Fälle wird eine Linksrotation und im zweiten eine Rechtsrotation um den Vater durchgeführt. Anschließend wird in jedem Falle der fünfte und damit letzte Fall überprüft.

insertCase4( Knoten n )
if n is n.parent.right and n.parent is gradnparent( n ).left
    rotateLeft( n.parent )
    n = n.left
else 
    if n is n.parent.left and n.parent is gradnparent( n ).right
        rotateRight( n.parent )
        n = n.right
insertCase5( n )

Fall 5

Der letzte Fall beinhaltet die Situationen, dass der neue Knoten einen schwarzen Onkel hat( auch Nil ist schwarz ) und der linke Knoten seines Vaters ist, der sich ebenfalls links am Großvater befindet bzw. dass der neue Knoten rechts an seinem Vater hängt, der sich ebenfalls am Großvater befindet. Da in diesem Fall die Eigenschaft verletzt ist, dass der Vater des neuen knoten keine zwei schwarzen Kinder aufweisen kann, bedient man sich einer Rechtsrotation, sofern der neue Knoten links an seinem Vater ist und sich dieser links am Großvater befindet. Im entgegengesetztem Fall bedient man sich der Linksrotation um den Großvater. Anschließend wird der ehemalige Vater schwarz und der ehemalige Großvater rot gefärbt.

insertCase5( Knoten n )
n.parent.color = BLACK
grandparent( n ).color = RED
if n is n.parent.left and n.patent is grandparent( n ).left
    rotateRight( grandparent( n ) )
else rotateLeft( grandparent ( n ) )

Löschen

Fall 1

Fall 2

Fall 3

Fall 4

Fall 5