Löschalgorithmus für einen Rot Schwarz Baum

Question

Jungs Ich versuche Löschalgorithmus für einen Rot Schwarz Baum zu implementieren und ich habe Probleme mit Verständnis Linie drei dieses Algorithmus (aus einem Buch „Introduction to Algorithms“ second edition):

1, wenn links [z] = nil [T] oder rechts [z] = nil [T]
 2, dann y ? z
 3 else y ? TREE-SUCCESSOR (z)
 4, wenn links [y] ? nil [T]
 5 dann x ? links [y]
 6 sonst x ? rechts [y]
 7 p [x] ? p [y]
 8, wenn p [y] = nil [T]
 9 dann root [T] ? x
10 else if y = left [p [y]]
11 dann links [p [y]] ? x
12 sonst rechts [p [y]] ? x
13, wenn y 3 ? z
14 dann die Taste [z] ? Taste [y]
15 kopieren y Satellitendaten in z
16, wenn Farbe [y] = schwarz und 17 dann RB-DELETE-FIXUP (T, x)
18 return y

Zunächst einmal gibt es nirgendwo in diesem Buch erklärt, was der TREE-SUCCESSOR suppose ist aussehen (kein Algorithmus für die), aber ich fand diese Seite : und wenn ich füttern diesen Algorithmus Whit 11,2,1,7,5,8,14,15,4 und dann versuchen, 7 löschen es findet Vorgänger , aber wenn ich versuche, 11 zu löschen findet Nachfolger . Und das, was ich nicht verstehen kann. Warum manchmal dauert es Vorgänger und Nachfolger manchmal? Nach welchen Kriterien werden berücksichtigt, während diese Entscheidung? Eines Knotens Farbe?
Danke.

P. S. Ich weiß nicht recht auch verstehen, was es in Zeilennummer 13. Does geschrieben wird es bedeuten, dass, wenn y drei Farben hat (weder schwarz noch rot) oder etwas anderes?

Answer 1

Baum Nachfolger (als das Gegenteil von Bäumen Vorgänger [die in diesem Buch ist, ich glaube]) wird im Allgemeinen für binäre Suchbäume definiert als der Knoten mit der nächsthöheren Schlüssel. Wie es bestimmt sie von der Art (rot-schwarz in diesem Fall) und Im fast sicher Ihr Buch Blätter der Nachfolger Methode als eine Übung abhängt. (Ich erinnere mich, das Problem: P)

Answer 2

Ich glaube, Sie lesen CLRS 2nd edition.

TREE-SUCCESSOR wird in Kapitel 12 Abschnitt 2 eingeführt - "12.2 Querying binärer Suchbaum". Und im Gegensatz zu dem, was Jesse Naugher sagt, es ist nicht abhängig von der Art der binären Suchbäume.

Zeile 13 Sie zitiert ist ein Tippfehler. Es sollte sein "wenn y! = Z".

Answer 3

Sie können zu folgenden Code verweisen.

http://code.google.com/p/ CSTL / source / browse / src / c_rb.c