Frage

Ich habe in mehreren Büchern, die ich in letzter Zeit gelesen habe, Binärbäume und Binärsuche erwähnt, aber da ich noch am Anfang meines Informatikstudiums stehe, habe ich noch keinen Kurs belegt, der sich wirklich mit Algorithmen und Daten befasst Strukturen auf ernsthafte Weise.

Ich habe mich in den typischen Quellen umgesehen (Wikipedia, Google) und die meisten Beschreibungen der Nützlichkeit und Implementierung (insbesondere) von Rot-Schwarz-Bäumen sind dicht und schwer verständlich geworden.Ich bin mir sicher, dass es für jemanden mit dem nötigen Hintergrund durchaus Sinn macht, aber im Moment liest es sich fast wie eine Fremdsprache.

Was macht Binärbäume also für einige der häufigsten Aufgaben nützlich, die Sie beim Programmieren erledigen?Welche Bäume bevorzugen Sie darüber hinaus (bitte fügen Sie eine Beispielimplementierung bei) und warum?

War es hilfreich?

Lösung

Rot-Schwarz-Bäume eignen sich gut für die Schaffung ausgewogener Bäume.Das Hauptproblem bei binären Suchbäumen besteht darin, dass man sie sehr leicht aus dem Gleichgewicht bringen kann.Stellen Sie sich vor, Ihre erste Zahl ist eine 15.Dann sind alle Zahlen danach zunehmend kleiner als 15.Sie haben einen Baum, der auf der linken Seite sehr schwer ist und auf der rechten Seite nichts hat.

Rot-Schwarz-Bäume lösen dieses Problem, indem sie erzwingen, dass Ihr Baum bei jedem Einfügen oder Löschen ausgeglichen wird.Dies wird durch eine Reihe von Rotationen zwischen Vorgängerknoten und untergeordneten Knoten erreicht.Der Algorithmus ist eigentlich ziemlich einfach, obwohl er etwas lang ist.Ich würde vorschlagen, das CLRS-Lehrbuch (Cormen, Lieserson, Rivest und Stein) „Einführung in Algorithmen“ in die Hand zu nehmen und sich über RB-Bäume zu informieren.

Die Implementierung ist auch nicht wirklich so kurz, daher ist es wahrscheinlich nicht das Beste, sie hier aufzunehmen.Dennoch werden Bäume verwendet ausführlich für Hochleistungs-Apps, die Zugriff auf viele Daten benötigen.Sie bieten eine sehr effiziente Möglichkeit, Knoten zu finden, mit einem relativ geringen Aufwand für das Einfügen/Löschen.Auch hier würde ich vorschlagen, einen Blick auf CLRS zu werfen, um zu erfahren, wie sie verwendet werden.

Obwohl BSTs möglicherweise nicht explizit verwendet werden, gibt es in fast jedem modernen RDBMS ein Beispiel für die Verwendung von Bäumen im Allgemeinen.Ebenso wird Ihr Dateisystem mit ziemlicher Sicherheit als eine Art Baumstruktur dargestellt, und Dateien werden ebenfalls auf diese Weise indiziert.Bäume treiben Google an.Bäume versorgen nahezu jede Website im Internet.

Andere Tipps

Ich möchte nur auf die Frage eingehen: „Was macht Binärbäume also für einige der häufigen Aufgaben nützlich, die Sie beim Programmieren erledigen?“

Dies ist ein großes Thema, über das viele Menschen uneinig sind.Einige sagen, dass die in einem Informatikstudium gelehrten Algorithmen wie binäre Suchbäume und gerichtete Graphen in der alltäglichen Programmierung nicht verwendet werden und daher irrelevant sind.Andere sind anderer Meinung und sagen, dass diese Algorithmen und Datenstrukturen die Grundlage für unsere gesamte Programmierung bilden und es wichtig ist, sie zu verstehen, auch wenn Sie nie selbst einen schreiben müssen.Dies führt zu Gesprächen über gute Vorstellungsgespräche und Einstellungspraktiken.Zum Beispiel, Steve Yegge hat einen Artikel über Vorstellungsgespräch bei Google das geht auf diese Frage ein.Erinnern Sie sich an diese Debatte;Erfahrene Leute sind anderer Meinung.

Bei der typischen Geschäftsprogrammierung müssen Sie möglicherweise nicht oder gar nicht so oft Binärbäume erstellen.Sie werden jedoch viele Klassen verwenden, die intern mithilfe von Bäumen arbeiten.Viele der Kernorganisationsklassen in jeder Sprache verwenden Bäume und Hashes, um Daten zu speichern und darauf zuzugreifen.

Wenn Sie an anspruchsvolleren Unternehmungen oder Situationen beteiligt sind, die etwas außerhalb der Norm der Geschäftsprogrammierung liegen, werden Sie Bäume als unmittelbaren Freund empfinden.Wie ein anderer Poster sagte, sind Bäume Kerndatenstrukturen für Datenbanken und Indizes aller Art.Sie sind nützlich beim Data Mining und bei der Visualisierung, bei erweiterten Grafiken (2D und 3D) und einer Vielzahl anderer Rechenprobleme.

Ich habe Binärbäume in der Form verwendet BSP-Bäume (Binary Space Partitioning). in 3D-Grafiken.Ich beschäftige mich derzeit erneut mit Bäumen, um große Mengen geokodierter Daten und anderer Daten zur Informationsvisualisierung in Flash/Flex-Anwendungen zu sortieren.Wann immer Sie die Grenzen der Hardware überschreiten oder mit niedrigeren Hardwarespezifikationen arbeiten möchten, kann das Verständnis und die Auswahl des besten Algorithmus den Unterschied zwischen Misserfolg und Erfolg ausmachen.

In keiner der Antworten wird erwähnt, wozu BSTs genau gut sind.

Wenn Sie nur nach Werten suchen möchten, ist eine Hashtabelle viel schneller, O(1)-Einfügung und Suche (amortisierter Bestfall).

Ein BST ist eine O(log N)-Suche, wobei N die Anzahl der Knoten im Baum ist, Einfügungen sind ebenfalls O(log N).

RB- und AVL-Bäume sind aufgrund dieser Eigenschaft wie eine andere erwähnte Antwort wichtig. Wenn ein einfacher BST mit Werten in der richtigen Reihenfolge erstellt wird, ist der Baum so hoch wie die Anzahl der eingefügten Werte, was sich negativ auf die Suchleistung auswirkt.

Der Unterschied zwischen RB- und AVL-Bäumen besteht in den Rotationen, die zum Neuausgleich nach einem Einfügen oder Löschen erforderlich sind. AVL-Bäume sind O(log N) für Neuausgleiche, während RB-Bäume O(1) sind.Ein Beispiel für den Vorteil dieser konstanten Komplexität ist der Fall, dass Sie möglicherweise eine persistente Datenquelle behalten. Wenn Sie Änderungen für ein Rollback verfolgen müssen, müssten Sie O(log N) mögliche Änderungen mit einem AVL-Baum verfolgen.

Warum wären Sie bereit, die Kosten für einen Baum statt für eine Hash-Tabelle zu zahlen?BEFEHL!Hash-Tabellen haben keine Ordnung, BSTs hingegen sind aufgrund ihrer Struktur immer natürlich geordnet.Wenn Sie also eine Menge Daten in ein Array oder einen anderen Container werfen und diese später sortieren, ist ein BST möglicherweise die bessere Lösung.

Die order-Eigenschaft des Baums bietet Ihnen eine Reihe geordneter Iterationsfunktionen: in der Reihenfolge, in der Tiefe zuerst, in der Breite zuerst, vor der Reihenfolge und nach der Reihenfolge.Diese Iterationsalgorithmen sind unter verschiedenen Umständen nützlich, wenn Sie sie nachschlagen möchten.

Rot-Schwarz-Bäume werden intern in fast jedem geordneten Container von Sprachbibliotheken, C++-Sets und Maps, .NET SortedDictionary, Java TreeSet usw. verwendet.

Bäume sind also sehr nützlich, und Sie können sie oft verwenden, ohne es zu wissen.Das wirst du höchstwahrscheinlich nie tun brauchen selbst eines zu schreiben, obwohl ich es als interessante Programmierübung wärmstens empfehlen würde.

Rot-Schwarz-Bäume und B-Bäume werden für alle Arten der dauerhaften Speicherung verwendet;Da die Bäume ausbalanciert sind, wird die Leistung von Breiten- und Tiefendurchquerungen gemindert.

Fast alle modernen Datenbanksysteme verwenden Bäume zur Datenspeicherung.

BSTs bringen die Welt in Bewegung, wie Michael sagte.Wenn Sie auf der Suche nach einem guten Baum sind, den Sie umsetzen können, werfen Sie einen Blick auf AVL-Bäume (Wikipedia).Sie unterliegen einer Ausgleichsbedingung und sind daher garantiert O(logn).Diese Art der Sucheffizienz macht es logisch, jede Art von Indexierungsprozess durchzuführen.Das Einzige, was effizienter wäre, wäre eine Hashing-Funktion, aber diese wird schnell, schnell und in Eile hässlich.Außerdem stoßen Sie auf die Geburtstagsparadoxon (auch als Schubladenproblem bekannt).

Welches Lehrbuch verwenden Sie?Wir verwendeten Datenstrukturen und Analyse in Java von Mark Allen Weiss.Ich habe es tatsächlich aufgeschlagen auf meinem Schoß, während ich das schreibe.Es gibt einen großartigen Abschnitt über Rot-Schwarz-Bäume und enthält sogar den Code, der zum Implementieren aller Bäume erforderlich ist, über die es spricht.

Rot-schwarze Bäume bleiben im Gleichgewicht, sodass Sie nicht tief durchqueren müssen, um Gegenstände herauszuholen.Die eingesparte Zeit führt dazu, dass RB-Bäume im SCHLECHTESTEN Fall O(log()n)) sind, wohingegen unglückliche Binärbäume in eine einseitige Konfiguration geraten und Abrufe in O(n) verursachen können, was im schlimmsten Fall der Fall ist.Dies geschieht in der Praxis oder anhand zufälliger Daten.Wenn Sie also zeitkritischen Code benötigen (Datenbankabrufe, Netzwerkserver usw.), verwenden Sie RB-Bäume, um geordnete oder ungeordnete Listen/Sets zu unterstützen.

Aber RBTrees sind etwas für Anfänger!Wenn Sie KI verwenden und eine Suche durchführen müssen, stellen Sie fest, dass Sie die Statusinformationen häufig verzweigen.Sie können ein persistentes Rot-Schwarz verwenden, um neue Zustände in O(log(n)) zu forken.Ein persistenter Rot-Schwarz-Baum behält eine Kopie des Baums vor und nach einer morphologischen Operation (Einfügen/Löschen), jedoch ohne den gesamten Baum zu kopieren (normalerweise und O(log(n))-Operation).Ich habe einen persistenten rot-schwarzen Baum für Java als Open Source bereitgestellt

http://edinburghhacklab.com/2011/07/a-java-implementation-of-persistent-red-black-trees-open-sourced/

Die beste Beschreibung rot-schwarzer Bäume, die ich gesehen habe, ist die in „Introduction to Algorithms“ von Cormen, Leisersen und Rivest.Ich konnte es sogar so gut verstehen, dass ich es teilweise umsetzen konnte (nur Einfügen).Es gibt auch einige Applets wie z Dieses hier auf verschiedenen Webseiten, die den Prozess animieren und es Ihnen ermöglichen, eine grafische Darstellung des Algorithmus beim Aufbau einer Baumstruktur zu beobachten und durchzugehen.

Da Sie fragen, welchen Baum die Leute verwenden, müssen Sie wissen, dass ein Rot-Schwarz-Baum grundsätzlich ein 2-3-4 B-Baum ist (d. h. ein B-Baum der Ordnung 4).Ein B-Baum ist nicht entspricht einem Binärbaum (wie in Ihrer Frage gestellt).

Hierist eine ausgezeichnete Ressource, die die anfängliche Abstraktion beschreibt, die als symmetrischer binärer B-Baum bekannt ist und sich später zum RBTree entwickelte.Sie müssen die B-Bäume gut verstehen, bevor es einen Sinn ergibt.Zusammenfassen:Ein „roter“ Link in einem Rot-Schwarz-Baum ist eine Möglichkeit, Knoten darzustellen, die Teil eines B-Baum-Knotens sind (Werte innerhalb eines Schlüsselbereichs), wohingegen „schwarze“ Links Knoten sind, die vertikal in einem B-Baum verbunden sind.

Folgendes erhalten Sie also, wenn Sie die Regeln eines Rot-Schwarz-Baums in einen B-Baum übersetzen (ich verwende das Format Rot-Schwarz-Baum-Regel => B-Baum-Äquivalent):

1) Ein Knoten ist entweder rot oder schwarz.=> Ein Knoten in einem B-Baum kann entweder Teil eines Knotens oder ein Knoten in einer neuen Ebene sein.

2) Die Wurzel ist schwarz.(Diese Regel wird manchmal weggelassen, da sie keinen Einfluss auf die Analyse hat) => Der Wurzelknoten kann entweder als Teil eines internen Wurzelknotens oder als untergeordnetes Element eines imaginären übergeordneten Knotens betrachtet werden.

3) Alle Blätter (NIL) sind schwarz.(Alle Blätter haben die gleiche Farbe wie die Wurzel.) => Da eine Möglichkeit zur Darstellung eines RB-Baums darin besteht, die Blätter wegzulassen, können wir dies ausschließen.

4) Beide Kinder jedes roten Knotens sind schwarz.=> Die Kinder eines internen Knotens in einem B-Baum liegen immer auf einer anderen Ebene.

5) Jeder einfache Pfad von einem bestimmten Knoten zu einem seiner Nachkommenblätter enthält die gleiche Anzahl schwarzer Knoten.=> Ein B-Baum wird im Gleichgewicht gehalten, da alle Blattknoten die gleiche Tiefe haben müssen (Daher wird die Höhe eines B-Baumknotens durch die Anzahl der schwarzen Verbindungen von der Wurzel bis zum Blatt eines rot-schwarzen Baums dargestellt )

Außerdem gibt es eine einfachere „nicht standardmäßige“ Implementierung von Robert Sedgewick Hier:(Er ist der Autor des Buches Algorithmen zusammen mit Wayne)

Hier gibt es viel, viel Wärme, aber nicht viel Licht, also schauen wir mal, ob wir etwas spenden können.

Erste, ein RB-Baum ist eine assoziative Datenstruktur, anders als beispielsweise ein Array, das keinen Schlüssel annehmen und einen zugehörigen Wert zurückgeben kann, es sei denn, es handelt sich um einen ganzzahligen „Schlüssel“ in einem 0 %-Sparse-Index zusammenhängender Ganzzahlen.Ein Array kann auch nicht größer werden (ja, ich kenne auch realloc(), aber unter der Decke erfordert das ein neues Array und dann ein memcpy()). Wenn Sie also eine dieser Anforderungen haben, reicht ein Array nicht aus .Die Speichereffizienz eines Arrays ist perfekt.Keine Verschwendung, aber nicht sehr intelligent oder flexibel – realloc() nicht beständig.

Zweite, Im Gegensatz zu einem bsearch() für ein Array von Elementen, bei dem es sich um eine assoziative Datenstruktur handelt, kann ein RB-Baum dynamisch wachsen (UND schrumpfen).Die Funktion bsearch() eignet sich hervorragend für die Indizierung einer Datenstruktur bekannter Größe, die diese Größe beibehält.Wenn Sie also die Größe Ihrer Daten nicht im Voraus kennen oder neue Elemente hinzugefügt oder gelöscht werden müssen, ist bsearch() die Lösung.Bsearch() und qsort() werden beide im klassischen C gut unterstützt und weisen eine gute Speichereffizienz auf, sind jedoch für viele Anwendungen nicht dynamisch genug.Sie sind jedoch mein persönlicher Favorit, weil sie schnell und einfach sind und oft flexibel genug sind, wenn Sie nicht mit Echtzeit-Apps arbeiten.Darüber hinaus können Sie in C/C++ ein Array von Zeigern auf Datensätze sortieren, indem Sie beispielsweise auf den struc{}-Member zeigen, den Sie vergleichen möchten, und dann den Zeiger im Zeiger-Array so neu anordnen, dass die Zeiger der Reihe nach gelesen werden Am Ende des Zeigers liefert die Sortierung Ihre Daten in sortierter Reihenfolge.Die Verwendung mit speicherzugeordneten Datendateien ist äußerst speichereffizient, schnell und relativ einfach.Alles, was Sie tun müssen, ist, Ihrer Vergleichsfunktion(en) ein paar „*“ hinzuzufügen.

Dritte, Im Gegensatz zu einer Hashtabelle, die ebenfalls eine feste Größe haben muss und nach dem Füllen nicht mehr vergrößert werden kann, wächst ein RB-Baum automatisch selbst und gleicht sich aus, um seine O(log(n))-Leistungsgarantie aufrechtzuerhalten.Insbesondere wenn der Schlüssel des RB-Baums ein int ist, kann er schneller sein als ein Hash, denn obwohl die Komplexität einer Hash-Tabelle O(1) ist, kann dieser Wert eine sehr teure Hash-Berechnung sein.Die mehrfachen 1-Takt-Ganzzahlvergleiche eines Baums übertreffen oft die 100-Takt+-Hash-Berechnungen, ganz zu schweigen vom erneuten Aufwärmen und dem Malloc()ing-Speicherplatz für Hash-Kollisionen und erneute Aufbereitungen.Wenn Sie schließlich ISAM-Zugriff sowie Schlüsselzugriff auf Ihre Daten wünschen, ist ein Hash ausgeschlossen, da es im Gegensatz zur natürlichen Reihenfolge der Daten in jeder Baumimplementierung keine inhärente Reihenfolge der Daten in der Hashtabelle gibt.Die klassische Verwendung einer Hash-Tabelle besteht darin, einem Compiler verschlüsselten Zugriff auf eine Tabelle reservierter Wörter zu ermöglichen.Die Speichereffizienz ist ausgezeichnet.

Vierte, Ganz unten auf jeder Liste steht die verknüpfte oder doppelt verknüpfte Liste, die im Gegensatz zu einem Array natürlich das Einfügen und Löschen von Elementen und damit auch die Größenänderung unterstützt.Es ist die langsamste aller Datenstrukturen, da jedes Element nur weiß, wie es zum nächsten Element gelangt. Sie müssen also durchschnittlich (element_knt/2) Links durchsuchen, um Ihr Datum zu finden.Es wird vor allem dort verwendet, wo Einfügungen und Löschungen irgendwo in der Mitte der Liste üblich sind, und vor allem, wenn die Liste kreisförmig ist und einen teuren Prozess erfordert, der die Zeit zum Lesen der Links relativ kurz macht.Mein allgemeiner RX besteht darin, ein beliebig großes Array anstelle einer verknüpften Liste zu verwenden, wenn Ihre einzige Anforderung darin besteht, dass die Größe zunehmen kann.Wenn Ihnen die Größe eines Arrays ausgeht, können Sie ein größeres Array mit realloc() erstellen.Das STL erledigt dies für Sie „unter der Decke“, wenn Sie einen Vektor verwenden.Grob, aber möglicherweise tausendmal schneller, wenn Sie keine Einfügungen, Löschungen oder Schlüsselsuchen benötigen.Die Speichereffizienz ist schlecht, insbesondere bei doppelt verknüpften Listen.Tatsächlich ist eine doppelt verknüpfte Liste, die zwei Zeiger erfordert, genauso speicherineffizient wie ein Rot-Schwarz-Baum, weist aber KEINE seiner verlockenden schnellen, geordneten Abrufeigenschaften auf.

Fünfte, Bäume unterstützen viele zusätzliche Operationen an ihren sortierten Daten als jede andere Datenstruktur.Beispielsweise machen sich viele Datenbankabfragen die Tatsache zunutze, dass ein Bereich von Blattwerten einfach angegeben werden kann, indem deren gemeinsames übergeordnetes Element angegeben wird und die anschließende Verarbeitung dann auf den Teil des Baums konzentriert wird, der diesem übergeordneten Element „gehört“.Das Potenzial für Multithreading, das dieser Ansatz bietet, sollte offensichtlich sein, da nur ein kleiner Bereich des Baums gesperrt werden muss – nämlich nur die Knoten, die dem übergeordneten Knoten gehören, und der übergeordnete Knoten selbst.

Kurz gesagt, Bäume sind der Cadillac unter den Datenstrukturen.Sie zahlen einen hohen Preis für den genutzten Speicher, erhalten dafür aber eine völlig selbstverwaltende Datenstruktur.Aus diesem Grund verwenden Transaktionsdatenbanken, wie bereits in anderen Antworten hier erwähnt, fast ausschließlich Bäume.

Wenn Sie sehen möchten, wie ein Rot-Schwarz-Baum grafisch aussehen soll, habe ich eine Implementierung eines Rot-Schwarz-Baums codiert, die Sie finden können Hier herunterladen

IME, fast niemand versteht den RB-Baum-Algorithmus.Die Leute können Ihnen die Regeln wiederholen, aber sie verstehen es nicht Warum diese Regeln und woher sie kommen.Ich bin keine Ausnahme :-)

Aus diesem Grund bevorzuge ich den AVL-Algorithmus, weil er einfach ist begreifen.Sobald Sie es verstanden haben, können Sie es von Grund auf neu programmieren, weil es für Sie sinnvoll ist.

Bäume können schnell sein.Wenn Sie eine Million Knoten in einem ausgeglichenen Binärbaum haben, sind durchschnittlich zwanzig Vergleiche erforderlich, um ein Element zu finden.Wenn eine verknüpfte Liste eine Million Knoten enthält, sind durchschnittlich fünfhunderttausend Vergleiche erforderlich, um dasselbe Element zu finden.

Wenn der Baum jedoch unausgeglichen ist, kann er genauso langsam sein wie eine Liste. Und Außerdem wird mehr Speicherplatz benötigt.Stellen Sie sich einen Baum vor, in dem die meisten Knoten ein rechtes Kind, aber kein linkes Kind haben;Es Ist eine Liste, aber Sie müssen immer noch Speicherplatz freihalten, um ihn in den linken Knoten einzufügen, falls einer angezeigt wird.

Wie auch immer, die AVL-Baum war der erste ausgeglichene Binärbaum-Algorithmus, und der Wikipedia-Artikel dazu ist ziemlich klar.Der Wikipedia-Artikel über rot-schwarze Bäume ist ehrlich gesagt klar und deutlich.

Über Binärbäume hinaus sind B-Bäume Bäume, bei denen jeder Knoten viele Werte haben kann.B-Baum ist nicht ein binärer Baum, so heißt es zufällig.Sie sind wirklich nützlich, um den Speicher effizient zu nutzen.Jeder Knoten des Baums kann so dimensioniert werden, dass er in einen Speicherblock passt, sodass Sie nicht (langsam) Unmengen verschiedener Dinge im Speicher finden müssen, der auf die Festplatte ausgelagert wurde.Hier ist ein phänomenales Beispiel dafür B-Baum.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top