Version vom 28. Januar 2016, 23:43 Uhr

Ein Baum ist eine der am häufigsten verwendeten rekusiven Datanstrukturen. 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 Datanstruktur ab.

Repräsentierter Aufbau

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

Ein Knoten gilt als Blatt, wenn er keine Unterbäume hat.

Ein Knoten ist immer Wurzel seines eigenen (Unter-)Baumes.

Eigenschaften und Begriffe

Binärbaum

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

Die Verwaltung von Daten in Binärbäumen wird im speziellen in Heaps und in Binären Suchbäumen verwendet. Diese erlauben für bestimmte Verwendungszwecke sehr effiziente Algorithmen.

Ebene

Zwei Knoten, die den gleichen Abstand zur Wurzel des Baumes haben, befinden sich in 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 zumindest 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 Positioon der Knoten zueinander wird dabei durch eine Ordnung bestimmt. Kleinere Werte werden dabei zumeist links von einem Knoten einsortiert, während größere Werte rechts von einem Knoten landen. Dadurch kann man bei der Suche, ob ein gewünschter Wert im Baum bereits einsortiert wurde, zielgerecht durch den Baum navigieren und so die Suche von linearer Zeit bei Listen auf logarithmische Laufzeit (in Abhängigkeit zur Tiefe des Baumes) reduzieren. 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.

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. Dabei ist für einen Knoten an Position i 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] Elter. Der Index 0 wird dabei ignoriert und der Index 1 ist die Wurzel des Baumes.

Objektorientiert

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

Verwendung

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

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

Fußnoten

1. ↑ Integerdivision