Aktuelle Version vom 18. Januar 2017, 16:16 Uhr

Ein Baum ist eine der am häufigsten verwendeten rekursiven Datenstrukturen. Bäume gehören zu den dynamischen Datenstrukturen. Die in dieser Veranstaltung behandelten Bäume sind hauptsächlich binäre Bäume. Bäume eignen sich vor allem zum strukturierten Abspeichern von Daten. Die interne Repräsentation hängt dabei von der Implementierung der Datenstruktur ab.

Repräsentativer Aufbau

Ein Baum ist entweder leer oder besteht aus einem einzelnen Knoten mit Unterbäumen. Die Unterbäume selbst können wiederum leer oder ein weiterer Knoten mit Unterbäumen sein.

Der erste Knoten in einem Baum, also ohne Vorgänger, wird als Wurzel bezeichnet. Ein Knoten ist immer Wurzel seines eigenen (Unter-)Baumes.

Der direkte Nachfolger eines Knotens wird als sein Kind bezeichnet.

Wenn ein Knoten keine Unterbäume hat, gilt er als Blatt.

Ein Knoten, der weder Blatt noch Wurzel ist, gilt einfach als innerer Knoten.

Eigenschaften und Begriffe

Binärbaum

Ein Binärbaum ist ein Baum, dessen Knoten genau zwei Kinder haben. Die beiden Kinder werden meistens als linkes und rechtes Kind bezeichnet.

Heaps und Binäre Suchbäume sind spezielle Binärbäume. Diese Strukturen ermöglichen für bestimmte Verwendungszwecke sehr effiziente Algorithmen .

Ebene

Zwei Knoten, die den gleichen Abstand zur Wurzel des Baumes haben, befinden sich auf der gleichen Ebene.

Eine Ebene wird als vollständig bezeichnet, wenn alle möglichen Knoten in einer Ebene auch existieren.

Eine Ebene ist linksvollständig, wenn von links an eine Ebene lückenlos gefüllt ist, aber nicht unbedingt vollständig ist.

Suchbaum

Ein Suchbaum ist ein Baum mit einer besonderen Struktur. Die Position der Knoten zueinander wird dabei durch eine Ordnung bestimmt: Kleinere Werte werden meistens links und größere Werte rechts von einem Knoten einsortiert.

Diese Ordnung gestattet eine zielgerechte Navigierung durch den Baum und reduziert somit die Suche nach einem gewünschten Wert auf logarithmische Laufzeit in Abhängigkeit von der Tiefe des Baumes. In Listen wird hierfür lineare Laufzeit benötigt.

Ein In-Order-Durchlauf eines binären Suchbaums gibt zudem eine sortierte Liste aus.

Implementierung

Ein Baum kann sowohl objektorientiert als Datenstruktur aufgebaut werden, als auch durch ein Array repräsentiert werden.

Implementierung als Array

Die Repräsentation des Baumes als Array ist im Allgemeinen nur dann nützlich, wenn der Baum linksvollständig besetzt werden soll.

Dabei werden die einzelnen Zellen des Arrays als Knoten interpretiert und die Eltern-Kind-Beziehung durch die passende Position im Array repräsentiert. Für einen Knoten an Position i ist der Knoten an Position 2i und 2i+1 ein Kind. Entsprechend ist für den Knoten an Position i der Knoten an Position i/2^[1] Vater/Mutter.

Der Index 0 wird dabei ignoriert. Stattdessen ist der Index 1 die Wurzel des Baumes.

Objektorientierte Implementierung

Eine objektorientierte Implementierung repräsentiert einen Baum mithilfe von Knotenobjekten. Dabei kann entweder jeder Knoten selbst alle Operationen eines Baumes umsetzen oder die Verwaltung einer zweiten Baumklasse überlassen. Ein Knoten besitzt dabei Referenzen auf seine Kinder und ein Attribut, um seinen Wert zu repräsentieren. Hinzufügen, entfernen, ändern, suchen etc. findet dabei meist rekursiv statt.

Verwendung

Heaps werden meistens zur Implementierung von Prioritätswarteschlangen verwendet, oder als Trägerstruktur für Sortieralgorithmen.

Binäre Suchbäume werden meistens zur Implementierung von Mengen verwendet, da das Hinzufügen und Suchen hier relativ schnell möglich ist. Die verschiedenen Arten der Baumdurchläufe haben in dieser Datenstruktur zudem Eigenschaften, die bei verschiedenen Problemstellungen zu relativ effizienten Algorithmen führen.

Anwendung zum Sortieren

Ist eine gegebene Menge an zu sortierenden Zahlen gegeben, können diese mithilfe eines binären Suchbaumes sortiert werden. Zuerst werden die gegebenen Zahlen in einen neuen Binärbaum eingefügt. Anschließend gibt man den In-Order-Durchlauf des Baumes aus. Dieser gibt, Aufgrund der Struktur des Baumes, die Zahlen aufsteigend sortiert aus.

Alternativ kann man alle gegebenen Zahlen einem Heap hinzufügen und nacheinander die Wurzel des Heaps entfernen und ausgeben. Dadurch, dass durch die Operationen des Heaps das kleinste bzw. größte Element immer in der Wurzel zu finden ist, gibt man also alle gegebenen Zahlen in auf-, bzw. absteigende Reihenfolge aus.

Der Heap ist nach diesem Verfahren jedoch leer, während der Binärbaum für weitere Berechnungen verwendet werden kann.

Beispielcode

public static void printSorted(int[] array){
    BinarySearchTree tree = new BinarySearchTree();
    for(int i = 0; i < array ; i++){
        tree.add(array[i]); //Fügt dem Baum jede zu sortierende Zahl hinzu
    }
    tree.printInOrder();
}

Fußnoten

1. ↑ Integerdivision: Division zweier Zahlen ohne Rest