4 Bäume und Graphen

Folgendes Beispiel zeigt die Merkmale eines Baums. Dieser Baum ist höhenbilanziert aber nicht vollständig, weil es zum Beispiel auf dem Niveau 3 nur 5 Knoten gibt anstatt der erforderlichen 8 (2 hoch 3).

4.1.1 binäre höhenbilanzierte Suchbäume

Ist ein binärer Suchbaum nicht höhenbilanziert, kann er durch Links- oder Rechtsrotation umstrukturiert werden.

Das folgende UML-Diagramm und die Instanzsicht zeigen, wie ein binärer Suchbaum implementiert werden kann. Diese Diagramme zeigen nur eine Möglichkeit der Implementierung, es gibt noch weitere Ansätze.

Um ein Element aus einem Binärbaum zu löschen müssen, abhängig von der Anzahl der Nachfolger, folgende Regeln beachtet werden.

Das zu löschende Element ist/hat

• ein Blatt --> einfach aus dem Baum herausnehemen (Knoten auf null setzen)
• einen Nachfolger --> der Nachfolger ersetzt das zu löschende Element
• zwei Nachfolger --> das zu löschende Element durch das kleinste/größte Element des rechten/linken Teilbaums ersetzen

4.1.2 Vielwegbäume

Bei Vielwegbäumen ist der Grad des Baumes > 2, d.h. es können mehr als 2 Kindelemente vorkommen. Folgendes UML-Diagramm und Instanzsicht sollen zeigen, wie so ein Baum implementiert werden kann. Dabei kann die Liste, die hier als Array dargestellt ist, einfach als Java Collection umgesetzt werden.

Collection<VielwegNode> subNodes = new Vector<VielwegNode>();

4.2 B-Bäume

B-Bäume sind nach Rudolph Bayer benannt, dabei steht das B nicht für binär, sondern Knoten in einem B-Baum können mehr als ein Element haben. Jeder B-Baum hat eine Ordnung m, dabei gilt

• alle Wege von der Wurzel zu den Blättern sind gleich lang
• alle Knoten besitzen die gleiche Anzahl von (möglichen) Einträgen (2m)
• jeder Knoten besitzt zwischen m und 2m Elementen (Ausnahme bei der Wurzelt, sie kann 1 bis 2m Elemente besitzen)
• Blattknoten haben keine Nachfolger
• jeder sonstige Knoten hat i+1 Nachfolger, falls i die Anzahl der Elemente des Knotens ist.

Ein B-Baum könnte wie folgt aussehen, dabei stehen zwischen den Elementen eines Knotens immer Verweise, die auf den nächsten Unterbaum verweisen. Eine Reihenfolge nach der Größe der Elemente wird dabei beigehalten.

4.2.1 Suchen in B-Bäumen

Soll nach einem Element in einem B-Baum gesucht werden wird folgendermaßen vorgegangen

• Start beim Wurzelknoten x und überprüfen ob x gleich oder größer einem Element ist,
• wenn x gleich einem Element, wurde er gefunden und kann zurückgeliefert werden
• wenn x > einem Element ist, wird im nächsten Unterbaum gesucht, auf den der Verweis zeigt
• weiteres Vorgehen, wie im Wurzelknoten
• sobald ein Blattknoten erreicht ist, überprüfen ob x das Element ist, wenn ja dann ist das Element gefunden, wenn nein ist das Element im B-Baum nicht enthalten.

4.2.2 Einfügen in B-Bäume

Beim Einfügen von Elementen in B-Bäume wird wie folgt vorgegangen

• Suchen nach der passenden Position des Elements und einfügen
• Überprüfen, ob im Knoten <= 2m Elemente sind
• wenn ja, Element dort belassen
• wenn nein, das mittlere Element einen Knoten nach oben verschieben, dort auch wieder auf <= 2m Elemente prüfen und gegebenenfalls rekursiv fortfahren

Ein kleines Beispiel um das Vorgehen des Einfügens zu verdeutlichen. Es sollen die Zahlen 1, 5, 2, 6, 7, 4 in einen B-Baum eingefügt werden.

4.2.3 Löschen in B-Bäumen

Beim Löschen eines Elements müssen folgende Regeln beachtet werden

• es müssen mindestens m Elemente im Knoten bleiben
• Element ist ein Blatt --> Element löschen
• Element ist ein Knoten --> Element löschen und durch nächst kleineres ersetzen

In beiden Fällen müssen eventuell Unterlauf-Behandlungen durchgeführt werden. Dabei gibt es zwei verschieden Möglichekeiten

1. Reorganisation: Falls die Seite und ihre Nachbarseite nach dem Löschen die Mindestanzahl an Elemente hat, können die Elemente neu verteilt werden: neues mittleres Element bestimmen, dieses wird neues Elternelement, die verbleibenden Elemente auf beide Seiten verteilen.
2. Zusammenlegen von Seiten: Falls die Seite und ihre Nachbarseite nach dem Löschen nicht mehr über genügend Elemente verfügen, werden die Elemente der beiden Seiten und des eingeschlossenen Elternelements auf eine Seite zusammengelegt.

Das Löschen eines Elements und beide Möglichkeiten der Unterlauf-Behandlungen sollen anhand eines Beispiels verdeutlicht werden.

Das 1. Beispiel zeigt das einfach Löschen eines Elements ohne weitere Unterlaufbehandlung.

Das zweite Beispiel zeigt das Löschen eines Elements mit nachfolgener Reorganisation als Unterlaufbehandlung.

Das letzte Beispiel verdeutlicht das Zusammenlegen von Seiten als Unterlaufbehandlung nach dem Löschen eines Elements.

4.3 Graphen

Ein Graph sind durch Kanten verbundene Knoten. Die Unterschiede zu Bäumen sind

• es sind mehrere Vorgängerelemente möglich
• es kann mehre Wurzelelelemente geben
• zyklische Abhängigkeiten sind erlaubt.

In einem Graphen, können gerichtete und ungerichtete sowie gewichtete und ungewichtete Kanten existieren. Eine Beispielanwendung für einen Graphen mit gewichteten Kanten ist z.B. eine Routenplanung, dabei entsprechen die Gewichtungen den Entfernungen.

Für die Implementierung eines Graphens ist es sinnvoll zuerst eine Adjazenzmatrix zu erstellen. Dafür wird eine quadaratische Matrix mit allen Knoten als Spalten wie auch Reihen aufgestellt. Für jede existierende Verbindung wird eine 1 oder auch die Gewichtung der Kante eingetragen.

Für jeden Knoten kann nun eine lineare Liste angelegt werden. Jeder linearen Liste werden nun alle Knoten hinzugefügt, die in der Reihe des jeweiligen Knotens durch eine Zahl als verbundenen Knoten markiert sind. Das heisst für den Knoten 1 werden die Knoten 2 und 4 angehängt, weil in der Reihe für Knoten 1 bei den Knoten 2 und 4 eine Zahl steht. Die Implementierung für diesen Graphen muss wie folgt aussehen.

4.3.1 Spezielle Graphen

In der Graphentheorie gibt es spezielle Graphen, den Eulerschen Kreis und den Eulerschen Weg.

Eulerscher Kreis: an jedem Knoten gibt es eine gerade Anzahl von Kanten, er kann mit einem Rundweg durchlaufen werden

Eulerscher Weg: es gibt genau 0 oder 2 Knoten mit ungerader Kantenanzahl

Es gilt: Eulerscher Kreis ist immer ein Eulerscher Weg (Umkehrschluss gilt nicht!!)

So ist z.B. das Haus vom Nikolaus kein Eulerscher Kreis aber ein Eulerscher Weg (beide unteren (=genau 2) Knoten haben nur 3 Kanten), siehe folgendes Beispiel.

4.3.2 Page-Rank Algorithmus

Das Erfolgsgeheimnis der Google-Suchmaschine ist das Page-Rank-Verfahren. Der Hauptakspekt dieses Verfahren ist, "wichtige" Internet-Seiten von "unwichtigen" Internet-Seiten zu unterscheiden. Dazu soll jede internetseite einen eigenen PageRank definiert bekommen, die deren Wichtigkeit bewertet.

Der PageRank einer einer Seite berechnet sich wie folgt

 PR(a) = d*(PR(T1)/C(T1)+....+PR(Ti)/C(Ti))+(1-d)*(1/AnzahlSeiten)

dabei ist PR(a) der PageRank der Seite a

               PR(Ti) der PageRank der Seiten Ti, von denen ein Link auf Seite a zeigt

               C(Ti) die Gesamtzahl der Links auf Seite Ti

                d      ein Dämpfungsfaktor.

Der Dämpgunsfaktor liegt zwischen 0 und 1 und soll das Ausmaß der Weitergabe des PageRanks von einer Seite auf eine andere verringern. Das ist deswegen notwendig, weil nicht immer von einer Seite zur anderen navigiert wird, manchmal wird auf eine Seite direkt zugegriffen, oder mit dem Rückwärtsbutton eine vorherige Seite aufgerufen. Die Navigationsmöglichkeiten über Links werde damit übergangen.

Um die Formel mit ihren etwas kryptischen Variablen besser zu verstehen soll folgendes Beispiel helfen. Die folgende Abbildung zeigt 6 Webseiten, die über Links miteinander verbunden sind.