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

Sich über die Leistung von Binär-Bäume ist bedeutungslos - es handelt sich nicht um eine Datenstruktur, sondern um eine Familie von Datenstrukturen, die alle unterschiedliche Leistungsmerkmale haben. Es ist zwar richtig, dass unausgeglichene binäre Bäume viel schlechter abschneiden als selbstbalancierende binäre Bäume für die Suche gibt es viele binäre Bäume (wie z.B. binäre Versuche) bei denen "ausgleichend" hat keine Bedeutung.

Anwendungen von Binärbäumen

• Binärer Suchbaum - Verwendet in viele Suchanwendungen, bei denen ständig Daten ein- und ausgehen, wie z. B. die map y set Objekte in den Bibliotheken vieler Sprachen.
• Binäre Raumaufteilung - 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 zur Speicherung von Router-Tabellen verwendet.
• Hash-Bäume - Wird in Torrents und speziellen Bildsignaturen verwendet, bei denen ein Hash verifiziert werden muss, aber die gesamte Datei nicht verfügbar ist. Wird auch in Blockchains verwendet, z. B. bei Bitcoin.
• Haufen - Einsatz bei der Implementierung effizienter Prioritätswarteschlangen, die wiederum für die Planung von Prozessen in vielen Betriebssystemen, Quality-of-Service in Routern und A* verwendet werden (Pfadfindungsalgorithmus, der in KI-Anwendungen, einschließlich Robotik und Videospielen, verwendet wird) . Wird auch bei Heap-Sortierung verwendet.
• Huffman-Kodierungsbaum ( Chip Uni ) - Wird in Kompressionsalgorithmen verwendet, wie z. B. bei den Dateiformaten .jpeg und .mp3.
• GGM-Bäume - Wird in kryptografischen Anwendungen verwendet, um einen Baum von Pseudo-Zufallszahlen zu erzeugen.
• Syntax-Baum - Wird von Compilern und (implizit) Taschenrechnern konstruiert, um Ausdrücke zu parsen.
• Treap - Zufallsgesteuerte Datenstruktur, die in drahtlosen Netzwerken und bei der Speicherzuweisung verwendet wird.
• T-Baum - Obwohl die meisten Datenbanken irgendeine Form von B-Bäumen verwenden, um Daten auf dem Laufwerk zu speichern, verwenden Datenbanken, die alle (die meisten) ihre Daten im Speicher halten, oft T-Bäume.

---

Der Grund dafür, dass binäre Bäume häufiger für die Suche verwendet werden als n-äre Bäume, liegt darin, dass n-äre Bäume komplexer sind, aber normalerweise keinen wirklichen Geschwindigkeitsvorteil bieten.

In einem (ausgewogenen) Binärbaum mit m Knoten, der Wechsel von einer Ebene zur nächsten erfordert einen Vergleich, und es gibt log_2(m) Ebenen, also insgesamt log_2(m) Vergleiche.

Im Gegensatz dazu erfordert ein n-ärer Baum log_2(n) Vergleiche (unter Verwendung einer binären Suche) um die nächste Stufe zu erreichen. Da gibt es log_n(m) Gesamtwerte, wird die Suche erfordern log_2(n)*log_n(m) = log_2(m) Vergleiche insgesamt. Obwohl n-äre Bäume also komplexer sind, bieten sie keinen Vorteil in Bezug auf die insgesamt erforderlichen Vergleiche.

(Allerdings sind n-äre Bäume in Nischensituationen immer noch nützlich. Die Beispiele, die mir sofort einfallen, sind Quad-Bäume und andere Raumaufteilungsbäume, bei denen die Aufteilung des Raums mit nur zwei Knoten pro Ebene die Logik unnötig komplex machen würde; und B-Bäume wird in vielen Datenbanken verwendet, wo 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)

Answer 2

Wenn die meisten Leute über binäre Bäume sprechen, denken sie meistens an binäre Suche Bäume, also werde ich das zuerst behandeln.

Ein nicht-balancierter binärer Suchbaum ist eigentlich nur nützlich, um Schülern etwas über Datenstrukturen beizubringen. Das liegt daran, dass der Baum, sofern die Daten nicht in einer relativ zufälligen Reihenfolge eingehen, leicht zu seiner schlimmsten Form degenerieren kann, nämlich zu einer verknüpften Liste, da einfache binäre Bäume no ausgeglichen.

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

Alice
Bob
Chloe
David
Edwina
Frank

so dass sich beim erneuten Einlesen der folgende Baum ergab:

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

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

Binäre Bäume werden erst dann wirklich nützlich für die Suche, wenn man sie ausbalanciert. Dabei werden die Teilbäume durch ihren Wurzelknoten so gedreht, dass der Höhenunterschied zwischen zwei beliebigen Teilbäumen kleiner oder gleich 1 ist. Wenn Sie die oben genannten Namen nacheinander in einen ausgeglichenen Baum einfügen, ergibt sich 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 sehen, wie sich ganze Teilbäume nach links drehen (in den Schritten 3 und 6), wenn die Einträge hinzugefügt werden. Dies ergibt einen ausgeglichenen Binärbaum, bei dem die Suche im schlimmsten Fall O(log N) und nicht die O(N ), die die entartete Form ergibt. Zu keinem Zeitpunkt ist die höchste NULL ( = ) um mehr als eine Stufe von der niedrigsten abweichen. Und in dem endgültigen Baum oben kann man Frank finden, indem man nur drei Knoten betrachtet ( Chloe , Edwina und schließlich, Frank ).

Natürlich können sie noch nützlicher werden, wenn man sie ausgewogen gestaltet Mehrweg Bäume und nicht binäre Bäume. 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 Spezialfall eines 1-Wege-Mehrwegbaums mit 1 Element und 2 Zeigern ist).

Bei einem Drei-Wege-Baum ergibt sich folgendes Bild:

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

Dies wird normalerweise bei der Pflege 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 Festplattenblocks hat (z. B. 512 Byte) und man so viele Schlüssel wie möglich in einen einzelnen Knoten packt. Die Zeiger waren in diesem Fall tatsächlich Datensatznummern in einer von der Indexdatei getrennten Direktzugriffsdatei mit Datensätzen fester Länge (also Datensatznummer X gefunden werden könnte, indem man einfach nach X * record_length ).

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

Die Verwendung von Mehrweg-Schlüsseln bringt die Komplexität einer zweistufigen Suche mit sich (Mehrweg-Suche, um den richtigen Knoten zu finden, kombiniert mit einer kleinen sequentiellen (oder linearen binären) Suche, um den richtigen Schlüssel im Knoten zu finden), aber der Vorteil, weniger Festplatten-E/A zu benötigen, macht dies mehr als wett.

Ich sehe keinen Grund, dies für eine In-Memory-Struktur zu tun, Sie wären besser dran, wenn Sie bei einem ausgeglichenen Binärbaum bleiben und Ihren Code einfach halten.

Denken Sie auch daran, dass die Vorteile der O(log N) en O(N) erscheinen nicht wirklich, wenn Ihre Datensätze klein sind. Wenn Sie einen mehrseitigen Baum verwenden, um die fünfzehn Personen in Ihrem Adressbuch zu speichern, ist das wahrscheinlich ein Overkill. Die Vorteile kommen zum Tragen, wenn Sie z. B. alle Bestellungen Ihrer hunderttausend Kunden aus den letzten zehn Jahren speichern wollen.

Der Sinn der Big-O-Notation besteht darin anzugeben, was passiert, wenn die N nähert sich der Unendlichkeit. Manche Leute sind vielleicht anderer Meinung, aber es ist sogar in Ordnung, Bubble Sort zu verwenden, wenn man sicher ist, dass die Datensätze unter einer bestimmten Größe bleiben, solange nichts anderes zur Verfügung steht :-)

---

Es gibt noch viele andere Verwendungsmöglichkeiten für Binärbäume, wie z. B.:

• Binäre Haufen mit höheren Schlüsseln sind über oder gleich unteren als links von (oder unter oder gleich und rechts);
• Hash-Bäume, ähnlich den Hash-Tabellen;
• Abstrakte Syntaxbäume für die Kompilierung von Computersprachen;
• Huffman-Bäume zur Komprimierung von Daten;
• Routing-Bäume für den Netzverkehr.

In Anbetracht der vielen Erklärungen, die ich für die Suchbäume gegeben habe, möchte ich nicht zu sehr ins Detail gehen, aber das sollte ausreichen, um sie zu erforschen, falls Sie es wünschen.

Answer 3

Die Organisation von Morsezeichen ist ein Binärbaum.

Answer 4

Ein Binärbaum ist eine Baumdatenstruktur, in der jeder Knoten höchstens zwei Kindknoten hat, die gewöhnlich als "links" und "rechts" bezeichnet werden. Knoten mit Kindern sind Elternknoten, und Kinderknoten können Verweise auf ihre Eltern enthalten. Außerhalb des Baums gibt es oft einen Verweis auf den "Root"-Knoten (den Vorgänger aller Knoten), falls dieser existiert. Jeder Knoten in der Datenstruktur kann erreicht werden, indem man beim Wurzelknoten beginnt und wiederholt Verweisen auf das linke oder rechte Kind folgt. In einem binären Baum ist der Grad jedes Knotens maximal zwei.

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

• Die Wurzel hat einen Wert von 31, der größer ist als 24, so dass Sie zum linken Knoten gehen.
• Der linke Knoten hat einen Wert von 15, also weniger als 24, also geht man zum rechten Knoten.
• Der rechte Knoten hat den Wert 23, der kleiner ist als 24, so dass Sie zum rechten Knoten gehen.
• Der rechte Knoten hat einen Wert von 27, der größer ist als 24, also geht man zum linken Knoten.
• Der linke Knoten hat einen Wert von 25, der größer ist als 24, also geht man zum linken Knoten.
• Der Knoten hat den Wert 24, der der gesuchte Schlüssel ist.

Diese Suche ist im Folgenden dargestellt:

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

Löschungen können komplex werden. Wenn der Knoten 0 oder 1 Kind hat, ist es einfach, einige Zeiger zu verschieben, um den zu löschenden Knoten auszuschließen. Ein Knoten mit 2 Kindern kann jedoch nicht einfach gelöscht werden. Also nehmen wir eine Abkürzung. Nehmen wir an, wir wollen den Knoten 19 löschen.

Da es nicht einfach ist, zu bestimmen, wohin der linke und der rechte Zeiger verschoben werden sollen, finden wir einen Ersatz. Wir gehen zum linken Teilbaum und dann so weit nach rechts wie möglich. So erhalten wir den nächstgrößeren Wert des Knotens, den wir löschen wollen.

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

---

Um diese Bilder zu erstellen, habe ich einen AVL-Baum implementiert, einen sich selbst ausgleichenden Baum, so dass der Baum zu jedem Zeitpunkt höchstens eine Stufe zwischen den Blattknoten (Knoten ohne Kinder) aufweist. Dadurch wird verhindert, dass der Baum schief wird, und es wird die maximale O(log n) Suchzeit, allerdings auf Kosten eines etwas höheren Zeitaufwands für Einfügungen und Löschungen.

Hier ist ein Beispiel dafür, wie mein RBL-Baum so kompakt und ausgewogen wie möglich gehalten wurde.

In einem sortierten Array würden die Suchvorgänge immer noch O(log(n)) wie ein Baum, aber das zufällige Einfügen und Entfernen würde O(n) anstelle des Baums O(log(n)) . Einige STL-Container nutzen diese Leistungsmerkmale zu ihrem Vorteil, so dass die Einfüge- und Entnahmezeiten maximal O(log n) was sehr schnell ist. Einige dieser Container sind map , multimap , set et multiset .

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

Answer 5

Die Hauptanwendung ist binäre Suchbäume . Es handelt sich um eine Datenstruktur, bei der das Suchen, Einfügen und Entfernen sehr schnell geht (etwa log(n) Operationen)