Get best of the week

Rot-schwarze Bäume in Javascript

Bild

Hallo Habr! Kürzlich untersuchte rot-schwarze Bäume. Ich habe versucht, die Details der Funktionsweise der Einfüge- und Löschalgorithmen auf d3.js zu visualisieren. Ich hoffe, das Ergebnis hilft denjenigen, die Algorithmen in Javascript studieren, Zeit zu sparen. Sie können es hier sehen . Der Quellcode der Implementierung, auf den ich mich hier verlassen habe . Unter Katze kurze Details.

Suchen Sie nach vorhandenen Lösungen


Das Hauptziel der Idee war es, die Implementierung des Algorithmus zu verstehen und zu visualisieren. Der erste Schritt bestand darin, nach einer Implementierung mit vollständigen und verständlichen Erklärungen und js-Code zu suchen. Während des Suchvorgangs war es traurig, dass die Autoren die Quelle zeitweise unvollendet ließen, zum Beispiel gibt es einen Einfügealgorithmus, aber keine Löschung. Oder sie tun Visualisierung wie diese , aber sie bieten keine Links zu der Quelle. Dann habe ich diesen ausgezeichneten Artikel gefunden. Aber zumindest töten, ich kann immer noch nicht verstehen, warum der Autor den Code mit Bildern eingefügt und auf Anfrage in Kommentaren keinen Link zum Quellcode angegeben hat. Es gibt auch ein npm-Rot-Schwarz-Baum-Paket , dessen gesamter Quellcode in der Readme-Datei lautet: 'in Bearbeitung ...'. Auch eine beliebte Implementierung gefunden rot-schwarze Bäume auf js, von denen viele Pakete und Millionen von Downloads pro Woche abhängen, aber der Code dort ist fünf Jahre alt.

Priorisierung und Aufgabenspezifikation


Porakinin Gehirn entschied ich, dass die Lesbarkeit und Verständlichkeit des Codes für Bildungszwecke eine Priorität ist, also nahm ich als Grundlage den Artikel, der am Anfang erwähnt wurde, und nicht das npm-Paket. Die Implementierung erwies sich hinsichtlich des Lesens von Code als bequemer und visueller. In dem Artikel beginnt der Autor mit einem Binärbaum und erweitert ihn dann auf Rot-Schwarz. Für die Visualisierung erscheint es ziemlich logisch, von einem rot-schwarzen Baum zu erben und einen animierten Baum zu erstellen. Nachdem ich den Code erneut eingegeben und sichergestellt hatte, dass er funktioniert, begann ich, einen animierten Baum zu zeichnen. D3.js. kommt zur Rettung. Es gibt wunderbare Übergänge, mit denen Sie Elemente an die richtigen Positionen verschieben und sie reibungslos in geeignete Zustände umwandeln können, während der Algorithmus funktioniert.

Die Bedeutung von rot-schwarzen Bäumen


Ich habe lange darüber nachgedacht, wie auf einfache Weise zu erklären, was was ist. Wahrscheinlich müssen Sie die Theorie trotzdem aus verschiedenen Quellen lesen. Wie das Sprichwort sagt: "Du wirst keine Worte aus einem Lied werfen." Einfache zusammenfassende Schlussfolgerungen können jedoch auf den Punkt gebracht werden. Das Fazit ist, dass es beim Einfügen und Löschen eines Elements mehrere Fälle gibt, je nachdem, welche „Großväter“, „Väter“, „Onkel“, „Kinder“, „Brüder“ neu streichen und sich zur Seite verschieben (drehen), wo weniger Elemente vorhanden sind . Infolgedessen kommt es nie vor, dass der Pfad vom entferntesten Knoten zum Wurzelknoten zu lang ist, sodass die Suche nach dem gewünschten Element in einer solchen Struktur sehr schnell ist. Nun, dies wird durch die Komplexität des Einfügens und Löschens ausgeglichen.

More articles:


All Articles