Mir ist folgender Lemma aufgefallen
Lemma: Ein Rot-Schwarz-Baum T mit N inneren Knoten hat
höchstens die Höhe 2log2(N+1).
Warum die mal zwei? die Plus eins ist für die Wurzel oder? und die mal zwei dann weil wir ausgehen d von der Wurzel einen linken und einen rechten Teil Baum haben können?
Lemma: Ein Rot-Schwarz-Baum T mit N inneren Knoten hat
höchstens die Höhe 2log2(N+1).
Warum die mal zwei?
weil der baum nicht ganz balanciert sein muss. ein pfad von der wurzel bis zum blatt ist aber höchstens
zweimal so lang wie jeder andere. der baum ist damit immernoch balanciert - aber halt mit dem faktor zwei davor.
Mal eine ganz Blöde frage wen ich eine schlüssel folge in einen Rot-schwarzbaum einfügen will mit hilfe des Rb-insert(T,z) und es Rb-Insert-Fixup methoden .
Und ich fange dann mit dem ersten schlüssel an dann ist der erste Knoten ja die wurzel wo wird es in denn Beiden Methoden gesichert das der Knoten dann auch schwarz ist .
Also nach einfügen durch rb-insert ist der Knoten zunächst rot oder? und in Fixup Starte ich dann mit dem nil knoten? das kan doch nicht sein oder?
Oder gehe ich einfach immer davon aus das ich direkt mit zweio Knoten starte ?
Und ich fange dann mit dem ersten schlüssel an dann ist der erste Knoten ja die wurzel wo wird es in denn Beiden Methoden gesichert das der Knoten dann auch schwarz ist .
ganz unten im fixup wird die wurzel schwarz gefärbt.
Oder gehe ich einfach immer davon aus das ich direkt mit zweio Knoten starte ?
nein, ein baum kann auch leer sein oder einen knoten enthalten.
Geiles Applet für Rot-schwarz-Bäume
Hier finde ich kann man sehr gut nachvoll ziehen wie der Algo abläuft.
http://fbim.fh-regensburg.de/~saj39122/gikasch/start.html
Ich habe mal folgende Aufageb versucht es ist eine Aufageb von einem Ad übungs Blatt vom vor letzten Semester
Sortieren sie 1,12,3,18,24,10,26,6,14 in einen Rbt ein
Es klapt auch alles wunderbar doch beim einfügen der letzten zahl 14 wird es etwas Knifelig in der Muster lösung und auch das Apllet ergebn das der Knoten 18 rot ist bei mir ist er aber schwarz.
Ich sage mal die letzen schritte vielleicht entdeckt ja einer von euch mein fehler ich wäre sehr dankbar:)
also 14 wird eingefügt 14 ,12 und 6 sind Rot Ich färebe einfach die 12 und die 6 schwarz die 10 die vorher schwarz war wird rot .Damit ist der verstoss ein nach oben im Baum gerückt nun sind da die 10 rot geworden ist haben wir einen neuen verstoß
es wird eine right Rotation um 18 geamcht und jetzt färeben wir die 3 rot die vorher schwarz war(Wurzel) und wir färeben die 18 schwarz!!!(hier das laut algo richtig aber wen ich es mit dem Applet mache ist es nicht der fall , da wird die färbung nach der right rotaion einfach übersprungen?? warum) dan mache ich noch eine left rotation um 3 und färebe wieder
Der Baum den ich rasu habe der ist richtig bis auf die 18 die bei mir halt immernoch schwarz ist
aaaa wo ist mein Fehler[8]
aaaa wo ist mein Fehler[8]
da, wo die ! sind:
es wird eine right Rotation um 18 geamcht und jetzt färeben wir die 3 rot die vorher schwarz war(Wurzel) und wir färeben die 18 schwarz!!!
right-rotate: zeile 11, richtig
3 wird rot: zeile 13, richtig
18 wird schwarz: zeile 12, falsch
hier wird der parent von z schwarz. zu diesem zeitpunkt ist die 18 aber selbst z. schwarz wird also die 10, die nach dem rotate der parent von der 18 ist.
wiso ist 18 =z ?
10 ist doch z ich rotiere doch um 18 und rotieren tue ich mit p(z) also ist 18 p(z) und 3 ist P(p(z))
es wird alsodie 18 und die 3 gefärbt???dann danach ist 18 =z
wiso ist 18 =z ?
in zeile 10 vor dem rotate und den beiden farb-zuweisungen wird z <- p[z]. z ist vorher 10, danach 18.
mist das ich drehe durch [28]okay danke schonmal werde nochmal ein anders bsp durch gehen
@T must du auch Ad jetzt schreiben?
@T must du auch Ad jetzt schreiben?
nein, die erste klausur hat gereicht
@T glaube ich gerne ich habe Ad auch schon lange vor mir her geschoben [28]
Nochmal eine frage zu denn geliebten Rot-schwarz -Bäumen wen ich die aufgabe 1 vom Blatt 5 :
Fügen Sie folgende Zahlen in der angegebenen Reihenfolge in einen anfangs leeren Rot-Schwarz-
Baum ein: 24, 10, 1, 43, 12, 25, 36 und löschen sie 36
mache kriege ich nicht die richtige Lösung hin wenn ich 36 aus meinem Baum Lösche mit dem rb-Delete-Node Algo dann verschiebe ich ja quasie die daten aus dem knoten 43 einfach nur in denn Knoten wo vorher die 36 Stand .
Dann kommt ja in zeile 16 die abfrage ob y = schwarz das ist ja nicht der fall da y = Knoten mit 43 war und der war Rot also wird der alte Knoten einfach glöscht nun habe ich die Daten aus dem Knoten also die 43 einfach an die alte stelle von der 36 geschoben .Keine farebn verändert undnicht rb-delete-Fixup aufgerufen .
Aber wenn ich es mit dem Applet mache die haben eine ander Lösung ?
Hoffe jeamnd von euch kann mir helfen[2]
kannst du vielleicht mal einen screenshot vom applet hier reinstellen?
okay hier nach entfernen von 36
okay hier nach entfernen von 36
also ich sehe 'hier' nichts
ich glaube ich weiss wo mein fehler istnur findeich ihn im Code nicht ich habe als y immer noch denn Knoten mit denn Daten 43 aber y müste z sein damit das Rb-delete-fixup aufgerufen wird aber das pasiert ja nicht da diese zuweisung y<-z nur aus geführt wird wenn zeile 1 giltoder?
ich weiss zwar nicht so genau was du eigentlich getan hast, aber:
y müste z sein damit das Rb-delete-fixup aufgerufen wird aber das pasiert ja nicht da diese zuweisung y<-z nur aus geführt wird wenn zeile 1 giltoder?
zeile 1 im rb-delete-node wird genau dann aufgerufen wenn mindestens ein nachfolger von z nicht existiert (also nil ist). ansonsten wird y der knoten mit dem kleinsten key der grade noch grösser als der von z ist (hier also 43).
rb-delete-node wird unabhängig davon ob y <- z ausgefüht wird genau dann aufgerufen, wenn der gelöschte knoten (y) schwarz war.
ansonsten ist der baum kaum zu erkennen und viel interessanter wäre wie er vor dem löschen des knotens aussah.
Also so sah der Baum Vorher aus aber wenn ich die 36 lösche einfach nur nach dem Algo Rb-delete wird einfach nur die 36 gelöscht es wird nicht rb-delete fixup auf gerufen da meinte ich
Also in rb-delete habe ich dann y=43 der Knoten ist rot also wird rb-delete-fixup nicht aufgerufen.
Aber dann komme ich nicht zu dem selben Baum denn das Applet erzeugt .
Ich muss also irgendwo ein fehler gemacht ahebn weil x der zu Löschende Knoten doch schwarz ist und ich dachte immerwenn der zu löschende Knoten schwarz ist muss rb-delete-fixup ausgeführt werden
Ich muss also irgendwo ein fehler gemacht ahebn
nein hast du nicht. so wie ich das sehe geht der algorithmus vom applet ein ganz klein bischen anders vor als der aus der foliensammlung: er nimmt nicht den kleinsten nachfolger sondern den größten vorgänger. in diesem fall also die 25. es wird auch beim applet kein fixup ausgeführt.
hatet ihr bei der Lösung der Ü Blätterauch eine ander Lösung?Ud wurde sie als richtig an erkannt?[28]
Kann es wirklich sein das man durch löschen eines Knoten auf verschieden rot-schwarz-Bäume kommt?
Wenn man aus folgenden Daten einen Rot-schwarz-Baum erstelt 1,12,3,18,24,10,26,6,14
Und dann die 1 Löschen soll dann erhalte ich einen ganz andern Baum als das Applet und ich habe noch einen Lösung von einem Kumpel die auch wieder anders ist ?
Könnte einer von euch mal versuchen ddie aufgabe auch zu machen mit dennAlgos aus dem Skrit und sagen ob seien lösung auch wieder anders ist ?[28]
Kann es wirklich sein das man durch löschen eines Knoten auf verschieden rot-schwarz-Bäume kommt?
wenn man den gleichen algorithmus benutzt: nein
aber:
so wie ich das sehe geht der algorithmus vom applet ein ganz klein bischen anders vor als der aus der foliensammlung: er nimmt nicht den kleinsten nachfolger sondern den größten vorgänger.
