Ich implementiere einen Red Black Tree mit Einfüge-, Such- und Löschfunktionen in O (log n) -Zeit. Einfügen und Suchen funktionieren einwandfrei. Allerdings stecke ich beim Löschen fest. Ich fand diese PPT-Folie im Internet, die den Algorithmus der RBT-Löschung zeigt: Ссылка auf Seite 56 weiter. Ich weiß, dass ich ein bisschen zu viel frage, aber ich stecke seit über zwei Wochen darauf und ich kann das Problem nicht finden. So wie ich die Top-Down-Löschung verstehe, müssen Sie Knoten entsprechend rotieren und neu einfärben, bis Sie den Vorgänger des Knotens gefunden haben, der gelöscht werden soll. Wenn Sie diesen Knoten finden - der entweder ein Blatt oder ein Knoten mit einem rechten Kind wäre, ersetzen Sie die zu löschenden Daten durch die Daten dieses Knotens und löschen Sie diesen Knoten wie bei der normalen BST-Löschung, oder?
Dies ist der Code, den ich gemacht habe, basierend auf dem, was ich von dieser Folie gelernt habe. Wenn jemand so nett wäre, darüber zu sprechen, wäre ich mehr als dankbar! Oder zumindest, wenn du denkst, dass es einen besseren Algorithmus gibt als den, den ich benutze, sag es mir bitte!
%Vor%Der Knoten wird gelöscht, aber der Baum nach dem Löschen wäre schwarz verletzt, was sehr falsch ist.
Der ewig verwirrte Blog enthält Top-down-Implementierungen sowohl von Einfügung als auch von Löschung für Rot-Schwarz-Bäume . Es geht auch von Fall zu Fall, warum es funktioniert. Ich werde es hier nicht replizieren (es ist ziemlich lang).
Ich habe diesen Blog als Referenz für die Implementierung von rot-schwarzen Bäumen in C ++ und Java verwendet. Wie ich bereits in einer früheren früheren Antwort erläutert habe, war die Implementierung schneller als die bottom-up-Implementierung von rot von std :: map -schwarze Bäume (was auch immer STL kam mit gcc zu der Zeit).
Hier ist eine ungetestete, direkte Übersetzung des Codes nach Java. Ich würde sehr empfehlen, dass Sie es testen und es an Ihren Stil anpassen.
%Vor%schneller Link: Ссылка
- & gt; Vorsicht: Der Code auf der Website basiert auf zwei Gläsern. In den Datenstrukturen kann die Abhängigkeit jedoch minimal sein. Manchmal genügt es, die Hauptmethode (die nur als Test-Client dient) zu kommentieren. Wenn nicht: Die Gläser können auf der gleichen Website heruntergeladen werden.
Wenn Sie nach zwei Wochen suchen und Algorithmien studieren, sind die Chancen gut, dass Sie davon wissen
die Website, die das berühmte
begleitetAlgorithmen, von Robert Sedgewick und Kevin Wayne
Buch.
Auf dieser Website gibt es diese Implementierung eines rotschwarzen (Balances) Baumes:
Ich habe es noch nicht untersucht (ich werde später in diesem Jahr), aber ich vertraue voll und ganz darauf, dass es eine funktionierende Implementierung eines RBTree ist.
Einige Randnotizen, die für Besucher dieses Themas interessant sein könnten: Das MIT hat exzellente Kurse zu Algorithms online gestellt. Die eine betrifft rbtrees ist Ссылка
Tags und Links java data-structures red-black-tree top-down