Startseite < Informatik < Algorithmen Datenstrukturen < Stack Queue [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] Tree < BinaryTree > > / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >
Tree
Die Datenstruktur Tree stellt einen speziellen Graphen dar.
Einführung Definitionen zum Baum
Was versteht man unter Tree in der Informatik?
Ein Tree, zu Deutsch Baum oder baumartige Datenstruktur, ist eine häufig genutzte Datenstruktur in der Informatik.

Diese baumartige Datenstruktur definiert sich rekursiv wie folgt:
  1. Ein einzelner Knoten ist ein Baum.
  2. Ein Knoten mit beliebig vielen Teilbäumen ist ein Baum.
Dabei wird ein terminaler Knoten, also ein Knoten ohne Teilbäume, oft als Blatt (Blattknoten) bezeichnet. Der Knoten, der nicht Teil eines anderen, übergeordneten Knotens ist, wird als Wurzel (Wurzelknoten) bezeichnet.

Bezüglich der Graphentheorie ist ein Baum ein zyklenfreier, zusammenhängender Graph mit einem einzigen Wurzelknoten. Vom Wurzelknoten aus können jeder Ast sowie jedes Blatt des Baumes erreicht werden. Das heißt, will man von einem Teilbaum zu einem anderen navigieren, führt der Weg schlimmstenfalls über die Wurzel.

Es mag Sie vielleicht ein wenig verwundern, dass hier ständig botanische Ausdrücke wie Wurzel, Ast oder Blatt gebraucht werden. Doch diese Ausdrücke sind üblich in diesem Fach, wenn man sich über eine baumartige Datenstruktur unterhält. Erklärungen bezüglich dieser Datenstruktur fallen einfach leichter.
  • Möchte ich zum Beispiel erklären, dass aus Informatikersicht ein Wald auch als Baum modelliert werden kann, dann kann ich dies vollständig auf metaphorischer Ebene deutlich machen.
    Eine Ameise (Metapher für Visitor) kann ja jedes Blatt des Baumes besuchen, ohne dabei den Baum verlassen zu müssen. Schlimmstenfalls muss sie den denkbar weitesten Umweg über die Wurzel des Baumes nehmen, aber den Baum muss sie dabei nicht verlassen. Ich behaupte jetzt, dass die Ameise jedes Blatt eines Waldes besuchen kann! Warum dem so ist, können Sie sich mit Ihrem jetzigen Stand durchaus selbst erschließen. Ich selbst komme zu dem Resultat, dass der Waldboden die Wurzel des Waldes ist. Wenn man die ganze Sache weiter spinnt, stellt die Modellierung von Fallholz sowie von herabgefallenem Laub auch kein Problem mehr dar. Herabgefallene Baumbestandteile sind aus Informatikersicht Teilbäume der Wurzel des Waldes.
    Und jetzt behaupte ich, dass eine Ameise jedes Blatt aller Wälder eines Kontinents besuchen kann! :-)
  • Es fällt mir mit Metaphern auch nicht schwer zu erklären, was ich mir unter verketteten Blattknoten vorstelle.
    Um der besagten Ameise bei ihrer Baumwanderung weite Umwege zu ersparen, kann ich doch um den Baum ein Netz spannen, sodass die Ameise über das Netz von einem Blatt zum nächsten ohne Umwege wandern kann. Übertragen auf einen Informatikbaum werden alle Blattknoten miteinander verkettet, jedes Blatt ist mit mindestens einem Nachbarblatt unmittelbar (quasi mit dem Netz) verbunden. Dies benötigt man in der Informatik hin und wieder. Sagen wir mal, die Blattknoten repräsentieren Wörter eines Aufsatzes. Wenn ich nun einen Satzanfang gefunden habe, möchte ich auch den Rest des Satzes lesen. Dann lese ich einfach entlang der Blattkette.
Ein Baum wird in der Informatik auch oft als Liste von Listen repräsentiert. In manchen Programmiersprachen gibt es beispielsweise keine andere Möglichkeit, Bäume zu konstruieren. Ich denke da zum Beispiel an funktionale Programmiersprachen.
Was versteht man unter einem Verzweigungsgrad?
Der Verzweigungsgrad (branching factor) ist die Anzahl der Teilbäume, die ein Knoten des Baumes haben kann. Manchmal wird der Verzweigungsgrad auch als Ordnung bezeichnet. Ist die Rede von einem maximalen Verzweigungsgrad k, so gibt es im Baum keinen Knoten der mehr als k Teilbäume besitzt oder besitzen kann.
  • Ein Baum mit dem maximalen Verzweigungsgrad 2 ist beispielsweise ein Binärbaum.
  • Ein Baum kann aber auch zu einer Liste entarten, wenn der maximale Verzweigungsgrad 1 ist.
Der Verzweigungsgrad spielt manchmal bei Komplexitätsabschätzungen eine besonders wichtige Rolle. Es gibt Algorithmen, deren Laufzeitverhalten stark vom Verzweigungsgrad eines Eingabebaumes abhängt.
Anwendungsfälle Anwendungsfälle für einen Baum
Alleinig zu wissen, was ein Baum in der Informatik darstellt, reicht eigentlich nicht aus, wenn man das Potential eines Baumes nicht zu nutzen weiß. Deshalb sind an dieser Stelle ein paar Anwendungsfälle aufgelistet.
Gliederungen
Für Gliederungen im Allgemeinen bietet sich stets eine baumartige Datenstruktur an. Beispielsweise stellt jedes Inhaltsverzeichnis einen Baum von Überschriften oder gar Inhalten dar. Das heißt, dass die Inhalte eines Schriftwerkes mittels baumartiger Datenstruktur repräsentiert werden. Wer schon mal mit LaTeX gearbeitet hat, weiß, wovon ich schreibe.

Ein Autor eines Buches kann den gesamten Inhalt, nicht nur die Überschriften, sondern auch die Textabschnitte, in eine baumartige Datenstruktur eingliedern. So hat er die Möglichkeit, das Inhaltsverzeichnis automatisch generieren zu lassen. So kann er sich hässliche Aufwände sparen, wie zum Beispiel die händische Synchronisation des Inhaltsverzeichnisses mit den tatsächlichen Inhalten des Buches.
Vorliegende Homepage baut auf demselben Prinzip auf. Die gesamte Website, also komplett ‚www.stefan-baur.de’, wird durch einen einzigen Baum repräsentiert; das Menü, das Inhaltsverzeichnis sowie jede einzelne Seite, jeder Textbaustein, so klein er auch sein mag, werden über Operationen der Baumstruktur automatisch erzeugt. So kann ich mich als Homepagebetreiber auf das Wesentliche, auf den eigentlichen Inhalt, konzentrieren, anstatt mich mit unnötigen Synchronisationsproblemen herumschlagen zu müssen.

Der Einsatz einer so simplen Datenstruktur wie die hier erläuterte vereinfacht die Arbeit eines Autors enorm; Inkonsistenzen bezüglich der Gliederung entstehen gar nicht erst. Im Allgemeinen kann man durch sinnvollen Einsatz einer (baumartigen) Datenstruktur gewissen Problemen aus dem Wege gehen (ein Beitrag zur Qualitätssicherung).
Datumssuche in Datenbanken
In Datenbanken werden Bäume dazu verwendet, bestimmte Daten möglichst schnell zu finden. Die Daten der Datenbank werden nach bestimmten Ordnungskriterien in so genannten Indexbäumen eingegliedert. Benötigt man nun ein bestimmtes Datum, so wird zunächst die Wurzel befragt, in welchem Teilbaum das Datum zu finden sei. Dieses Befragen setzt sich in den Teilbäumen fort, bis eben das Datum gefunden wird oder andernfalls bis ein terminaler Knoten angibt, dass das gesuchte Datum nicht vorhanden sei. Der Vorteil bei dieser Vorgehensweise mit einer baumartigen Struktur ist, dass nicht jedes einzelne Datum der Datenmenge befragt werden muss, ob es sich um das gesuchte Datum handle, sondern dass der Baum in nur wenigen Schritten (die Tiefe des Baumes; bei n Daten beträgt die Tiefe des Baumes etwa log(n)) das Datum findet oder nicht findet (falls nicht vorhanden).

Zum besseren Verständnis erinnere ich an dieser Stelle an das vorhergehende Gliederungsbeispiel:
  1. Um einen Textabschnitt in einem Buch möglichst schnell zu finden, blättern Sie sicherlich nicht das gesamte Buch durch, sondern nutzen das dafür vorgesehene Inhaltsverzeichnis. Da das Inhaltsverzeichnis eine baumartige Struktur aufweist, können Sie entsprechend effizient suchen, schlimmstenfalls müssen Sie das gesamte Inhaltsverzeichnis durchgehen.
    Die Suche nach einem Datum in einer Datenbank läuft im Wesentlichen analog zur gerade beschriebenen Abschnittsuche in einem Buch ab.
  2. Wenn Sie in einem Buch besonders schnell einen Begriff finden wollen, nutzen Sie bestimmt das Stichwortverzeichnis. Da das Stichwortverzeichnis nach den Anfangsbuchstaben der Stichwörter gegliedert ist, haben Sie es noch leichter. Ein Indexbaum einer Datenbank ist im Prinzip nichts anderes als ein baumartig strukturiertes Stichwortverzeichnis einer Datenmenge, mit dem Ziel, ein Datum aus einer extrem großen Datenmenge extrem schnell zu finden.
Mit einer baumartigen Datenstruktur ist man in der Lage, die Laufzeitkomplexität für Suchfunktionen von O(n) auf O(log n) herunterzubrechen.
Realisierung Realisierung eines Baumes
Verwendung eines Entwurfsmusters
Es gibt einige unterschiedliche Herangehensweisen, eine baumartige Datenstruktur zu realisieren. Einleitend war zum Beispiel die Rede von einer Liste von Listen, und in Urzeiten der Informatik hat man irgendwas mit Zeigern verbrochen. Doch unterm Strich können alle Ansätze auf ein ganz bestimmtes Entwurfsmuster zurückgeführt werden. Das einzig wahre Entwurfsmuster, mit dem eine baumartige Datenstruktur aufgebaut werden kann, nennt sich Kompositum und gehört zur Kategorie der — wie könnte es auch anders sein — Strukturmuster.

Im Folgenden sehen Sie eine stark vereinfachte Implemenation eines Kompositums.
SimpleTreeNode (Source-Code)
import java.util.LinkedList;

// Jeder Knoten besitzt einen Namen und ggf. Kindknoten.
// Ein Knoten ohne Kinder ist hier automatisch ein Blattknoten.
// Der Knotentyp heißt hier SimpleTreeNode.

public class SimpleTreeNode {

    private String name;
    private LinkedList<SimpleTreeNode> children;

    public SimpleTreeNode(String name) {
        this.name = name;
        this.children = new LinkedList<SimpleTreeNode>();
    }

    // Kindknoten hinzufügen.
    public SimpleTreeNode add(SimpleTreeNode child) {
        this.children.add(child);
        return child;
    }

    // Baum als Text.
    public String toString() {
        return this.toString("");
    }

    // Baum als Text mit einem bestimmten Einrückstring.
    public String toString(String indent) {
        String result = "";

        result += indent + this.name + "\r\n";

        for (int i = 0; i < this.children.size(); i++) {
            result += this.children.get(i).toString(indent + (i + 1) + ".");
        }

        return result;
    }

    // Kleiner Baumtest, lass wachsen!
    public static void main(String[] arguments) {

        /* Baum aufbauen. */

        // Die Wurzel des Baumes.
        SimpleTreeNode root = new SimpleTreeNode("Wurzel (Mein Buch)");

        // Erster Teilbaum der Wurzel.
        SimpleTreeNode branch1 = root.add(new SimpleTreeNode("Ast (Einleitung)"));
        branch1.add(new SimpleTreeNode("Blatt"));
        branch1.add(new SimpleTreeNode("Blatt"));
        branch1.add(new SimpleTreeNode("Blatt"));

        // Zweiter Teilbaum der Wurzel.
        SimpleTreeNode branch2 = root.add(new SimpleTreeNode("Ast (Hauptteil)"));
        branch2.add(new SimpleTreeNode("Blatt"));
        SimpleTreeNode branch22 = branch2.add(new SimpleTreeNode("Ast"));
        branch22.add(new SimpleTreeNode("Blatt"));
        branch22.add(new SimpleTreeNode("Blatt"));
        branch22.add(new SimpleTreeNode("Blatt"));
        branch22.add(new SimpleTreeNode("Blatt"));
        branch22.add(new SimpleTreeNode("Blatt"));
        branch2.add(new SimpleTreeNode("Blatt"));

        // Dritter Teilbaum der Wurzel.
        root.add(new SimpleTreeNode("Blatt (Schluss)"));

        /* Ausgabe des Baumes */

        System.out.println(root.toString());
    }
}
⇑ SimpleTreeNode (Source-Code) ⇑
Nach Ausführung des hier gezeigten Java-Codes erhalten Sie folgende simple Textausgabe, welche wiederum stark an eine Gliederung erinnert. Sie erkennen bestimmt schon einen bereits oben erwähnten Vorteil einer baumartigen Datenstruktur: Die Gliederungspunkte werden selbst bei einem so primitiven Implementierungsbeispiel automatisch durchnummeriert. Würde man beispielsweise ein weiteres Kapitel dazwischenschieben wollen, muss man sich über die Nummerierung keine Gedanken mehr machen.
java SimpleTreeNode
Wurzel (Mein Buch)
1.Ast (Einleitung)
1.1.Blatt
1.2.Blatt
1.3.Blatt
2.Ast (Hauptteil)
2.1.Blatt
2.2.Ast
2.2.1.Blatt
2.2.2.Blatt
2.2.3.Blatt
2.2.4.Blatt
2.2.5.Blatt
2.3.Blatt
3.Blatt (Schluss)
⇑ java SimpleTreeNode ⇑
Es bleibt Ihrem Ehrgeiz überlassen, die Methode toString der Klasse SimpleTreeNode derart umzuschreiben, dass der Baum als XML-Struktur ausgegeben wird. Diesbezüglich können Sie sich von der Java-Methode toXML unter Dequeue beflügeln lassen. Nebenbei bemerkt, wird mit XML in der Regel ein für den Menschen lesbarer Objektbaum beschrieben.
Startseite   Sitemap   Downloads   Hilfe   Impressum  
Startseite < Informatik < Algorithmen Datenstrukturen < Stack Queue [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] Tree < BinaryTree > > / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >