wir haben uns bisher hvl bäume und 234 bäume angeschaut hvl bäume sind binäres bäume bei den zwei drei vier bäumen haben wir verschiedene knoten typen mit zwei drei oder vier kindern wir wollen jetzt von den 234 bäumen wieder zurück zu binär bäumen kommen und gelangen zu zu den sogenannten rot-schwarz bäumen diese rot-schwarz bäume können wir aus den zwei drei vier bäumen konstruieren und genau das wollen wir machen bevor wir die rot schwarz bäume formal definieren dazu die folgende idee wir wollen die unterschiedlichen kundentypen zwei knoten drei knoten und vier knoten jetzt als teil bäume in
einem binär baum probieren damit das möglich wird brauchen wir ein zusätzliches merkmal pro knoten und wir nehmen dazu eine farbe wir unterscheiden zwischen zwei farben rot und schwarz 12 knoten soll abgebildet werden auf einen einzelnen schwarzen knoten im binären bei 1 3 knoten soll abgebildet werden auf einen teil baum mit einem schwarzen knoten als wurzel und einem roten knoten entweder als linkes oder als rechtes kind ich habe hier nur die eine möglichkeit die andere ist genauso gut wichtig ist dass andere kind hier um schwarz sein also es muss mit einem schwarzen knoten in der anderen
richtung weitergehen ansonsten könnten das ganze von dem letzten fall nicht unterscheiden vier knoten wird abgebildet auf einen teil baum mit einem schwarzen knoten als wurzel mit roten linken und rotem rechten kind wenn wir uns das jeweils überlegen dann sehen wir dass sich hier die roten und die schwarzen knoten einer bestimmten weise abwechseln müssen im ersten fall beim zwei knoten muss es unterhalb von diesem knoten auch wieder schwarz weitergehen ansonsten könnte ich den fall nicht unterscheiden vom 23 oder vom vier knoten und für den drei knoten am maschine weil es gesagt hier und hier muss es
mit einem schwarzen knoten weiter gehen ansonsten könnten mit diesem fall wiederum nicht unterscheiden von den vier knoten hier das in unsere drei fälle wie wir die knoten typen in 234 baum mit verzweigung grad 2 3 und 4 abbilden auf teil bäume in einem binär baum wo wir als zusätzliches merkmal noch farbe nämlich rot oder schwarz verbinden uns dazu ein beispiel an wir sehen hier einen 234 bau und wollen den jetzt als gut schwarz beim schreiben die wurzeln ist ein vier knoten mit den schluss und 7 14 und 16 wenn man das nach den regeln vom
leben schreiben bedeutet dass wir haben hier einen schwarzen knoten die 14 als wurzel links und rechts jeweils ein rotes kind nämlich die sieben und die 16 das linke kind von der wurzel ist wieder ein vier knoten genau das gleiche spiel da steht links von der 7 wir haben als wurzel von diesem teil baum in schwarzen knoten mit dem wirt 4 und links und rechts ihr essen roten knoten der 3 und der 5 das kind mitte links ist 20 bis 12 knoten die zwölf das portieren einzelner schwarzer knoten genauso mit rechts die 15 einzelne schwarze knoten
und schließlich haben auch hier den drei knoten mit der 17 und der 18 damit zwei möglichkeiten ich kann entweder die 17 oder die 18 als wurzel von diesem teil baum nehmen versuchen es erst mit 17 dann schaut das ganze so aus 17 schwarz und die 18 ist ein rotes kind das in dem fall natürlich auf der rechten seite wir hätten es auch andersrum machen können dass wir hier oben nicht die 17 die 18 genommen hätten also 18 ein schwarzes kind und dann wieder ins schwarze würze von dem teil bank und dann wird die 17 als
kind auf der linken seite geblieben als rotes kind in dem fall schau mal was richtig gemacht haben das ist unser 234 baum und hier der entsprechende bierbaum rot schwarz eingefärbt tatsächlich unser rot-schwarz baum was ist nun ein rot schwarzbau wir definieren den rot-schwarz bau auf englisch red black trieb als einen binären such bau in dem jedem knoten noch einfach attribut zugeordnet ist so das gilt erstens jeder knoten ist entweder rot oder schwarz zweitens die wurzel ist schwarz drittens alle blätter sind schwarz vierter beide kinder eines roten knotens sind schwarz und fünftens jeder tat von einem
gegebenen knoten zu einem erreichbaren blatt enthält die selbe anzahl schwarze knoten schauen wir uns diese definition noch mal an der erste punkt ist klar wir färben die knoten ein entweder rot oder schwarz der zweite punkt die wurzel ist schwarz ist tatsächlich nicht unbedingt nötig wir werden sehen das wird die wurzel immer ohne probleme umfärben kann sollte die ruhr zur rot sein können sie ohne irgendwelche probleme ohne irgendwas weitermachen zu müssen einfach schwarz werden der dritte punkt den muss man gleich noch erklären alle blätter sind schwarz wenn man noch mal zurück denken an unser beispiel dann
sehen wir nie das stimmt hier nicht weil 35 17 das sind alles blätter wir denken uns dass so das wir annehmen alle knoten mit einem schlüssel sind interne knoten und die eigentlichen blätter das sind so damit noten hilfs knoten ohne werte ohne schlüssel und die haben nach definition die farbe schwarz auf die art und weise sind alle blätter tatsächlich schwarz wer kann das auch noch brauchen denn wir wären fall unterscheidungen haben bezüglich bestimmten knoten die vielleicht gar nicht existieren im sinn von dass es an der stelle gar keinen knoten mit einem schlüssel gibt in dem
fall halten wir uns immer an diese damit knoten hier diese damit noten braucht man in der implementierung tatsächlich nicht das reicht wenn man sie uns denken es reicht wenn wir uns denken wenn irgendwo ein kind fehlt steht dafür ein schwarzer knoten beide kinder eines roten knotens sind schwarz die regel ist tatsächlich wichtig in der konsequenz bedeutet das nämlich dass sich rote und schwarze knoten immer abwechseln müssen und sich dabei in einer art und weise abwechseln das auf einen schwarzen knoten zwar wieder ein schwarzer knoten folgen darf das auf einen roten knoten in einem pfad von
der wurzel zu einem blatt aber nur ein roter knoten folgen darf also es dürfen beliebig viele schwarze knoten auf einem pfad im baum nach unten aufeinanderfolgen aber es dürfen nie zwei rote knoten nacheinander stehen es muss immer mindestens ein schwarze knoten dazwischen stehen die fünf der eigenschaft ergibt sich eigentlich aus den anderen müssten sie an der stelle zeigen dass du mir hier nicht jeder part von einem gegebenen knoten zu dem erreichbaren blatt enthält die selbe anzahl schwarzer knoten schauen uns das gerade an unseren beispiel an wenn wir hier von der wurzel zu dem blatt gehen
mit den blättern meiner wieder unsere damit knoten und die schwarzen knoten zählen sind das hier 123 123 123 und so weiter auch hier zb 123 123 123 das heißt wir haben in diesem beispiel tatsächlich immer die gleiche anzahl schwarze knoten auf dem pfad von der wurzel zu dem blatt und wie gesagt mit blättern meine ich die da oben diese anzahl von schwarzen knoten die wird manchmal auch schwarz höhe genannt und zusammen mit der eigenschaft das rote knoten nicht aufeinander folgen dürfen ist diese schwarz höhe tatsächlich ja ein sinnvolles maß für die höhe des baums denn
die tatsächliche höhe des baums kann höchstens doppelt so hoch sein weil wir zwischen je zwei schwarze knoten höchstens einen roten knoten noch dazwischen fügen können dürfen ja nicht zwei rote knoten aufeinanderfolgen diese überlegungen führen uns aber schon zu eigenschaften von rot-schwarz baum insbesondere zu der eigenschaft dass die höhe immer beschränkt ist im logarithmisch der anzahl der einträge im baum also die höhe ist von login wenn die anzahl einträge ist der werden das nicht formal zeigen wir müssen das auch gar nicht weil wir haben uns ja schon überlegt dass die 234 bäume in ihrer höhe perfekt
ausbalanciert sind das allerdings in den verschiedenen teil bäumen unterschiedlich viele schlüssel stehen können weil wir ja unterschiedliche knoten typen zwei drei und vier knoten haben dass diese balance aber nie über kippen kann weil der verzweigung grad begrenztes wenn wir jetzt argumentieren dass wir rot-schwarz bäume aus den zwei drei vier bäumen konstruieren können oder das 234 bäume auf rot-schwarz bilder auf rot-schwarz bei mir abgebildet werden können und umgekehrt dass die beiden also wie so oft zueinander sind dann haben wir damit auch ein argument das die rot schwarz bäume als binär bäume ausbalanciert sein müssen in einem
sim dass die höhe eben auch nur logarithmisch mit der anzahl einträge wachsen kann wir brauchen also gar keinen formalen beweis zu den rot schwarz bäumen mehr antreten wenn wir uns an die 234 bäume halten nach konstruktion gezeigt haben dass sie immer ausgeglichen sind weil sie ja immer nur dann um 1 wachsen und der höhe wenn die wurzel getan zurück zu unserem beispiel hier nochmal der baum mit dem dummy knoten jetzt noch mal hin schön so wie ich sie gerade eben auch skizziert habe und noch weil die wichtigen eigenschaften also für jeden roten knoten gilt dass
beide kinder schwarz sein müssen damit es umgekehrt auch der vater von den roten knoten schwarz sein weil sonst wäre wäre dessen kind rot und damit können zwei rote knoten auf dem pfad von der würze zu irgendeinem anderen knoten nie aufeinander folgen das ist das balance kriterium für den brot schwarzbau und wie gesagt eher überlegen uns das einfach anhand der abbildung auf den 234 bauen wir wollen aber jetzt nicht zwei drei vier bäume bauen um rot-schwarz bäume zu erzeugen sondern wir wollen rot schwarz räume tatsächlich direkt als binär bäume erzeugen das heißt wir werden wieder regeln
finden zum einfügen und zum umstrukturieren und wir strukturieren jetzt immer um wenn die entsprechenden eigenschaften dass rot-schwarz baums verletzt sind wir machen dazu trotzdem nicht einmal zur anschauung den umweg über die 234 boyle und wir schauen uns jeweils die lokale situation an vor sich die ausschnitte auf den folgenden folien sind für sich keine gültigen rot-schwarz bäume sondern immer nur ausschnitte daraus wenn wir in rot-schwarz baum einfügen wollen dann können wir uns das genau so vorstellen wie das einfügen in 234 bäumen für 234 bäume wissmann ihnen zwei knoten einfügen ergibt einen drei knoten in drei knoten
einer gibt in vier knoten in den vier knoten einfügen bedeutet ich brauche diese kombination aus split und mensch das muss ich jetzt übertragen auf einmal rotationen dass es die eine operation die wahrheit aber dadurch dass wir den knoten jetzt noch fahren gegeben haben jeder knoten es entweder rot oder schwarz haben auch den anderen freiheitsgrad wir können die knoten auch umfärben das einfügen in zwei knoten ist jetzt einfach aus dem zwei knoten wird um drei knoten es kommt einfach ein roter knoten noch als kind runter in den zwei knoten in den drei knoten entschuldigung nochmal einfügen
dann würden vier knoten draus es kommt einfach auch noch mal ein rotes kind darunter die spannende operation ist jetzt tatsächlich der split also was passiert wenn ich bald nach der erfolglosen suche im 234 baum in einen vier knoten einfüge und mit das als rot-schwarz baumann schauen wir müssen also den split mit hilfe von rotationen oder restrukturierung und zusätzlich noch einem umfärben modellieren genau wie im 234 baum kann das entweder bottom up oder top down geschehen wir schauen uns hier nur die bottom up variante an wir werden nicht weiter erwähnen dass es beide möglichkeiten natürlich auch
für den rot schwarz raum gibt der erste fall ist nun wir möchten einen vier knoten einfügen man braucht also den split und über diesen vier knoten habe ich als eltern knoten einen zwei gruppen es ist egal ob der vier knoten links wie hier oder rechts hängt wenn man uns das ganze in 234 baumann schauen dann ist klar der mittlere eintrag hier der schlüssel b wird hochgezogen und es gibt sich ergibt sich dieses bild nach dem split wenn man das ganz übersetzen in einen rot schwarz baum dann haben wir hier den zwei knoten de und hier
unten als linkes kind den teil baum der diesen vier knoten repräsentiert schwarze kurze vom teil baum mit b links und rechts jeweils rot a und c wir machen jetzt folgendes den split hier von hier nach da das kennen wir schon von hier nach da das macht man einfach durch unsere regeln liefert 234 baum auf den rot schwarz baum abgebildet und stadt dass wir von hier nach hier gehen überlegen wir uns jetzt einfach den weg von hier nach da und wieder runter also wir schauen uns diesen 234 baum nach dem split an und schon angst wie
uns wir schauen uns an wie der als rot-schwarz baum aussehen würde wir haben als wurzel jetzt einen drei knoten mit b und d als schlüssel diesen drei knoten lassen hier nach links über hingen dhd ist die schwarzwurzel das linke kind ist ein roter knoten mit b diese blauen linien waren hier jeweils die knoten voneinander abtrennen so an diesen drei knoten habe ich zwei kinder aus dem split noch das eine ist das andere ist sie beides sind zwei knoten also beides in einzelne schwarze knoten in meinem rot schwarz blau das heißt wir sind einmal von hier
nach da gegangen von hier nach hiervon hiernach hier und jetzt kann man daraus den weg von hier nach hier uns erschließen das heißt uns jetzt anschauen was passiert denn in rot-schwarz bauen ohne dass ich mir den 234 baum noch mal anschauen und wenn wir hier links und rechts miteinander vergleicht dann sieht man es ist eigentlich fast nichts passiert es habe lediglich ein paar knoten die farbe gewechselt also dieses umstrukturieren durch den split im 234 baum wird aus dem vier knoten 22 knoten und der eltern knoten 12 knoten wird zum drei knoten ist im rot schwarz
vom einfach ein umfärben der knoten a und c herrn schwarz und rot eigentlich ganz einfach der nächste fall unser vier knoten den wir splitten wollen hängt unter einem drei knoten als eltern kunden dabei kann er entweder links oder rechts aber nicht in der mitte hängen das wird vielleicht der dritte fall sein schauen wir uns an was passiert mit dem split wandert der schlüssel b in den eltern knoten ich bekomme also als eltern knoten in vier knoten jetzt mit den schlüsseln b d und e und als kinder bleiben übrig und c jeweils 22 knoten es ist
natürlich wie immer so dass hier noch teil bäume dranhängen können die zimmer einfach mit wir schauen es tatsächlich nur diesen lokalen ausschnitt an so jetzt schauen wir wieder wie würde diese konfiguration allem rot-schwarz baum aussehen wir haben einmal den drei knoten den modell immer hier mit einem schwarzen knoten und einem roten kind in dem fall dass man wieder nach links hängen also dieser teil entspricht diesen drei knoten und der vier knoten hier unten ist wie gerade eben auch die konfiguration mit b als schwarze wurzel a und c links und rechts als rote kinder das gleiche
machen wir hier nach dem split schauen uns aus als schauen uns an wie das in rot-schwarz baum aussieht wir haben jetzt hier oben als wurzel einen vier knoten die ist der mittlere schlüssel dementsprechend hier die schwarzwurzel von dem teil baum b und d stehen als rote knoten und linkes rechtes kind also dieser teil hier den ich hier abgetrennt hat entspricht dem vier knoten und a und c 2 10 2 knoten dementsprechend hier im gut schwarzbau zwei schwarze knoten so jetzt ist es nicht mehr ganz so einfach wie gerade heben wir sehen einige knoten haben die
farbe gewechselt und sie waren vorher rot und sentiert schwarz b war schwarz und ist jetzt rot war gut und es jetzt schwarz und er hat auch noch mal die farbe gewechselt also alles hat munter die farbe gewechselt aber auch die struktur von diesem teil baum hat sich verändert wir haben nämlich das ganze nach rechts rotiert wir haben dass er hier so herunter geklappt und wenn wir uns überlegen welche der rotationen das war dann ist das eine einfach rotation nach rechts also in dem fall vier knoten hängt links unter den drei knoten müssen wir um färben
und einmal nach rechts rotieren hätte man den vier knoten nicht als linkes kind sondern als rechtes kind würden wir um färben und nach links rob tieren also dann würde das hier nicht nach links und rechts umhängen und die rotation würde genau in die andere richtung gehen fehlt ist der fall dass der vier knoten jetzt mittig unter dem drei knoten hängt schauen uns an wie das aussieht wenn wir hier splitten ziehen dass sie nach oben es ergibt sich als eltern knoten wieder an vier knoten und die beiden zwei knoten mit b und d als schlüsseln die
übrig bleiben hängen jetzt in der mitte zwischen a und c bzw zwischen c und e als kind mit links und mit rechts wenn uns das in rot-schwarz baumann schauen dann haben wir hier wieder unseren zwei knoten mit a und e als schlüssel wir lassen ihn wieder nach links hängen das heißt erste schwarze und dann links das rote a unser vier knoten hängt oder sieht aus wie gerade eben auch hängt aber jetzt auf der rechten seite machen dass gleich wieder auf der anderen seite wir gehen von 234 baum zum rot-schwarz baum da haben wir jetzt als
wurzel von unserem teil baum nennen vier knoten das heißt schwarzes zsh und als linkes und rechtes kind hat dass es diese vier knoten hier oben und b und d die beiden kinder nach dem split das sind mit der zwei knoten dementsprechend einzelne schwarze knoten in rot-schwarz bau und die hängen diesmal rechts von aa und links von e und jetzt überlegen uns wieder was da eigentlich passiert ist wir haben auch wieder umgefärbt b und d die farbe gewechselt von rot nach schwarz die farbe gewechselt von schwarz nachrodt und sie haben ihre farbe behalten aber auch die
struktur von unserem baum hat sich wieder geändert ganz kurz überlegen der baum hier ist linkslastig aber in dem zickzack der linke teil warum ist rechtslastig zumindest wenn wir uns diesen ausschnitt anschauen wir haben hier also eine zickzack konfiguration und dementsprechend können wir schon erraten was hier passiert ist wir haben mit doppel rotation angewendet also erst hier einmal nach links das herunter geklappt und das c an diese position und dann nach rechts dass er nach unten geklappt als wir haben erst nach links und dann nach rechts rotiert um diese konzentration zu halten dementsprechend diesen dritten fall
können wir abbilden auf umfärben und doppel rotation noch mein tipp das gilt für die hvl bäume genauso wie die für die rot schwarz bäume für diese überlegung aber auch nachher wenn man die rot schwarz bäume konstruieren oder das einfügen üben wenn man zwischendurch nicht wissen wo man die kinder nach dem rotieren wieder einfügen wir können entweder uns die folie anschauen wo die teile bäume die null bis t3 zu liegen kommen der einfache trick ist aber immer dass wir uns merken der in oder durchlauf muss der gleiche bleibt und damit ergibt sich immer die richtige position
wo ich die kinder tatsächlich ein für gerade hier in oder alles was links von astana dann bädern c dann die dann vorsicht ich hätte das ihr hier geometrisch weiter nach rechts schieben müssen also dass die ist hatte ich noch links von also man sieht hier in der darstellung nicht gut ich hab ein bisschen platz sparen müssen und auf der rechten seite muss ich natürlich wieder das gleiche haben hier sieht das geometrische ein bisschen schöner alles was links von hsbc die alles was rechts von ehe ist und alles zwischen a und b alles zwischen b und
c zwischen c und d zwischen den habe ich unter schlagen kann also wenn wir das im hinterkopf behalten dann ist es sehr leicht die rotationen mit papier und stift auch durchzuführen wären das implementieren wollen dann überlegt was uns einmal mit papier und stift und danach ist es nicht schwer das in rot zu fassen tatsächlich implementiert niemand rot-schwarz bäume über den umweg von zwei drei vier bäumen mir ging es hier nur darum noch einmal zu zeigen dass das was uns bei dem zwei drei vier bäumen als split und münchen belegt haben sich abbilden lässt auf rotationen
und umfärben im brot schwarzbau tatsächlich unterscheidet man in der praxis einfach eigentlich einfache fälle man muss nur aufpassen dass man alle fälle richtig zusammenbekommt und ich habe mir hier eine übersicht aus der wikipedia ausgeborgt da ist muss schauen ob beim deutschen und beim englischen eintrag auch eine recht schöne darstellung mit jeweils code snippets es ist sehr gut und kein java code für die einzelnen fälle man kann diesen code auch recht schön lesen und dabei zumindest eine ahnung bekommen dass das ganze gar nicht so kompliziert ist die fall unterscheidungen werden immer anhand der farben durchgeführt wir
überlegen also nicht wo ist unser mann in vier knoten wo ist der an welcher position wie sieht der eltern knoten aus sondern alle fall unterscheidungen laufen ganz einfach über die farben von den knoten dabei ist eine wichtige regel jeder knoten den wir neu einfügen ist ein guter grund also wir machen eine erfolglose suche fügen dann einen neuen knoten ein und dieser neue knoten ist gut so diesen neuen knoten geben hier einen namen wie neu oder new wir nehmen noch ein paar andere namen und zwar für parent dass es der eltern knoten von unseren neu eingefügten
knoten g für grant herren dass es der großeltern knoten zu unseren neu eingefügten knoten und schließlich für anke oder onkel knoten wer will auch tante knoten es ist egal das ist einfach der bruder oder geschwister knoten von den eltern knoten oder das andere kind vom großvater ring kompliziert ist aber gleich ganz einfach wenn man auf die bilder schon so und jetzt haben eine kaskade von fällen die ja nach und nach komplizierter werden aber nie wirklich kompliziert zu implementieren sind okay erster fall unser neuer knoten ist der wurzel knoten also haben in den leeren baum eingefügt
die regel sagt die wurzel ist immer gut die eu wird es immer schwarz dementsprechend wir fügen den roten knoten ein wir färben einfach um und behalten eine schwarze wurzeln zweiter fall wir haben den roten knoten eingefügt und sehen das der eltern knoten p schwarzes dann müssen wir nicht weitermachen warum auf den schwarzen knoten darf im rother knoten folgen dass es kein problem probleme gibt es immer dann wenn zwei rote knoten auf einem pfad von der würze nach unten nacheinander auftauchen das darf nicht passieren nachdem wir den roten knoten einfügen kann es aber passieren wenn das
wenn der blood knoten an dem er einfügen schon rot war und darüber verzweigen jetzt die restlichen fälle also wie ließ man das ganze wir haben hier einen neuen knoten eingefügt über einem eltern knoten der ebenfalls rotes so wir haben also hier eine rot rot verletzung in rot-schwarz baum und müssen deswegen entweder umfärben umwerben und restrukturieren in dem fall ist es einfach wir färben einfach um was macht diesen fall aus wir schauen uns immer wie eine rot rot verletzungen haben den konkel knoten an in dem fall ist der onkel knoten rot das heißt hier auf dieser
ebene sind sowohl vater als auch onkel knoten roth wir werden die einfach um und das ist genau das was hier passiert wir müssen einfach nur schwarz machen im gegenzug wird der großeltern knoten rot eingefärbt eigentlich ganz einfach kompliziert oder schwieriger wird das dadurch dass wenn wir den großeltern knoten roth machen dann kann es natürlich wieder sein dass hier ein ur großeltern knoten trüber ist der auch rotes wenn das der fall ist dann muss man das ganze weg kursiv nach oben auch wieder reparieren das heißt dieses umfärben sieht sich regressiv nach oben wenn wir den großeltern
knoten umfärben von schwarz auf rot dann kann eine ebene höher das gleiche wieder passieren dass wir die rot-rot verletzung haben und wir müssen wieder über diese einzelnen fällig sodass meine erste fall der war insofern einfach dass wir nur um färben müssen der zweite fall wir machen den sprung hier nach ganz rechts wir haben neun knoten eingefügt der eltern knoten ist rot aber der onkel knoten ist diesmal schwarz in dem fall wird rotiert und ungefragt also in dem fall hatte eine rotation hier nach rechts das rote p wird die neue schwarze wurzeln bleibt ein roter knoten
g wird in dem fall das rechte kind und auch wieder rot und ansonsten bleibt alles wie es ist ich habe hier die fälle das was links über hängt und wir nach rechts rotieren das ganze spiegelverkehrt wer dann ja der nächste der vierte bzw der fünfte fall wenn man hier von drei bis fünf durchnummerieren das war der hier einfach rotation in dem fall nach rechts warum habe ich die mitte übersprungen weil in dieser konfiguration hier müssen wir auch umstrukturieren auch hier ist der punkt knoten schwarz wir färben um und rotieren in dem fall müssen wir aber
zweimal pro tieren einmal nach links als wir haben hier immer so wilden zickzack konfiguration wenn man gehe von den beiden roten knoten nach oben vom neuen knoten zum vater dann zum großvater einmal zig und einmal zeigt wie rotieren einmal nach links dann haben wir wieder eine in dem fall links links konfiguration dieser baum hier ist der gleiche wie hier oben und wir machen auch einfach nochmal das gleiche wie rotierende noch nach rechts also auf der linken seite nur umwerben vorsicht das zieht sich repressiv nach oben durch auf der rechten seite die einfach rotation und in
der mitte die doppel rotation einmal in die eine richtung und dann sind wir dem fall von einfach rotation und es geht weiter in die andere richtung genauso kann ich übrigens auch implementieren ich muss die doppel rotation nicht als ein als einzelne operation implementieren sondern ich rotieren in die eine richtung und begebe mich dann in den anderen fall und rotieren noch mal in die andere richtung und habe das ganze mit relativ wenig brot erschlagen wie gesagt es ist in den wikipedia-artikel ganz schön dargestellt allerdings nicht sondern hinziehen tatsächlich würde ich euch gar nicht warten die fälle
so abzuhandeln wie hier es sei denn ihr wollt wirklich eine effiziente schnelle implementierung von rot-schwarz können dann ist das wahrscheinlich die variante der wahl wenn es nur darum geht das erst mal zu verstehen oder rot-schwarz wollen wir möglichst einfach zu implementieren oder mit papier und stift zu arbeiten dann finde ich viel einfacher statt rotationen wieder dieses kleinod restructuring zu verwenden also lokal zu restrukturieren in dem wir drei in dem pfad von unten richtung wurzel aufeinanderfolgende knoten betrachten und in die gewünschte in anführungszeichen reihenfolge bringen auf die art und weise kann ich den gleichen algorithmus sehr
viel einfacher beschreiben es geht wieder ganz einfach los genau wie eben wir fügen den neuen knoten als blatt knoten ein und dieser neue knoten ist rot wir fügen immer einen roten knoten 1 dann schauen wir ob wir eine rot rot verletzung haben das heißt ob der eltern knoten dieses neuen knoten also da wo wir eingefügt haben auch rotes dann haben wir ne rot-rot verletzung und müssen entweder restrukturieren oder um fern ganz wichtig wenn wir umfärben dann kann es weiter oben auch wieder rot rot verletzungen geben wir müssen wenn man umfärben das ganze regressiv betrachten genauso
wie eben auch wenn man das ganze mit rotationen machen so warum jetzt diese restrukturierung stadt rotationen weil ich damit im prinzip alle fälle ganz einfach beschreiben kann der erste fall wir haben eine rot rot verletzung einen von diesen vier fällen in allen fällen ist gleich das wenn das der neue knoten es der hilter knoten großeltern knoten und hier der onkel knoten in allen fällen ist gleich dass der onkel knoten schwarzes und ich finde das klingt so lustig das kann man sich auch ganz einfach merkt also eine onkels rot oder der onkel schwarz für den fall
der onkel ist schwarz restrukturieren wir das heißt wir schauen uns diese drei knoten an wo es die rot-rot verletzung gegeben hat und bringen die in die in oder reihenfolge und bauen daraus den baum gegen das sehen wollen der lokale ausgeglichen ist ganz einfach so zweiter fall der onkel knoten ist rot das hier ist unser onkel knoten in dem fall wird nicht restrukturiert sondern es wird umgefärbt also der vater und der onkel bernd schwarz und der großeltern knoten wird gut 1 gehört und jetzt kann es eben passieren wenn der eltern knoten hier wiederholt ist dass sich
das ganze weg kursiv nach oben zieht zweiter fall ist noch einfacher weil wir nur um färben müssen umfärben bedeutet erstmal nicht mehr als dass wir ein attribut pro knoten ändern von rot auf schwarz von schwarz auf rot wird wenn der implementierung natürlich durch folien einfach nur darstellen schwarz falls road zb allerdings müssen wir aufpassen dass wir rot-rot verletzung eine stufe höher dann auch noch überprüfen müssen und das so lange ist es keine rot rot verletzungen mehr gibt restrukturierung ist auch nicht schwer weil da alle fälle in einen überführen das heißt wir müssen uns nicht mit
einfach rotation links rechts doppel rotation links rechts rechts links auseinandersetzen sondern wir haben alles in einem algorithmus und die farben vorher und nachher sind auch klar genau so mache ich das in der beispiel implementierung von einem rot schwarz baum die entsprechende klasse heißt red flag tree die erweitert wieder die klasse beine research tree und verwendet dieses lokale restrukturieren die eigentliche arbeit macht die methode gravity devil red das heißt die prüft ob es rot-rot verletzung gegeben hat wendet dann den ersten oder den zweiten fall an und sorgt dafür dass regressiv nach oben richtung wird so weiter
überprüft wird ob es noch mal eine rot rot verletzung gibt und wenn ja passiert das ganze eben noch mal bevor wir uns ein beispiel anschauen noch ein paar bemerkungen es gibt eine ganz interessante erweiterung trifft es nicht ganz von robert zoellick wer in den büchern von selbst liest die rot schwarz bäume sind dort sehr schön dargestellt allerdings ein kleines bisschen anders sedgwick fertig die knoten sondern die kanten ein es ist im prinzip aber das gleiche in gewisser weise ist das mit den kranken vielleicht sogar schüler die meisten leute haben allerdings die knoten ein deswegen bleibe
ich dabei was hat es mit dieser erweiterung auf sich selbst führt sogenannte left leg trees ein um das bedeutet nichts anderes als dass die darstellung von einem zwei knoten er von einem dreieck noten entschuldigung im 234 baum immer diese variante ist und dass diese hier nicht vorkommt also unser baum lehnt sich immer ihr nach links das heißt einen freiheitsgrad dem er bei den rot schwarz räume noch haben nämlich wie setzen wir drei knoten aus dem 23.4 baum um der wird da eliminiert das hat ein paar vorteile beim einfügen vor sich das hat ein paar nachteile
beim löschen aber es macht den algorithmus zum einfügen noch mal einfacher und eleganter ich lade euch ein das tatsächlich nachzulesen ihr findet auf den folien den link zum original artikel den kann man sich einfach runterladen der ist gar nicht lang der schön geschrieben mit java code noch an optiert also habt im prinzip eine komplette implementierung noch mit dabei und es ist effizienter als das restrukturieren in gewisser art und weise und gleichzeitig sieht man dass es auch nicht wirklich schwer also es noch eine andere darstellung als meine beispiele die es wirklich wert ist sich anzuschauen zurück
zu unseren beispielen ihr findet ein beispiel red black tricks ampel womit ihr innen rot schwarz baum interaktiv einfügen könnt ihr könnt die zwischenschritte immer sehen und mit verfolgen also einmal was wie schaut der baum aus nachdem ich den roten knoten eingefügt habe und wie sieht er aus nachdem ich umgefärbt und restrukturiert hat ich verwende wie gesagt diese methode red devil red die wiederum auf dem kleinod restructuring von goodrich und thomas kufus die benutzten wesentlichen ja auch die gleiche nomenklatur habe ich dort übernommen geklaut ihr findet wie gesagt diese lässt linie mit black dress als eine
alternative an die wir vor allem auch leicht rankommt ja das pdf viel schneller herunter geladen als das buch gekauft hier findet fragmente in den wikipedia-artikel die sind auch ganz schön zu lesen allerdings eben kein java code und ihr findet die klassische implementierung als alternative auch noch mal im buch von sagt und sattler klassisch bedeutet hier wir färben um und rotieren zu guter letzt wir haben jetzt sowohl für apfelbäume als auch für rot-schwarz bäume und für die 32 34 bäume implementierungen vl und rot-schwarz sind binär bäume also erweitern beide beine research die lade euch ein beides
mal zu vergleichen und zwar durchaus auch für größere bäume also für bäume wo mehr passiert als wir dass wir jetzt zehn einträge einfügen so was könnte ohne probleme mit den beispielen auch machen schaut euch dabei auch tatsächlich mal an was passierten in den schlechten fällen also wenn meine schlüsse der sortierten reihenfolge kommen wie sie dann der apfelbaum wie sie dann der rot schwarz baum aus wenn man die beiden vergleichen dann gilt sowohl für den vfl als auch für den rot schwarz baum einmal dass ein bau mit den einträgen speicherplatz eu von n braucht das ist
klar jeden eintrag speichere ich in den knoten da steht noch ein bisschen zusatzinformation die höhe für die balance oder die farbe für den rot schwarz baum die verweise auf links rechtes kind gegebenenfalls auf den eltern knoten aber es ist nur eine konstante anzahl von dingen die wir mehr speicher müssen also insgesamt an speicherplatz linear in der anzahl einträge die suche sahin logarithmische zeit denn durch die balance kriterien die wir nach jedem einfügen wieder forcieren ist die höhe effektiv auf von login beschränkt dabei habe auch gesehen dass vl und rot-schwarz ganz unterschiedliche balance kriterien verwenden ihr
habt gesagt auch varell finde ich intuitiver weil es direkt mit höhe zu tun hat bei rot-schwarz muss man sich erst überlegen warum dieses einfärben und die regeln fürs einfügen tatsächlich für eine balance sollten das ist ein bisschen mein auch schwieriger weil es nicht direkt abbildbar ist auf die höhe von dem bauunternehmen den umweg über diese schwarz höhe also die anzahl der schwarzen knoten in einem pfad von der wurzel zu dem blatt für beide bäume gilt dass sie dass es auch einen schlechtesten fall gibt in diesem schlechtesten fall entarten sie aber nicht zur liste aber sie
hängen trotzdem in die eine oder in die andere richtung über der schlechteste fall ist jeweils einfügen von der sortierten oder invers sortierten folge er sind artet nicht tatsächlich sondern der baum und über bedeutet für die suche brauche ich dann ja jeweils den faktor länger aber die suche bleibt trotzdem in loccum beschränkt es gibt nur pfade die sind vielleicht doppelt so lang wie andere das einfügen geht auch in ufern locken denn zum einfügen muss ich einmal suchen brauchen erfolglose suche danach muss ich restrukturieren dabei kann beim fvl baum kann es beim fvl baum passieren dass ich
ein stückchen weiter nach oben muss bis ich feststellen wo die auf vl eigenschaft verletzt ist ich muss allerdings nie weiter als login träge hoch beim rot schwarzbau sich unmittelbar sofort dass es eine rot rot verletzten gegeben hat allerdings muss ich auch regressiv nach oben hoch weil sie sein kann durch das durch das umfärben sich wieder eine rot rot verletzung ergeben hat allerdings ist es so dass ich im mittel tatsächlich nur einmal restrukturieren muss beim rot-schwarz bauen das ist übrigens auch ein grund warum die rot schwarz bäume beim einfügen in der praxis bevorzugt werden oder warum
die rot schwarze mann der praxis bevorzugt werden weil sie beim einfügen einen kleinen vorteil haben für beide gilt auch das haben wir hier nicht angeschaut das löschen in ufernähe von le pen möglich ist zum löschen braucht eine erfolgreiche suche und danach mussten wir auch wieder umstrukturieren tatsächlich ist das löschen schon deutlich schwieriger als das einfügen die grundideen dabei bleiben aber die gleichen also es ist bis in unübersichtlicher von der anzahl fälle die wir unterscheiden müssen aber wir lernen mich wirklich was neues wenn man das einfügen verstanden haben reicht mir das hier für die vorlesung dann
ist es auch schwierig sich das löschen noch anzulesen anzeigen und zu implementieren manchmal liest man das einfügen und löschen von 1 möglich ist wenn ihr das liest dann ist dabei immer gemeint dass die erfolglose suche nicht mitgezählt wird weil für diese erfolglose suche brauche ich auf jeden fall den aufwand von ufern locken ich musste erst mal bis zu dem blatt knoten kommen mir gesagt beim fvl baum kann sein dass die hvl eigenschaft irgendwoher verletzt wurde in mittel schenkt sich das aber trotzdem weder für vl noch für rot-schwarz räume viel ich muss nicht besonders weit aufsteigen
für die restrukturierung mal die beiden bäume jetzt vergleichen ohne dass man noch mal nachrechnen dann haben wir für den evl baum eine formel wir können nachschlagen für den rot schwarzen hummer eine formel für die höhe von dem baum mit in einträgen und wir sehen beide die anzahl einträge davon den logarithmen dem von zwei euro gar it muss unterscheiden tun sich die beiden im wesentlichen durch die konstante beim rot-schwarz bauen hab ich ne 2 stehen für mich beim vfb wohl weniger als anderthalb stehen habt also die suchen in rot-schwarz baum sind entschuldigung israel baum sind tick
schneller als im rot schwarz baum weil er weil ich annehmen kann dass er bei gleich vielen einträgen bisschen niedriger ist geschenkt sich tatsächlich aber nicht viel gut alles was hier noch steht haben wir im prinzip schon gesagt hier noch ein kurzer überblick zu bestehenden implementierungen vl bäume und rot-schwarz bäume werden ja mehr oder weniger in der praxis verwendet die hvl bäume findet er hauptsächlich in der literatur zu balancierten bäumen es gibt mit sicherheit auch jede menge implementierungen in der praxis werden trotzdem die rot schwarz bäume hier bevorzugt was kann ich jetzt mit diesen binären zu
bäumen machen ich kann abstrakte datentypen wie set oder web definieren genau das passiert auch zb in den cover collections die tri set und die tri map das sind beides jeweils rot schwarz bäume wie er in der dokumentation nachliest da steht auch explizit dass es rot schwarz bäume sind in der zyklus nur standard bibliothek gibt es entsprechend klassen stz und stb web da steht nicht wie es implementiert sind es ist auch nicht vorgeschrieben da steht je lediglich das suchen einfügen löschen jeweils in von login möglich sein muss tatsächlich kann einfach in die implementierung schauen ich kenne
keine implementierung von stz und sc dem app die nicht einen rot schwarz baum verwendet also rot-schwarz bäume werden in der praxis tatsächlich den apfelbäumen gegenüber bevorzugt vl hat oder markt den vorteil haben wenn wir viele suchen müssen in den baum der sich wenig verändert weil den dick niedriger sind rot schwarz bäume sind bisschen leichter zu handhaben wenn man viel einfügen und löschen muss weil diese operationen kleines bisschen billiger sind aber wie gesagt es geht tatsächlich nur um einen kleinen factor oder kleinen tick mehr als sympathisch haben wir für beide die gleiche komplexität für alle operationen
die wir uns angeschaut haben so jetzt machen wir zum abschluss tatsächlich noch ein beispielen einfügen in einen rot schwarz baum alles was ich hier mache könnte mit den beispielen auch noch mal überprüfen ob es richtig gemacht habe alles was ich hier mache aber für den fvl baum und für den 234 warum schon mal gemacht ich nehme die gleiche sequenz von zahlen jedoch bahn und wuchs in den rot-schwarzen all das solltet ihr tatsächlich auch selber machen können mit papier und stift ok schauen uns an wie wir diese zahlen in einem rot schwarz vom einfügen wir fangen
an mit der 3 die drei wird eingefügt einfügen immer einen roten knoten der baum war vorher leer das heißt diagnosen 3 ist jetzt die wurzel die wurzel wir immer schwarz das heißt wir färben um ich mal einfach drüber ich spare mir bei der darstellung die damit noten noch mit an zu zeichnen so jetzt fühlt man links von der drei die 2 1 auch wieder als roten knoten jetzt haben den roten knoten unter dem schwarzen knoten da ist alles in ordnung so jetzt kommt die einst die einst kommt links von der zwei als rotes kind jetzt
haben wir hier ne rot-rot verletzung verbrauchern zu fall unterscheiden die restrukturieren egal ob restrukturieren oder rotieren fall unterscheidung läuft über die farbe des runkel knotens den onkel gibt's hier nicht und nur für den fall dass es die nicht gibt wahrlich den dummy knoten jetzt trotzdem hin wenn es den onkeln bluten ich gibt neben den schwarzen knoten an so was passiert in dem fall wenn der onkel schwarz ist dann restrukturieren wir restrukturieren bedeutet 123 bringen wir in in oder reihenfolge dann steht die 2 als neue wurzel in der mitte und zwar als schwarze knoten links steht
die einst als roter knoten recht steht die drei als roter faden so jetzt kommt die vier die vier steht rechts von der 3 wir fügen wieder den roten knoten ein jetzt wenn man wieder ne rot-rot verletzung hier wir schauen wieder dem onkel knoten an also das ist ja nun dem einfügen der vater der großvater der onkel oder der bruder vom vater der es in dem fall rot rot bedeutet wir färben um also 1 und 3 kann den schwarze knoten dafür wird der großvater die zwei ein roter knoten jetzt immer fast fertig jetzt wird man aber
dass die wurzel immer schwarzes das heißt wann immer wir die wurzel rot gefärbt haben werfen sie einfach direkt wieder schwarz die 2 fährt man wiederum bleibt ein schwarzer nur so als nächstes fügen wir die 5 1 die fünf steht rechts von der 4 als roten knoten wir haben wieder rot rot verletzungen hier unser knoten vater großvater fall unterscheidung läuft wieder über den onkel den onkel gibt es nicht wir denken uns hier also einen schwarzen damit noten schwarzer knoten bedeutet schwarz onkel bedeutet wir restrukturieren das heißt die die einst hier schreibe ich ab 345 wird restrukturiert
in order reihenfolge die mittleren die vier nehmer als neue wurzeln das ist ein schwarzer muten die 3 und die 5 stehen als rote kinder links und rechts als nächstes für die 6 1 die sechs steht rechts von der 5 und die sechs ist als neu eingefügte knoten rot so wir haben eine rot rot verletzung wir haben an dem roten knoten den roten knoten als kind angehängt wir müssen wieder schauen vater der onkel der onkel ist rot wenn der onkel roth es dann wird umgefärbt also die drei wird in schwarz die fünf wird jetzt schwarz dafür
wird die vierte großvater knoten roth es geht weiter mit der sich mit der entscheidung mit der 7 die sieben steht rechts unter der 6 wir haben wieder eine rot rot verletzung hier wir schauen uns die farbe vom onkel an den punkt gibt es nicht also nehmen den schwarzen onkel knoten an wir müssen wieder restrukturieren so zeigen den baum ab also die 2 bleibt diese ist die schwarze eins auf die vier hier hat mir grad eben rot gefärbt die drei bleibt ebenfalls wiese ist so jetzt wird hier restrukturiert 567 in der mitte steht die sechs als
ein schwarzer knoten links die rote fünf rechts die rote sieben als nächstes fühlt man die 16 ein die 16 rechts unter der sieben verfügen auch wieder den roten knoten ein so und jetzt wird's erst mal richtig interessant weil der wir haben hier die rot-rot verletzung vater großvater onkel der ampel ist rot onkels rot bedeutet wir färben um also die fünf und die sieben werden jetzt schwarz dafür wird die sex rot und jetzt immer durch dieses umfärben haben wir hier wieder näher rot-rot konfiguration erzeugt also jetzt haben wir das erste mal diesen fall dass wir massiv
nach oben weiter restrukturieren und umfärben müssen wir haben jetzt hier die rot-rot verletzung von der 6 zu 4 4 ist der vater zwei der großvater einst der onkel das heißt die 1 die schwarz der onkel ist schwarz die restrukturierung wir förmlich um sondern wir restrukturieren 246 in oder durchlauf bedeutet dass die vier die neue nur zu wird zwar schwarz die zwei steht links von der vier rot die sechs steht rechts von der 4 auch gut so jetzt haben wir links von der 2 die einst die man noch mitnehmen müssen die drei die hier unter der
vier war kommt nach der restrukturierung hierhin wir können uns dazu die regeln merken wir können uns auch immer merken der in oder durchlauf muss gleich bleiben bzw es gibt hier gerade gar keinen anderen platz wo die drei sein könnte ansonsten wäre es kein binäre such bei mir so dann haben wir jetzt noch die fünf und die sieben die haben wir gerade umgefärbt die fünf ist schwarz die sieben ist auch schwarz und die 16 haben als roten knoten eingefügt so jetzt fehlen noch die 15 und die acht ich mache es eine grad bisschen leichter und schaffe
erst mal platz so sieht unser baum geradeaus und wir fügen jetzt als nächstes die 15 1 die 15 steht links von der 16 als ein roter knoten wir haben wieder eine rot rot verletzung den kontakten gibt es wieder nicht also nehmen den schwarzen knoten an das heißt wir müssen umstrukturieren jetzt mache ich mir noch mal einfach der teil ändert sich nicht den kopier 7 15 16 im in- oder durchlauf bedeutet dass wir hier die 15 schwarzen knoten haben links die rote sieben rechts die rote 16 hier die rot-rot verletzung schwarze onkel und haben hier lokal
restrukturiert in oder reihenfolge und den baum draus gemacht wer mutiert hätten wäre das jetzt die zick zack konfiguration und wir hätten mit doppel rotation erst nach rechts und dann das ganze nach links gemacht jetzt fehlt uns noch die acht wenn man eine erfolglose suche machen die acht das größer als die vier größer als die sechs kleiner als die 15 größer als die 7 dann liegt die acht jetzt rechts unter der 7 wir fügen sie als roten knoten 1 wir haben wieder eine rot rot verletzung wir schauen uns vater großvater den onkel an der onkel ist
auch das heißt wir müssen um fern also die sieben und die 16 werden jetzt schwarz dafür wird die 15 roth jetzt sehen wir haben hier wieder eine rot rot verletzung das heißt wir müssen wieder weg kursiv nach oben so die rot-rot verletzung haben wir hier von der 15 rauf zu 415 6 ist der eltern knoten 4 ist der großvater 2 ist der onkel dem uns anschauen müssen die zwei ist rot der onkel knoten ist wo das heißt wir werden nochmal um die zwei wird schwarz die sex wird schwarz und die vier für droht wir sind
fast fertig jetzt an den bau mit einer roten wurzer die wurzel soll aber immer schwarz bleiben das heißt wir färben die wurzel einfach um die wurzel die vier bleibt schwarz und das ist unser baum wenn man jetzt noch mal ca wir haben gesagt auf jedem pfad von der wurzel bis zu den blättern haben wir die gleiche anzahl schwarzer knoten wobei er dafür jetzt noch uns damit knoten annehmen so sehen wir mal 1234 neben den anderen zwei 1234 neben interessanten pfad über den roten knoten 12 den roten überspringen 34 wurde drei den roten bespringen 4 bzw
123 4 also auf jeden pfad von der wurzel bis zu dem blatt also zu einem von diesen damit noten die wir selber als schwarze knoten in dem fall mit sie erzählen haben wir immer die gleiche anzahl schwarze knoten und das ist in dem fall für den rot schwarz bauen unser balance kriterium wie gesagt an der stelle können wir jetzt nachrechnen wie sich daraus die formel für die höhe ergibt es ist nicht besonders schwer ein schöner induktions beweis den findet er ihm kommen zb einfacher ist es aber sich zu überlegen die rot schwarz bäume müssen balanciert
sein weil wir wissen dass die 234 bäume nach konstruktion in der höhe balanciert sind und weil wir die rot schwarz bäume auf die 234 bäume abbilden können bzw umgekehrt und damit sie mit rot-schwarz bäumen fertig die nächsten bäume die wir uns anschauen sind sogenannte bäume die sind wieder ähnlich den 234 bäumen wir balancieren also wieder aus indem wir den verzweigungen grad variabel halten und diesmal richtig groß werden lassen es gibt also immer zwei drei und vier knoten sondern die 234 bäume leben davon dass der verzweigung grad tatsächlich recht hoch werden darf und wir werden sehen
warum das sinnvoll sein kann das macht man im nächsten video