Baum Datenstruktur als abstrakter Datentyp mit Beispielen

Baum Datenstruktur

In diesem Beitrag wird die Baum Datenstruktur als abstrakter Datentyp betrachtet. Ein Baum enthält üblicherweise drei Arten von Knoten:

  1. Wurzelknoten: Ist der Ursprung und besitzt keine Elternknoten, dafür aber beliebig viele Kindknoten.
  2. Innerer Knoten: Befinden sich im Inneren eines Baums und hab einen Eltern Knoten und mindestens einen Kindknoten.
  3. Äußere Knoten: nennt man auch Blattknoten. Sie haben keine weiteren Kindknoten mehr.
Baum als Datentyp einfache Baumstruktur
Baum als Datentyp einfache Baumstruktur

Verketteter Baum

Ein verketteter Baum ist vergleichbar mit einer verketteten Liste. Unsere Knoten sind Objekte, die ihre Kindknoten als Referenz speichern. Eine sehr wichtige Bedingung ist, dass keine Referenz auf den Wurzelknoten zurück führen darf, da so ein Kreis entsteht und ein Kreis ist laut Definition kein Baum. Außerdem muss zu jedem anderen Knoten genau eine Referenz führen, das heißt, der Baum muss zusammenhängend sein. Ein abgefallenes Blatt zählt demnach nicht mehr zum Baum. 

Tiefensuche

Die Tiefensuche wird genutzt, um eine Baumstruktur zu durchsuchen. Begonnen wird dabei bei der Wurzel, falls die Wurzel das gesuchte Element ist, ist die Suche beendet. Andernfalls wird das erste Kind vollständig durchsucht, danach das Zweite usw. Wenn keins der Kindknoten den Wert enthält, kann das gesuchte Element bzw. der gesuchte Wert nicht gefunden werden.

Effizienzklasse: O(n)

Beispiel: Wir suchen die „7″ in unserem Baum.

Tiefensuche mit pre-order Traversierung einer Baum Datenstruktur.
Tiefensuche mit pre-order Traversierung einer Baum Datenstruktur.

Der hier abgebildete Baum in Verbindung mit der pre-order Tiefensuche stellt den “worst-case” dar, weil der gesuchte Wert erst beim letzten Knoten gefunden wird. 

Bei der post-order Traversierung werden die Kindknoten vor den Eltern Knoten durchsucht.

Tiefensuche mit post-order Traversierung einer Baum Datenstruktur.
Tiefensuche mit post-order Traversierung einer Baum Datenstruktur.

Bei der in-order Traversierung werden die Elternknoten zwischen den Kindknoten durchsucht. Diese Methode wird hauptsächlich bei Binärbäumen genutzt.

Tiefensuche mit in-order Traversierung einer Baum Datenstruktur.
Tiefensuche mit in-order Traversierung einer Baum Datenstruktur.

Breitensuche

Das Gegenstück zur Tiefersuche ist die Breitensuche. Dieses Suchverfahren durchsucht die Baumstruktur Ebene für Ebene.

Breitensuche-Verfahren einer Baum Datenstruktur.
Breitensuche-Verfahren einer Baum Datenstruktur.

Breiten- und Tiefensuche im Vergleich

Beide Suchverfahren sind Spezialfälle der linearen Suche. Der Unterschied liegt in der Aufzählung der Elemente, wodurch unterschiedlich viel Speicherplatz verbraucht wird.

  • Speicher Verbrauch von dfs (Tiefensuche): O(n)
  • Speicher Verbrauch bfs (Breitensuche): O(n)

Der Speicherverbrauch beider Methoden sieht gleich aus, gilt aber für unterschiedliche “worst cases”.

Vollständige Bäume

Um eine bessere Aussage über die “use-cases” (Anwendungsfälle) der beiden Suchverfahren zu treffen, betrachten wir den vollständigen Baum. Ein Baum ist vollständig wenn folgende Kriterien erfüllt sind:

  1. Jeder Knoten bis zur Tiefe d- 1 hat genau b Kinder.
  2. Jeder Knoten der Tiefe d ist ein Blatt Knoten.

Bei einem vollständigen Baum schneidet die Tiefensuche deutlich besser ab, denn die maximale Tiefe d bestimmt hier den Speicher Verbrauch: O(d) statt O(b^d)

Ein vollständiger Baum mit der Tiefe d=3 und b=4 Kindknoten.
Ein vollständiger Baum mit der Tiefe d=3 und b=4 Kindknoten.

Iterative Suche

Die iterative Suche ist quasi eine Tiefensuche mit der Ausnahme, dass die Tiefe beschränkt wird.

Baum als Datentyp iterative Suche.
Baum als Datentyp iterative Suche.

Laufzeit: 0 (n) Speicher: 0 (d)

Die Laufzeit ist um einen Konstanten Faktor c <5 Schlechter als ber dfs oder bfs. Der Speicherverbrauch ist mit 0 (d) aber nicht besser. wo liegt nun der Vorteil der iterativen Suche?
Die Antwort ist iteratives Feedback, welche genutzt werden kann, um dem Benutzer beispielsweise Rückmeldung zu geben oder beim nächten iterativen Schritt den besten Pfad zu wählen.

Weitere Beiträge aus dieser Serie

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Notify me of followup comments via e-mail. You can also subscribe without commenting.