Wozu braucht man Binärbäume?
Ich soll für den Informatik Unterricht eine Präsentation über Binärbäume halten. Als Einleitung würde ich gerne eine Folie über Anwendungsfälle machen und warum man Binärbäume eigentlich benötigt. Im Internet gibt es jedoch ausschließlich information darüber wie Binärbäume aufgebaut sind und wie sie funktionieren
5 Antworten
Meistens verwendet man Binärbäume als Searchtrees also als Datenstrukturen in denen das Suchen von Elementen schnell geht.
Der Binärbaum ist (sofern er ausbalanciert ist) so ziemlich eine der schnellsten Datenstrukturen bezogen auf Suchoperationen die es derzeit gibt (von denen die mir bekannt sind).
Daher kommen Binärbaume immer dann zum Einsatz wenn man in großen Datenmengen schnell irgenendwelche Werte finden will.
Kann ich einen ausreichend niedrigen Load-Faktor garantieren, dann sind Hashes deutlich schneller
Das ist richtig. Wollte ich ursprünglich auch dazu nehmen hab es aber dann weggelassen. Es ist hald immer die Frage ob man eine entsprechende Hashfunktion finden kann, die hier Sinnvoll ist. Was unter einbeziehung einer maximalen Speichergröße nicht immer funktionert.
Und wenn Du sagst, daß keine Ordnung auf dem Schlüsseluniversum existiert, dann fallen Bäume flach.
Was meinst du damit genau?
Du musst natürlich einen Schlüssel für die Einträge finden nachdem du suchst, bzw brauchst du an sich auch gar keinen Schlüssel wenn die Daten selbst als solcher geeignet sind.
Im wesentlichen reicht ja einfach eine größer kleiner Relation zwischen den Schlüsselwerten um den Baum zu erstellen.
Bäume brauchen eine Ordnungsrelation auf den Schlüsseln (Vergleichbarkeit).
Wie ich sagte, in der Praxis hast Du im Zweifelsfall immer einen Binärstring des Schlüssels und kannst notfalls darauf die Ordnung definieren. Bei theoretischen Betrachtungen ist das aber 'tabu', wenn keine Ordnung, dann eben kein Baum.
Das ist einfach ein Klassiker: Wörterbuchproblem ohne Ordnung auf dem Schlüsseluniversum - ob das praktisch realistisch ist, ist dabei zweitrangig... .
Binärbäume werden verwendet, um schneller nach Elementen in einer großen Sammlung zu suchen. Jede Node in einem Binärbaum hat einen repräsentativen Zahlenwert (oder ähnlichen Vergleichswert). Beim Suchen nach dem Element mit dem Wert n wird zuerst die Wurzel angeschaut. Hat diese den Wert n, so wurde das Element schon gefunden. Wenn nicht, so sucht die Software rechts weiter, wenn der gesuchte Wert größer ist, und links, wenn der Wert kleiner ist. Dadurch ist eine Suche nicht mehr
sondern
, was eine enorme potentielle Performance-Steigerung darstellt.
Du hast eine Sammlung von Objekten, ggf. sogar von unterschiedlicher Struktur/Typ. Objekte haben einen Schlüssel, wobei eine Ordnung auf den Schlüssel existiert. Dann kannst Du einen Binärbaum aufbauen, dessen Tiefe log_2(n) ist.
Für die Suche nach Elementen kannst Du nun gezielt im Baum absteigen, die Suche endet spätestens im Blatt, also nach O(log_2(n)) Schritten, im Gegensatz zur linearen Suche in der Menge O(n).
Ein sortiertes Array, auf dem Du eine Binärsuche durchführst ist nichts anderes als ein etwas versteckter Binärbaum, die Suche (Wahl des Folgeelementes) beschreibt einen Pfad im Baum.
Hast DU erstmal einen Baum, dann kannst Du auch in O(log_2(n)) Schritten Elemente einfügen, sofern Du den Baum pflegst und ausgewichtest.
------
Wir haben also hier die Anwendung als Suchbaum (AVL, rot-schwarz, splay) daneben gibt es z.B. in speziellen Fällen Spielbäume die Binärbäume sind und z.B. bei Alpha-Beta-Pruning Verwendung finden. Und dann wären da noch Binäre Codebäume wie z.B. im Entropiecoder.
Dann gibt es natürlich noch weitere Baumtypen, wenn mehr Kinder je Knoten zugelassen werden.
Binärbäume dienen dazu, Datenablage so zu organisieren, dass auch in riesig großen Mengen von Datensätzen (wie sie etwa in relationalen Datenbanken auftreten) der jeweils gewünschte Datensatz in kürzest möglicher Zeit — mit einem Minimum von CPU-Zyklen also — gefunden wird.
Da man in einem Binärbaum abgelegte Daten in einfacher Weise auch sortiert abrufen kann, lassen sich auf diese Weise Daten auch ganz besonders schnell und einfach sortieren.
Ein Binärbaum brauvhst du doch dazu das du am Schluss alle Binär zahlen einer Zahl hast die in Summe die Zahl ergeben. Und mit dem kannst du irgendetwas einfacher berechnen aber ich weiss nicht mehr was
Das ist nicht richtig - Binärbäume haben nichts mit Binärzahlen zu tun sondern werden verwendet, um die Suche nach Elemente in einer Datenstruktur großartig zu verschnellern
Kann ich einen ausreichend niedrigen Load-Faktor garantieren, dann sind Hashes deutlich schneller - Tradeoff ist möglicherweise ein entsprechend hoher Speicherverbrauch.
Und wenn Du sagst, daß keine Ordnung auf dem Schlüsseluniversum existiert, dann fallen Bäume flach. (In der Praxis muß ich natürlich die Schlüssel irgendwie kodieren und erhalte somit eine mehr oder minder sinnvolle Ordnung und sei es die der Binärstrings)