Der Baum als abstrakter Datentyp

In diesem Beitrag wird der Baum 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.

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
Tiefensuche mit pre-order Traversierung

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

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

Breitensuche

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

Breitensuche-Verfahren
Breitensuche-Verfahren

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.

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.

Kommentare

Eingehende Suchbegriffe zum Artikel:

Zusammenfassung
Der Baum als abstrakter Datentyp
Artikeltitel
Der Baum als abstrakter Datentyp
Beschreibung
In diesem Beitrag betrachten wir den Baum als abstrakten Datentyp.
Autor

Schreibe einen Kommentar

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

E-Mail-Benachrichtigung bei weiteren Kommentaren.
Auch möglich: Abo ohne Kommentar.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.

Pin It on Pinterest

Durch die weitere Nutzung der Seite stimmst du der Verwendung von Cookies zu. Weitere Informationen

Die Cookie-Einstellungen auf dieser Website sind auf "Cookies zulassen" eingestellt, um das beste Surferlebnis zu ermöglichen. Wenn du diese Website ohne Änderung der Cookie-Einstellungen verwendest oder auf "Akzeptieren" klickst, erklärst du sich damit einverstanden.

Schließen