Rot-Schwarz-Bäume

[Mariexshhx]

Hallo ich habe hier die 7 eingefügt. Es dürfen ja aber keine zwei Knoten hintereinander rot sein laut Skript muss ich nun e schwarz und g rot und dann muss ich eine Rechtsrotation um g ausführen. Dann wird ja der Onkel hochgezoge, aber wie soll das gehen, wenn der Onkel nen Nil Knoten ist?

 

[Jw456]

Verstehe nicht wo dein Problem ist.

Was bedeuten die schwarzen Punkte?
Außer an der (1) rechts eine (2) kann kein Blatt mehr angehangen werden .

Wenn du zb etwas größer als 13 hinzufügen willst musst du umbauen.

 

[Jw456]

Dein Baum etspricht nicht den Regeln.

Jeder Knoten ist entweder rot oder schwarz
Jedes Blatt ist schwarz
Beide Nachfolger eines roten Knoten ist schwarz
Jeder einfache Weg von einem Knoten zu einem Blatt hat die gleiche Anzahl schwarzer Knoten.

Wird zb nicht eingehalten.
zB schon bei der (1) dort ist es einmal 2 und 1

 

[Mariexshhx]

Verstehe nicht wo dein Problem ist.

Was bedeuten die schwarzen Punkte?
Außer an der (1) rechts eine (2) kann kein Blatt mehr angehangen werden .

Wenn du zb etwas größer als 13 hinzufügen willst musst du umbauen.

das sind Nil-Knoten. Und sorry an meinem Baum fehlt bei der eins rechts die 2 dann passt es wieder

Und ja in dem monemt entspricht er nicht den Regeln aber zunächst einmal ist doch jeder neu eingefügte Knoten rot. Ich weiß nicht wie ich die Rechtsrotation um den Großvater machen soll...

Man soll folgendes tun: 3. Fall: Der Onkel u von v ist schwarz und v ist ein linkes Kind.
• Wir färben den Elternknoten e schwarz und den Großelterknoten g rot.
• Anschließend führen wir eine Rechtsrotation um den Großelterknoten g aus.

 

[Jw456]

Die 7 könnte um die Regeln einzuhalten an die (12) links als roter Knoten.
An die (1) muss rechtst die (2) dann würden die Regeln passen.

 

[Mariexshhx]

Die 7 könnte um die Regeln einzuhalten an die (12) links als roter Knoten.
An die (1) muss rechtst die (2) dann würden die Regeln passen.

aber die 7 ist doch nicht größer als die 11 die muss doch an die 8 oder nicht ?

 

[Jw456]

links kleiner als (12) und nicht kleiner als (5) Wurzel

wenn an 8 was ist , ist die schwarz höhe 4 nicht mehr gegeben.

 

[Mariexshhx]

links kleiner als (12) und nicht kleiner als (5) Wurzel

wenn an 8 was ist , ist die schwarz höhe 4 nicht mehr gegeben.

rechts von der 11 muss doch alles größer sein als die 11 wie soll dann die 7 rechts von der 11 sein

 

[Jw456]

Nicht rechts an der 12 sondern links an der 12.

 

[Jw456]

Du willst eine gewisse Balance des Baumes haben. Mal von dern Werten abgesehen und nur die Regeln fur die Balance betrachtet ist geht es nicht anders. Also musst du einiges umbauen, deine Wurzel wird dann auch nicht mehr 5 sein. Wenn du einen ausbalancierten Baum haben willst.