Ist es in Ordnung, RB-Bäume nicht vollständig zu verstehen? [geschlossen]

15

Also habe ich gerade bei Cormen rot-schwarze Bäume gelernt und wow! Normalerweise verstehe ich gerne alle Algorithmen und Datenstrukturen bis zu dem Punkt, an dem ich sie von Grund auf neu erstellen kann, ohne den Pseudocode zu betrügen. Ich mag Algorithmen sehr, deshalb lerne ich gerne, wie sie funktionieren. Normalerweise gehe ich Zeile für Zeile und probiere einige Fälle aus, indem ich mir den Code ansehe und überprüfe, ob das, was passiert, das ist, was ich verstanden habe.

Nur zu verstehen, was passiert, hat mir viel Zeit für RB-Bäume gekostet. Trotz der Erklärungen des Buches fiel es mir immer noch schwer, den Code zu verstehen. Ganz zu schweigen davon, dass ich nicht verstehen konnte, wie / warum Rotationen funktionieren. Ich finde es überhaupt nicht intuitiv. Ich meine, die drei (eigentlich sechs) verschiedenen Fälle zum Einfügen und dann die 4 Fälle zum Löschen? Ist es möglich, diese Sache zu verstehen? Es ist unmöglich für mich, diesen Code ohne Schummeln neu zu erstellen. Bis zum Binärbaum konnte ich das Zeug aus meinem Kopf heraus implementieren, mit einigem Optimierungsaufwand würde es immer funktionieren, aber RB-Bäume werde ich nicht einmal versuchen. Ich meine, sogar der Lehrer war manchmal verwirrt, also denke ich, dass es wirklich nicht so einfach ist, aber sollten wir nicht gleichzeitig alles verstehen müssen, was passiert, oder zumindest warum? Das Buch hat nicht t wirklich erklären, wie jemand auf die Idee von Rotationen kam. Wie ist jemand aufgefallen, dass Sie mit 2 Umdrehungen ein Einfügeproblem lösen können? Das ist erstaunlich!

Meine Frage ist, muss ich RB-Bäume wirklich zu 100% verstehen? Ich fühle mich irgendwie schlecht, wenn ich Sachen überspringe, ohne es vollständig zu verstehen. Vielen Dank im Voraus Jungs! (PS: Es gibt kein Tag für RB-Tree, eigentlich nicht einmal für Tree, nur für Binary-Tree, also setze ich nur Algorithmen)

algorithms Bernardo Pires
quelle
18
"Junger Mann, in der Mathematik versteht man die Dinge nicht. Man gewöhnt sich einfach daran." - John von Neumann
2
@Clash In welchem ​​Kontext? Ich glaube nicht, dass ich jemals wissen musste, wie RB-Bäume in einer professionellen Umgebung funktionieren, aber das kann variieren, je nachdem, was Sie tun möchten. Ich würde sagen, es ist in Ordnung, sie zu überspringen, bis Sie sie brauchen.
Adam Lear
4
@Clash Es stört mich ungemein, dass du sagst, es sei "Betrug", etwas mit Hilfe einer externen Quelle umzusetzen. Der Pseudocode existiert aus einem Grund - sie eliminieren die Notwendigkeit, dies aus dem Speicher zu tun. Ich stimme Winston voll und ganz zu: Verstehen und Wissen aus dem Gedächtnis schließen sich gegenseitig aus. Auswendiglernen! = Verstehen und Verstehen! = Auswendiglernen.
doppelgreener
3
Es ist in Ordnung, sich nicht wirklich um RB-Bäume zu kümmern - bis ich sie brauche?
Steven A. Lowe
1
Vielleicht verstehen Sie, WANN Sie RB-Bäume verwenden sollten, vor allen anderen Arten der Baumimplementierung. Wissen, welche Probleme sie lösen, und alle Gründe für die Wahl von RB-Bäumen. Wenn Sie jedoch jemals eine implementieren müssen (natürlich außerhalb einer Prüfung), können Sie sie nachschlagen. Warum also die Mühe machen, aus dem Gedächtnis heraus zu wissen, wie es geht?
Dawood sagt, Monica

Antworten:

13

Sie scheinen die Idee des "Verstehens" mit "den Code schreiben zu können, ohne das Buch anzusehen" gleichzusetzen. Das sind zwei verschiedene Dinge. Wenn Sie sehen, wie durch Drehen der Baumknoten der Baum neu angeordnet wird, um das Gleichgewicht aufrechtzuerhalten, verstehen Sie dies. Es ist nicht der Punkt, alle Fälle, für die Rotationen gelten, sofort abrufen zu können.

Ich selbst könnte wahrscheinlich die Drehungen herausfinden, wenn ich Stift / Papier / mehrere Stunden hätte, um damit zu spielen. Aber ich konnte es bestimmt nicht ohne nachzudenken aufschreiben. Wenn ich tatsächlich einen solchen Algorithmus schreiben müsste, würde ich ihn nachschlagen, um sicherzustellen, dass alle Details stimmen. Natürlich würde ich in fast jeder Situation bereits geschriebenen Code verwenden.

All dies kommt zum Einsatz, wenn Sie auf eine Situation stoßen, die keinem der Algorithmen entspricht. Sie müssen niemals Ihre eigene Baumimplementierung schreiben. Aber Sie könnten beispielsweise feststellen, dass Sie eine Reihe von doppelt verknüpften Listen abflachen müssen. In diesem Fall kann es sehr hilfreich sein, die Grundidee der Rotation zu verstehen.

Winston Ewert
quelle
2
"Sie scheinen die Idee des" Verstehens "mit" den Code schreiben zu können, ohne auf das Buch zu schauen "gleichzusetzen. Das sind zwei verschiedene Dinge. ' Äh ... nein. Wenn Sie dies schreiben, bedeutet dies wahrscheinlich, dass Sie nicht viel mehr als ein oder zwei Jahre am College Mathematik studiert haben, wenn auch nicht das. Irgendwann geht es beim "Verstehen" von Mathematik (was mit freundlicher Genehmigung von Turing mit dem Rechnen gleichgesetzt wird) nur darum, zu demonstrieren, was Sie "verstanden" haben. Es gibt keinen Workaround oder Ifs oder Maybes oder Foo oder Bar oder Baz. Wenn Sie auf dieser Ebene Ihre mathematische Behauptung nicht beweisen können, stoßen Sie an. (Es sei denn, Ihr Name ist Fermat.)
Denis de Bernardy
14
@ Tennis, ich habe einen MS in CS mit überdurchschnittlich vielen Mathekursen für den Hauptfach. Ich fürchte, Sie haben meinen Standpunkt nicht verstanden. Es ist sehr wichtig zu beweisen oder zu demonstrieren, was Sie verstehen. In der Lage zu sein, sich die Details eines Beweises oder einer Methode zu merken, ist es nicht. Sie sollten in der Lage sein, den Code zu schreiben. Aber ich sehe keine Verwendung für eine Anforderung, in der Lage zu sein, den Code von MEMORY zu schreiben.
Winston Ewert
2
Seien Sie vorsichtig, wo Sie es auch nachschlagen - IIRC, einige Lehrbücher haben erhebliche Fehler in ihren rot-schwarzen Baumalgorithmen.
Steve314
2
@ Steve314, du musst RB nicht einmal verstehen, um ein Lehrbuchautor zu sein! ;)
Winston Ewert
Danke Winston, das erleichtert mich! Es gibt nur ein paar Dinge, die ich mit dem Code, den ich in naher Zukunft veröffentlichen könnte, nicht verstanden habe. Aber ich bin so froh, dass es in Ordnung ist, nicht zu verstehen (unter Verstehen meine ich, den Code zu schreiben, ohne zu schummeln), warum / wie jemand die 3/6-Fälle zum Einfügen und 4/8-Fälle zum Löschen bemerkt hat.
Bernardo Pires
4

Wenn Sie mit funktionaler Programmierung vertraut sind, finden Sie diese Herangehensweise möglicherweise besser (Okasaki 1999):

http://www.eecs.usma.edu/webs/people/okasaki/jfp99redblack.pdf

Wenn nicht, nimm wenigstens den Anfangssatz zur Kenntnis:

Jeder lernt in seinen einführenden Informatikkursen etwas über ausgeglichene binäre Suchbäume, aber selbst die Betroffenen zittern bei dem Gedanken , ein solches Biest tatsächlich zu implementieren .

Ryan Culpepper
quelle
Hahah Ryan! Das erleichtert mich doch! Danke vielmals! Heute ist mir auch aufgefallen, dass es zu RB-Trees sehr wenige Fragen zu SO gibt. Ich nehme an, sie sind wirklich knifflig.
Bernardo Pires
2
Ich denke, es ist nur so, dass sie, abgesehen von CS-Studenten, ungefähr einmal pro Programmiersprache implementiert werden. (Oder weniger. Ich denke, der beliebteste RB-Code für Schema wurde aus dem RB-Code für OCaml portiert.)
Ryan Culpepper
Verbindung ist unterbrochen: Spiegel 1 , Spiegel 2 . Vollständiges Zitieren für den Fall, dass beide Spiegel zu irgendeinem Zeitpunkt in der Zukunft nicht verfügbar sind: Chris Okasaki, "Rot-Schwarze Bäume in einer funktionalen Umgebung", Journal of Functional Programming, 9 (4), S. 471-477, Juli 1999.
Snowball
3

Sie müssen die Rotationen nicht im Detail verstehen. Sie sollten die Beziehung zwischen RB-Bäumen und 2-3-4 Bäumen verstehen (siehe Sedgewick). All diese verrückten Rotationen sind viel sinnvoller, wenn man sie als 2-3-4 Bäume ansieht. Wenn Ihr Professor RB-Bäume nicht als Implementierungsdetail für 2-3-4 Bäume gelehrt hat, sollten Sie wahrscheinlich etwas über 2-3-4 Bäume lesen. (Sedgewicks Behandlung ist ziemlich gut; Wikipedia hat sie nicht.)

Allgemeiner ist es nur manchmal nützlich, die Implementierungsdetails zu verstehen, warum ein Algorithmus funktioniert. Es ist fast immer nützlich, die Logik der Funktionsweise des Algorithmus zu verstehen. Es ist normalerweise nicht erforderlich, den Algorithmus selbst zu entwickeln. Je mehr Algorithmen Sie jedoch verstehen, desto größer ist Ihre Chance.

Rex Kerr
quelle
1

Wenn Sie nächste Woche "RB Trees By Heart" für Ihre Prüfung benötigen, müssen Sie die Kugel beißen und sie lernen. In diesem Fall sollten Sie Ihre Lernmethoden überdenken. Vielleicht hilft Ihnen der Versuch, RB Trees einem Klassenkameraden zu erklären, mehr als eine weitere Nacht einsamen Code-Schreibens.

Wenn RB Trees eine Basis für Ihren nächsten Kurs nach den Ferien sind, überspringen Sie sie jetzt (ohne schlechte Gefühle) und konzentrieren Sie sich auf den Kurs dieses Semesters. Aber halten Sie nach Themen Ausschau, die Sie auf einen zweiten Versuch bei RB Trees vorbereiten könnten.

Wenn Sie ehrlich gesagt das Gefühl haben, dass Sie sie nie wirklich brauchen werden (vgl. Anna Lears Kommentar), küssen Sie sie ohne Reue auf Wiedersehen - niemand weiß mehr, dass ein Tropfen des Wissensmeeres (nur schade, dass Lehrer oft denken, dass ihr Tropfen der größte ist) wichtig).

Ekkehard.Horner
quelle
1

Der Schlüssel zum Programmiererfolg ist, niemals aufzugeben :

Heute sind seine RB Bäume morgen wird es etwas anderes sein. Die größere Lektion gibt nicht auf .

Für mich ist das einer der Kernpunkte des Programmierens, nicht aufzugeben ...

Ich würde vorschlagen, dass Sie weiter versuchen , und wenn Sie scheitern, tun Sie es wieder .

"Bis Sie bekommen, bis es klickt, bis es läuft."

Denn sobald Sie die Berge überwunden haben, wird der Himmel klar. Dein Verstand verändert sich im Verständnis, du bist zeitlich erhöht (bis zum nächsten Berg) . Diese zeitliche Erhebung ist mehr wert als alles Geld der Welt.

Dunkle Nacht
quelle
Danke, das war genau meine Angst! Wenn ich das aufgebe, was hindert mich daran, das nächste aufzugeben? Deshalb habe ich fast einen ganzen Tag damit verbracht, das Einfügen und Löschen zu verstehen.
Bernardo Pires
Es ist nie eine Verschwendung, glauben Sie mir, wenn es die Erhebung "klickt", macht das alles wieder wett.
Darknight
0

Der beste Weg, es zu verstehen, ist, es auszuprobieren :

  • Es gibt 3 oder 6 Umdrehungen. Nehmen Sie ein Stück Papier und schreiben Sie es einzeln auf.
  • Sobald Sie es erhalten haben, implementieren Sie einen rot-schwarzen Baum. Es ist in Ordnung, wenn Sie ein paar Dinge nachschlagen müssen.

So haben wir es am College gemacht. Und für die Prüfung mussten wir erklären, wie ein Teil davon funktionierte.

Carra
quelle