Was sind die Anwendungen von Binärbäumen?

Question

Ich frage mich, was die besonderen Anwendungen von Binärbäumen sind. Könnten Sie einige konkrete Beispiele nennen?

Answer 1

In C++ STL und vielen anderen Standardbibliotheken in anderen Sprachen, wie Java und C#. Binäre Suchbäume werden zur Implementierung von Set und Map verwendet.

Answer 2

Eine der wichtigsten Anwendungen von Binärbäumen sind ausgeglichen binäre Suchbäume wie:

• Rot-schwarze Bäume
• AVL-Bäume
• Sündenbock-Bäume

Diese Art von Bäumen hat die Eigenschaft, dass der Höhenunterschied zwischen dem linken und dem rechten Teilbaum klein gehalten wird, indem jedes Mal, wenn ein Knoten eingefügt oder gelöscht wird, Operationen wie Rotationen durchgeführt werden.

Dadurch bleibt die Gesamthöhe des Baums in der Größenordnung von log n und die Operationen wie Suche, Einfügen und Löschen von Knoten werden in O(log n)-Zeit durchgeführt. Die STL von C++ implementiert diese Bäume auch in Form von Mengen und Karten.

Answer 3

Sie können als schnelle Möglichkeit zum Sortieren von Daten verwendet werden. Einfügen von Daten in einen binären Suchbaum mit O(log(n)). Dann durchlaufen Sie den Baum, um sie zu sortieren.

Answer 4

Implementierungen von java.util.Set

Answer 5

Auf moderner Hardware ist ein Binärbaum aufgrund des schlechten Cache- und Platzverhaltens fast immer suboptimal. Dies gilt auch für die (halbwegs) ausgewogenen Varianten. Wenn man sie findet, dann dort, wo die Leistung nicht zählt (oder von der Vergleichsfunktion dominiert wird), oder, was wahrscheinlicher ist, aus historischen Gründen oder aus Unwissenheit.