Was sind die Anwendungen von Binärbäumen?

323

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

Jichao
quelle

Antworten:

425

Über die Leistung von Binärbäumen zu streiten ist bedeutungslos - es handelt sich nicht um eine Datenstruktur, sondern um eine Familie von Datenstrukturen, die alle unterschiedliche Leistungsmerkmale aufweisen. Während es stimmt, dass unausgeglichene Binärbäume bei der Suche viel schlechter abschneiden als selbstausgleichende Binärbäume , gibt es viele Binärbäume (wie z. B. Binärversuche), für die "Ausgleich" keine Bedeutung hat.

Anwendungen von Binärbäumen

  • Binärer Suchbaum - Wird in vielen Suchanwendungen verwendet, in denen ständig Daten eingegeben / verlassen werden, z. B. mapund setObjekte in den Bibliotheken vieler Sprachen.
  • Binary Space Partition - Wird in fast jedem 3D-Videospiel verwendet, um zu bestimmen, welche Objekte gerendert werden müssen.
  • Binäre Versuche - Wird in fast jedem Router mit hoher Bandbreite zum Speichern von Routertabellen verwendet.
  • Hash-Bäume - werden in P2P-Programmen und speziellen Bildsignaturen verwendet, bei denen ein Hash überprüft werden muss, aber nicht die gesamte Datei verfügbar ist.
  • Heaps - Wird zur Implementierung effizienter Prioritätswarteschlangen verwendet, die wiederum zum Planen von Prozessen in vielen Betriebssystemen, zur Dienstgüte in Routern und zu A * (Pfadfindungsalgorithmus für KI-Anwendungen, einschließlich Robotik und Videospiele) verwendet werden. . Wird auch bei der Heap-Sortierung verwendet.
  • Huffman Coding Tree ( Chip Uni ) - wird in Komprimierungsalgorithmen verwendet, z. B. in den Dateiformaten .jpeg und .mp3.
  • GGM-Bäume - Wird in kryptografischen Anwendungen verwendet, um einen Baum von Pseudozufallszahlen zu generieren.
  • Syntaxbaum - Wird von Compilern und (implizit) Taschenrechnern erstellt, um Ausdrücke zu analysieren.
  • Treap - Randomisierte Datenstruktur für drahtlose Netzwerke und Speicherzuweisung.
  • T-Baum - Obwohl die meisten Datenbanken eine Art B-Baum zum Speichern von Daten auf dem Laufwerk verwenden, verwenden Datenbanken, die alle (die meisten) Daten im Speicher behalten, häufig T-Bäume, um dies zu tun.

Der Grund dafür, dass Binärbäume häufiger als n-ary-Bäume für die Suche verwendet werden, ist, dass n-ary-Bäume komplexer sind, aber normalerweise keinen wirklichen Geschwindigkeitsvorteil bieten.

In einem (ausgeglichenen) Binärbaum mit mKnoten erfordert der Übergang von einer Ebene zur nächsten einen Vergleich, und es gibt log_2(m)Ebenen für insgesamtlog_2(m) Vergleiche.

Im Gegensatz dazu erfordert ein n-ary-Baum log_2(n)Vergleiche (unter Verwendung einer binären Suche) , um zur nächsten Ebene zu gelangen. Da es log_n(m)Gesamtstufen gibt, erfordert die Suche log_2(n)*log_n(m)= log_2(m)Vergleiche insgesamt. Obwohl n-ary Bäume komplexer sind, bieten sie keinen Vorteil in Bezug auf die insgesamt erforderlichen Vergleiche.

(N-ary-Bäume sind jedoch in Nischensituationen immer noch nützlich. Die Beispiele, die sofort in den Sinn kommen, sind Quad-Bäume und andere raumteilende Bäume, bei denen die Aufteilung des Raums mit nur zwei Knoten pro Ebene die Logik unnötig komplex machen würde B-Bäume, die in vielen Datenbanken verwendet werden, wobei der begrenzende Faktor nicht darin besteht, wie viele Vergleiche auf jeder Ebene durchgeführt werden, sondern wie viele Knoten gleichzeitig von der Festplatte geladen werden können.

BlueRaja - Danny Pflughoeft
quelle
3
> Treap - Randomisierte Datenstruktur für drahtlose Netzwerke und Speicherzuweisung. Wie genau werden sie bei der Speicherzuweisung und beim drahtlosen Netzwerk verwendet?
9.
1
Es gibt viele nützliche Datenstrukturen und Algorithmen, die das Wort "binär" verwenden, und "binärer Suchbaum" ist tatsächlich eine davon, aber das ist nicht die Frage, die gestellt wurde. Welchen Nutzen hat ein einfacher alter "Binärbaum", kein sortierter, kein ausgeglichener, kein vollständiger. Nur ein einfacher alter zufälliger Baum?
Michael Erickson
4
@ MichaelErickson Hast du die Antwort gelesen? Denn genau das habe ich beantwortet.
BlueRaja - Danny Pflughoeft
1
Ich glaube, Hash-Bäume werden allgemein Merkle-Bäume genannt, zumindest innerhalb der Bitcoin- und Ethereum-Gemeinschaften, IPFS usw.
Duke
1
Schade, dass diese Antwort so viele Fehler enthält. n-ary-Bäume auf moderner Hardware sind binären Bäumen fast immer vorzuziehen. Die genannten Anwendungen verwenden meist keine Binärbäume.
Stephan Eggermont
289

Wenn die meisten Leute über binäre Bäume sprechen, denken sie meistens nicht an binäre Suche Bäume, so dass ich das erste decken werde.

Ein nicht ausgeglichener binärer Suchbaum ist eigentlich nur für die Aufklärung der Schüler über Datenstrukturen nützlich. Dies liegt daran, dass der Baum, wenn die Daten nicht in einer relativ zufälligen Reihenfolge eingehen, leicht in seine Worst-Case-Form ausarten kann, bei der es sich um eine verknüpfte Liste handelt, da dies bei einfachen Binärbäumen nicht der Fall ist ausgeglichen sind.

Ein gutes Beispiel: Ich musste einmal eine Software reparieren, die ihre Daten zur Manipulation und Suche in einen Binärbaum lud. Es schrieb die Daten in sortierter Form aus:

Alice
Bob
Chloe
David
Edwina
Frank

so dass beim erneuten Einlesen der folgende Baum angezeigt wurde:

  Alice
 /     \
=       Bob
       /   \
      =     Chloe
           /     \
          =       David
                 /     \
                =       Edwina
                       /      \
                      =        Frank
                              /     \
                             =       =

Welches ist die entartete Form. Wenn Sie in diesem Baum nach Frank suchen, müssen Sie alle sechs Knoten durchsuchen, bevor Sie ihn finden.

Binäre Bäume werden für die Suche wirklich nützlich, wenn Sie sie ausbalancieren. Dies beinhaltet das Drehen von Teilbäumen durch ihren Wurzelknoten, so dass der Höhenunterschied zwischen zwei beliebigen Teilbäumen kleiner oder gleich 1 ist. Wenn Sie diese Namen nacheinander zu einem ausgeglichenen Baum hinzufügen, erhalten Sie die folgende Reihenfolge:

1.   Alice
    /     \
   =       =

 

2.   Alice
    /     \
   =       Bob
          /   \
         =     =

 

3.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       =

 

4.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       David
                    /     \
                   =       =

 

5.           Bob
        ____/   \____
   Alice             David
  /     \           /     \
 =       =     Chloe       Edwina
              /     \     /      \
             =       =   =        =

 

6.              Chloe
            ___/     \___
         Bob             Edwina
        /   \           /      \
   Alice     =      David        Frank
  /     \          /     \      /     \
 =       =        =       =    =       =

Sie können tatsächlich ganze Teilbäume sehen, die sich nach links drehen (in den Schritten 3 und 6), wenn die Einträge hinzugefügt werden, und dies gibt Ihnen einen ausgeglichenen Binärbaum, in dem die Suche im ungünstigsten Fall O(log N)eher als die O(Nder entarteten Form erfolgt. Zu keinem Zeitpunkt unterscheidet sich das höchste NULL ( =) vom niedrigsten um mehr als eine Ebene. Und vor in dem letzten Baum, können Sie Frank finden nur bei drei Knoten suchen ( Chloe, Edwinaund schließlichFrank ).

Natürlich können sie noch nützlicher werden, wenn Sie sie in mehrere Richtungen ausbalancieren anstatt zu binären Locken machen. Das bedeutet, dass jeder Knoten mehr als ein Element enthält (technisch gesehen enthalten sie N Elemente und N + 1 Zeiger, wobei ein Binärbaum ein Sonderfall eines Einweg-Mehrwegbaums mit 1 Element und 2 Zeigern ist).

Mit einem Drei-Wege-Baum erhalten Sie:

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

Dies wird normalerweise zum Verwalten von Schlüsseln für einen Index von Elementen verwendet. Ich habe eine für die Hardware optimierte Datenbanksoftware geschrieben, bei der ein Knoten genau die Größe eines Plattenblocks hat (z. B. 512 Byte) und Sie so viele Schlüssel wie möglich in einen einzelnen Knoten stecken. Die Zeiger in diesem Fall waren tatsächlich Datensatznummern in einer Direktzugriffsdatei mit fester Länge, die von der Indexdatei getrennt ist (sodass die Datensatznummer durch Xeinfaches Suchen gefunden werden konnte X * record_length).

Wenn die Zeiger beispielsweise 4 Byte groß sind und die Schlüsselgröße 10 beträgt, beträgt die Anzahl der Schlüssel in einem 512-Byte-Knoten 36. Das sind 36 Schlüssel (360 Byte) und 37 Zeiger (148 Byte) für insgesamt 508 Byte mit Pro Knoten werden 4 Bytes verschwendet.

Die Verwendung von Mehrwegeschlüsseln führt zu der Komplexität einer zweiphasigen Suche (Mehrwegesuche zum Finden des richtigen Knotens kombiniert mit einer kleinen sequentiellen (oder linearen binären) Suche zum Finden des richtigen Schlüssels im Knoten), aber zum Vorteil von Wenn Sie weniger Festplatten-E / A ausführen, wird dies mehr als wettgemacht.

Ich sehe keinen Grund, dies für eine In-Memory-Struktur zu tun. Sie sollten sich besser an einen ausgeglichenen Binärbaum halten und Ihren Code einfach halten.

Denken Sie auch daran, dass die Vorteile von O(log N)überO(N) nicht wirklich auftreten, wenn Ihre Datenmengen klein sind. Wenn Sie einen Mehrwegbaum verwenden, um die fünfzehn Personen in Ihrem Adressbuch zu speichern, ist dies wahrscheinlich übertrieben. Die Vorteile ergeben sich, wenn Sie so etwas wie jede Bestellung Ihrer hunderttausend Kunden in den letzten zehn Jahren speichern.

Der springende Punkt der Big-O-Notation ist es, anzuzeigen, was passiert, wenn sich die NUnendlichkeit nähert. Einige Leute mögen anderer Meinung sein, aber es ist sogar in Ordnung, die Blasensortierung zu verwenden, wenn Sie sicher sind, dass die Datensätze unter einer bestimmten Größe bleiben, solange nichts anderes verfügbar ist :-)


In Bezug auf andere Verwendungszwecke für Binärbäume gibt es sehr viele, wie zum Beispiel:

  • Binäre Haufen, bei denen höhere Tasten über oder gleich niedrigeren und nicht links von (oder unter oder gleich und rechts) liegen;
  • Hash-Bäume, ähnlich wie Hash-Tabellen;
  • Abstrakte Syntaxbäume zur Kompilierung von Computersprachen;
  • Huffman-Bäume zur Komprimierung von Daten;
  • Routing-Bäume für den Netzwerkverkehr.

Angesichts der vielen Erklärungen, die ich für die Suchbäume generiert habe, bin ich zurückhaltend, auf die anderen näher einzugehen, aber das sollte ausreichen, um sie zu untersuchen, falls Sie dies wünschen.

paxdiablo
quelle
28
+1 Für eine solche haben wir eine Antwort geschrieben; Außerdem mache ich mich mit ausgewogenen Mehrwegbäumen bekannt, auf die ich noch nie gestoßen bin.
Tony
3
Ich bin mit Ihrer Behauptung nicht einverstanden, dass sie nur für die Ausbildung von Studenten nützlich sind. Sie sind auch als einfache statische Datenstruktur sehr nützlich. Dies ist jedoch eine sehr gut geschriebene und illustrierte Antwort, also +1 für alle anderen. :-)
Benson
1
Bei moderner Hardware sollten fast alle Bäume mehrwegig sein.
Stephan Eggermont
89

Die Organisation des Morsecodes ist ein Binärbaum.

Binärbaum

Morse-Code

IliasT
quelle
4
Das ist meine Lieblingsantwort. Veranschaulicht direkt die Verringerung der Rechenkomplexität, die erforderlich ist, um Zeichen weiter entlang der Liste zu erreichen.
Schnurrbart
7
Ich habe diese Antwort wirklich genossen!
Duncan Edwards
2
Ich habe für eine Firma gearbeitet, die Filter für
JosephDoggie
62

Ein Binärbaum ist eine Baumdatenstruktur, in der jeder Knoten höchstens zwei untergeordnete Knoten hat, die normalerweise als "links" und "rechts" unterschieden werden. Knoten mit untergeordneten Knoten sind übergeordnete Knoten, und untergeordnete Knoten können Verweise auf ihre übergeordneten Knoten enthalten. Außerhalb des Baums wird häufig auf den "Wurzel" -Knoten (den Vorfahren aller Knoten) verwiesen, sofern dieser vorhanden ist. Jeder Knoten in der Datenstruktur kann erreicht werden, indem am Stammknoten begonnen wird und wiederholt Verweisen auf das linke oder rechte untergeordnete Element gefolgt wird. In einem Binärbaum beträgt der Grad jedes Knotens maximal zwei.

Binärer Baum

Binäre Bäume sind nützlich, denn wie Sie auf dem Bild sehen können, müssen Sie, wenn Sie einen Knoten im Baum finden möchten, nur maximal sechs Mal suchen. Wenn Sie beispielsweise nach Knoten 24 suchen möchten, beginnen Sie an der Wurzel.

  • Die Wurzel hat einen Wert von 31, der größer als 24 ist. Sie gehen also zum linken Knoten.
  • Der linke Knoten hat einen Wert von 15, was weniger als 24 ist. Sie gehen also zum rechten Knoten.
  • Der rechte Knoten hat einen Wert von 23, was weniger als 24 ist. Sie gehen also zum rechten Knoten.
  • Der rechte Knoten hat einen Wert von 27, der größer als 24 ist. Sie gehen also zum linken Knoten.
  • Der linke Knoten hat einen Wert von 25, der größer als 24 ist. Sie gehen also zum linken Knoten.
  • Der Knoten hat den Wert 24, der Schlüssel, nach dem wir suchen.

Diese Suche ist unten dargestellt: Baumsuche

Sie können sehen, dass Sie beim ersten Durchgang die Hälfte der Knoten des gesamten Baums ausschließen können. und die Hälfte des linken Teilbaums auf der zweiten. Dies ermöglicht eine sehr effektive Suche. Wenn dies mit 4 Milliarden Elementen geschehen wäre, müssten Sie nur maximal 32 Mal suchen. Je mehr Elemente im Baum enthalten sind, desto effizienter kann Ihre Suche sein.

Löschungen können komplex werden. Wenn der Knoten 0 oder 1 untergeordnetes Element hat, müssen lediglich einige Zeiger verschoben werden, um den zu löschenden auszuschließen. Sie können jedoch einen Knoten mit 2 untergeordneten Knoten nicht einfach löschen. Also machen wir eine Abkürzung. Angenommen, wir wollten Knoten 19 löschen.

Löschen 1

Da es nicht einfach ist zu bestimmen, wohin der linke und der rechte Zeiger verschoben werden sollen, finden wir einen, durch den wir ihn ersetzen können. Wir gehen zum linken Unterbaum und gehen so weit rechts wie möglich. Dies gibt uns den nächstgrößeren Wert des Knotens, den wir löschen möchten.

Löschen 3

Jetzt kopieren wir den gesamten Inhalt von 18 mit Ausnahme des linken und rechten Zeigers und löschen den ursprünglichen 18-Knoten.

Löschen 4


Um diese Bilder zu erstellen, habe ich einen AVL-Baum implementiert, einen selbstausgleichenden Baum, sodass der Baum zu jedem Zeitpunkt höchstens eine Differenzstufe zwischen den Blattknoten (Knoten ohne Kinder) aufweist. Dies verhindert, dass der Baum verzerrt wird, und behält die maximale O(log n)Suchzeit bei, wobei die Kosten für das Einfügen und Löschen etwas länger sind.

Hier ist ein Beispiel, das zeigt, wie sich mein AVL-Baum so kompakt und ausgewogen wie möglich gehalten hat.

Geben Sie hier die Bildbeschreibung ein

In einem sortierten Array würden Suchvorgänge O(log(n))wie bei einem Baum weiterhin ausgeführt, beim zufälligen Einfügen und Entfernen jedoch O (n) anstelle des Baums O(log(n)). Einige STL-Container nutzen diese Leistungsmerkmale zu ihrem Vorteil, sodass das Einsetzen und Entfernen maximal dauert O(log n), was sehr schnell ist. Einige dieser Behälter sind map, multimap, set, und multiset.

Beispielcode für einen AVL-Baum finden Sie unter http://ideone.com/MheW8

Drise
quelle
5
Sie müssen nur nach O (log n) suchen, wenn Sie es mit einem binären Suchbaum zu tun haben (der selbst gut ausbalanciert ist). Beliebige binäre Bäume haben keine Ordnungsbeschränkungen, und eine zufällige BST hat die Suchkomplexität O (log h ).
dlev
Diese sind nicht in den entsprechenden Standardbehältern gelagert.
Welpe
12

Die Hauptanwendung sind binäre Suchbäume . Hierbei handelt es sich um eine Datenstruktur, in der das Suchen, Einfügen und Entfernen sehr schnell erfolgt (Informationen zu log(n)Vorgängen).

BlueRaja - Danny Pflughoeft
quelle
1
Binäre Suchbäume sind keine Anwendung, sondern eine bestimmte Art von Binärbäumen.
nbro
@nbro: Sie argumentieren sinnlose Semantik, das sind beide gültige Arten, dasselbe zu sagen. Beachten Sie, dass "Anwendung" hier nicht dasselbe bedeutet wie "Computeranwendung"
BlueRaja - Danny Pflughoeft
Ich denke, dass sich die Frage eher auf reale Anwendungen und nicht auf bestimmte Implementierungen oder bestimmte Arten von Binärbäumen bezog. Übrigens fragt der Fragesteller nicht, welche Datenstrukturen bestimmte Binärbäume sind. Es ist nicht sinnlos, IMO. Aber ich stimme zu, dass es sowieso nicht eindeutig ist. In Ihrer anderen Antwort erwähnen Sie beispielsweise Syntaxbäume, bei denen es sich um eine Anwendung der Baumdatenstruktur (jedoch nicht unbedingt binär ) in einer realen Anwendung handelt. Aufgrund Ihrer Überlegungen könnte ich dann alle mir bekannten Binärbäume aufzählen. Wir alle würden uns über die Menge der Elemente freuen.
nbro
11
Chip Uni
quelle
11

Ein interessantes Beispiel für einen nicht erwähnten Binärbaum ist der eines rekursiv ausgewerteten mathematischen Ausdrucks. Vom praktischen Standpunkt aus ist es im Grunde genommen nutzlos, aber es ist eine interessante Art, sich solche Ausdrücke vorzustellen.

Grundsätzlich hat jeder Knoten des Baums einen Wert, der entweder sich selbst inhärent ist oder durch rekursives Auswerten der Werte seiner untergeordneten Knoten ausgewertet wird.

Zum Beispiel kann der Ausdruck (1+3)*2ausgedrückt werden als:

    *
   / \
  +   2
 / \
1   3

Um den Ausdruck zu bewerten, fragen wir nach dem Wert des Elternteils. Dieser Knoten erhält seine Werte wiederum von seinen untergeordneten Knoten, einem Plus-Operator und einem Knoten, der einfach '2' enthält. Der Plus-Operator erhält seine Werte wiederum von untergeordneten Elementen mit den Werten '1' und '3' und addiert sie, wobei 4 an den Multiplikationsknoten zurückgegeben wird, der 8 zurückgibt.

Diese Verwendung eines Binärbaums ähnelt in gewissem Sinne der umgekehrten Poliernotation, da die Reihenfolge, in der Operationen ausgeführt werden, identisch ist. Zu beachten ist auch, dass es sich nicht unbedingt um einen Binärbaum handeln muss, sondern nur darum, dass die am häufigsten verwendeten Operatoren binär sind. Im Grunde ist der Binärbaum hier nur eine sehr einfache, rein funktionale Programmiersprache.

Ahnungslos
quelle
9

Ich glaube nicht, dass es eine Verwendung für "reine" Binärbäume gibt. (außer zu Bildungszwecken) Ausgewogene Binärbäume wie Rot-Schwarz-Bäume oder AVL-Bäume sind viel nützlicher, da sie O (logn) -Operationen garantieren. Normale Binärbäume können eine Liste (oder fast eine Liste) sein und sind in Anwendungen, die viele Daten verwenden, nicht wirklich nützlich.

Ausgeglichene Bäume werden häufig zum Implementieren von Karten oder Sets verwendet. Sie können auch zum Sortieren in O (nlogn) verwendet werden, obwohl es bessere Möglichkeiten gibt, dies zu tun.

Auch zum Suchen / Einfügen / Löschen können Hash-Tabellen verwendet werden, die normalerweise eine bessere Leistung aufweisen als binäre Suchbäume (ausgeglichen oder nicht).

Eine Anwendung, bei der (ausgeglichene) binäre Suchbäume nützlich wären, wäre, wenn gesucht / eingefügt / gelöscht und sortiert werden müsste. Die Sortierung kann vorhanden sein (fast ohne Berücksichtigung des für die Rekursion erforderlichen Stapelspeichers), wenn ein Baum mit einem ausgeglichenen Build erstellt wird. Es wäre immer noch O (nlogn), aber mit einem kleineren konstanten Faktor und ohne zusätzlichen Platzbedarf (mit Ausnahme des neuen Arrays, vorausgesetzt, die Daten müssen in ein Array gestellt werden). Hash-Tabellen hingegen können nicht sortiert werden (zumindest nicht direkt).

Vielleicht sind sie auch in einigen ausgeklügelten Algorithmen nützlich, um etwas zu tun, aber mir fällt nichts ein. Wenn ich mehr finde, werde ich meinen Beitrag bearbeiten.

Andere Bäume wie zB B + -Bäume werden häufig in Datenbanken verwendet

George
quelle
9

Eine der häufigsten Anwendungen ist das effiziente Speichern von Daten in sortierter Form, um schnell auf gespeicherte Elemente zugreifen und diese durchsuchen zu können. Zum Beispiel std::mapoder std::setin der C ++ Standard Library.

Der Binärbaum als Datenstruktur ist nützlich für verschiedene Implementierungen von Ausdrucksparsern und Ausdruckslösern.

Es kann auch verwendet werden, um einige Datenbankprobleme zu lösen, z. B. die Indizierung.

Im Allgemeinen ist der Binärbaum ein allgemeines Konzept einer bestimmten baumbasierten Datenstruktur, und verschiedene spezifische Arten von Binärbäumen können mit unterschiedlichen Eigenschaften erstellt werden.

Mloskot
quelle
7

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

Yin Zhu
quelle
2
Tatsächlich basieren Sets / Maps in C ++ am häufigsten auf rot-schwarzen Bäumen, bei denen es sich um einen binären Suchbaum mit einigen weiteren Einschränkungen handelt.
Idan K
6

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

Diese Baumarten haben die Eigenschaft, dass der Höhenunterschied zwischen linkem und rechtem Teilbaum gering gehalten wird, indem bei jedem Einfügen oder Löschen eines Knotens Operationen wie Rotationen ausgeführt werden.

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

Rohit
quelle
5

Sie können als schnelle Methode zum Sortieren von Daten verwendet werden. Fügen Sie bei O (log (n)) Daten in einen binären Suchbaum ein. Überqueren Sie dann den Baum, um sie zu sortieren.

Aaron
quelle
2

Die Syntax Ihres Programms oder viele andere Dinge wie natürliche Sprachen können mithilfe eines Binärbaums analysiert werden (allerdings nicht unbedingt).

Anycorn
quelle
2

Implementierungen von java.util.Set

römisch
quelle
2

Auf moderner Hardware ist ein Binärbaum aufgrund eines schlechten Cache- und Speicherverhaltens fast immer suboptimal. Dies gilt auch für die (halb) ausgeglichenen Varianten. Wenn Sie sie finden, zählt die Leistung nicht (oder wird von der Vergleichsfunktion dominiert) oder eher aus historischen Gründen oder aus Gründen der Unwissenheit.

Stephan Eggermont
quelle
2
Suboptimal im Vergleich zu was?
Mehrwegbäume. Die lineare Suche durch alle Daten, die Sie von einem Speicherzugriff erhalten, ist viel schneller als ein neuer Hauptspeicherzugriff
Stephan Eggermont
0

Ein Compiler, der einen Binärbaum für die Darstellung eines AST verwendet, kann bekannte Algorithmen zum Parsen des Baums wie Postorder, Inorder verwenden. Der Programmierer muss keinen eigenen Algorithmus entwickeln. Da ein Binärbaum für eine Quelldatei höher ist als der n-ary-Baum, dauert das Erstellen länger. Nehmen Sie diese Produktion: selstmnt: = "if" "(" expr ")" stmnt "ELSE" stmnt In einem Binärbaum hat es 3 Ebenen von Knoten, aber der n-ary Baum hat 1 Ebene (von Chids)

Aus diesem Grund sind Unix-basierte Betriebssysteme langsam.

Evenhorizon
quelle