Frage von thundercake, 23

Binärbaum Erklärung?

Ahoi!

Kann mir jemand Binärbäume erklären? (Funktionsweise, Nutzen, Aufbau etc.)

Thx Thundercake c:

Antwort
von sarahj, 10

Aufbau wird in der anderen Antwort erklärt.

Nochmal kurz zusammenfassend:
jeder Knoten hat Referenzen auf bis zu 2 Kindknoten.
Die Knoten, die keine Kinder mehr haben nennt man Blätter.
Die "Kinder" sind also ihrerseits Unterbäume oder Blätter.

Es gibt balancierte und unbalancierte Binärbäume (unausgeglichen / ausgeglichen).
Im allgemeinen will man balancierte; d.h. die beiden Unterbäume haben möglichst gleich viele Blätter. Warum werden wir gleich sehen.

Außerdem gibt es im Baum üblicherweise eine Ordnung.
Zum Beispiel alle kleineren Elemente im linken, alle größeren im rechten Unterbaum.

Nutzen:
Bäume eignen sich hervorragend zum Suchen von Daten.
(ich nehme im folgenden mal Personennamen, als konkretes Beispiel)

Nehmen wir mal zum Vergleich eine einfache Liste.
Will man Informationen zu einer Person suchen, mss man die Liste von vorne bis hinten durchsuchen. Nehmen wir mal an, die Liste hat die Länge n. Das heißt, rein statistisch findet man die gesuchte Person (falls in der Liste) nach (n / 2) Vergleichen. Um sicher zu stellen, daß die Person nicht in der Liste ist, muß man alle n Elemente vergleichen.
Ist die Liste doppelt so lange, muß man also auch doppelt so viele vergleiche machen. 4 mal solange, 4 mal so viele Vergleiche usw.
Man sagt, der Algorithmus hat eine Laufzeit von O(n). D.h. sie hängt linear von n ab.

Nun zum Baum:
Nehmen wir an, du hast den Baum so organisiert, daß er ausgeglichen ist, und der oberste Knoten die Namen quasi in 2 Hälften teilt. Alle kleineren Namen sind im linken, alle größeren im rechten Unterbaum.

Wenn Du jetzt einen Namen suchst, und mit dem obersten Knoten vergleichst, kannst Du gleich sagen in welche Richtung Du weiter suchen musst. Du kannst also gleich die Hälfte ausschließen, und must sie gar nicht erst durchsuchen. Folgst also entweder entlang dem rechten oder linken Teilbaum. Mit jedem Vergleich wird also wieder die Hälfte der verbleibenden ausgeschlossen. D.h. (1/2), (1/4), (1/8) usw.

Ein Baum der Tiefe t kann also n = 2^t Elemente halten. Umgekehrt brauchst Du also nur ld(n) Vergleiche zum suchen (ld = 2er Logarithmus). Der Algorithmus hat eine Laufzeit von O(ld n)

Das ist doch was oder:
bei 1000 Elementen brauchst Du nur noch ld(1000) = 10 Vergleiche.

Das tolle ist, daß der logarithmus viel viel langsamer steigt.
Bei 100000 Elementen brauchst Du also nicht 100 mal so lange, sondern nur ld(100000) = 17 Vergleiche.

Der Nutzen ist doch wohl jetzt klar?

Antwort
von Denno2015, 23

Versuch es mal hiermit:

http://www.inf-schule.de/algorithmen/suchbaeume/binaerbaum/struktur

Kommentar von thundercake ,

Dankeschön! :)

Keine passende Antwort gefunden?

Fragen Sie die Community