In CLRS führen die Autoren die Rotationsoperation in einem rot-schwarzen Baum durch folgenden Pseudocode ein:
LEFT-ROTATE(T, x)
y = x.right # Line 1
x.right = y.left # Line 2
if y.left ≠ T.nil # Line 3
y.left.p = x # Line 4
y.p = x.p
if x.p == T.nil
T.root = y
elseif x == x.p.left
x.p.left = y
else x.p.right = y
y.left = x
x.p = y
Wobei das Attribut .left, .right, .p seinem linken, rechten Kind und seinem Elternteil entspricht. T ist der Baum.
Meine Hauptfragen liegen in Zeile 3 und Zeile 4:
Warum muss ich die if-Bedingung von Zeile 3 haben? Das Buch sagt, dass NIL tatsächlich ein Blatt des rot-schwarzen Baums ist, daher gehe ich davon aus, dass NIL auch einen übergeordneten Zeiger haben kann. Diese Codes sollten weiterhin ohne Zeile 3 funktionieren.
Kann ich mit Zeile 1 und Zeile 2 Zeile 4 als schreiben
x.right.p = x
? Wenn sie tatsächlich gleich sind, gibt es einen Grund, als den der Autor sie geschrieben haty.left.p = x
?
Mein Instinkt ist, dass x.right.p = x
das anders ist als y.left.p = x
. Ich kann jedoch keine gute Erklärung dafür finden. Ich habe die Definition von Zeigern überprüft , aber es ist immer noch ziemlich verwirrend, nachdem ich viel gegoogelt habe ...
quelle
parent
enthält, existiert nicht, existiert alsoparent
nicht.Nachdem ich die letzte Zeile Ihrer Beschreibung gelesen hatte, bemerkte ich, dass Sie keine Hinweise gelernt haben. Daher fällt es Ihnen möglicherweise schwer zu verstehen, warum wir beurteilen müssen, ob etwas T.nil ist. Aber ich versuche immer noch, Ihre Frage zu beantworten. Ich hoffe, ich kann sie klar erklären.
In Bezug auf die Datenstruktur brauchen Sie sicherlich nicht Zeile 3, Sie müssen y.left.p auf jeden Fall anpassen.
Verwenden Sie für eine bestimmte Sprache jedoch nur C / C ++ als Beispiel. Wir verwenden NULL oder nullptr für das übergeordnete Element von leaf und root, was bedeutet, dass es nichts ist. Denken Sie nur daran, ist es notwendig, Speicher so viele wie Baumknoten zu kosten, um nutzlose Blätter zu retten? Natürlich nicht. Also markieren wir es als NULL-Zeiger, was nichts bedeutet, und alse hat kein p, links oder rechts.
Die Schlussfolgerung kommt, dass es von Ihrer Implementierung abhängt, ob Sie T.nil in Zeile 3 beurteilen sollten.
Ja, du kannst. danach
x.right = y.left
sind x.right und y.left vorübergehend dasselbe, also sind x.right.p und y.left.p genau dasselbe.Für Zeile 2 ~ 4 können Sie auch folgendermaßen schreiben:
quelle