AuD 2020: Skip Lists

es gibt ist sind eine alternative zu suchen bäumen und eine ganz andere datenstruktur es gibt ist sind pro babbel ist ish das heißt wir verwenden zufall gleichzeitig gibt es eine sehr einfache datenstruktur vor allem wenn man es mit vl oder rot-schwarz bäumen und balancierten bäumen vergleicht wir erweitern einfach unsere verkettete liste das problem dabei hilft wir müssen schon verkettete liste wir können nicht effizient suchen die skippers verwendet jetzt zufällige entscheidungen um für eine balance zu sorgen allerdings wird diese balance nicht garantiert aber sie ist in gewisser weise wahrscheinlich oder soll es umgekehrt sagen es ist

unwahrscheinlich dass die skip lässt tatsächlich sehr schlecht balanciertes oder tatsächlich journalisten die generiert und gleichzeitig ist das ganze super einfach zu implementieren was wir erreichen wollen mit dem zufall hier es tatsächlich zeigen zu können dass wir für die suche für das einfügen oder auch für das löschen einen aufwand von login haben in dem fall nicht als garantie sondern erwartet das heißt wenn wir immer wieder suchen dann ist der erwartungswert für den aufwand einer suche begrenzt durch von login wobei in die anzahl der einträge in unserer datenstruktur sind schauen wir uns an wie das funktionieren soll

es gibt es setzt erst darauf auf eine verkettete liste ich nehme hier als beispiel immer eine liste sortierte liste von primzahlen also ich habe eine verkettete liste und die hält meine einträge in sortierte reihenfolge hier 235 7 und die idee setzt dass es das gibt es gibt ist dass ich noch zusätzliche verkettungen mit einfügt das heißt ich brauche dann hier natürlich auch die entsprechenden attribute das heißt ich habe nicht nur next attribut sondern sie müssen noch irgendwie weitere attribute gespeichert werden die für eine verkettung sorgen ich werde auf die implementierung im folgenden überhaupt nicht eingehen

wenn man verkettete listen verstanden haben dann denke ich kriege und das ganz gut hin so wichtig ist die idee und die ist hier schon skizziert wir bauen uns zusätzlich noch abkürzungen in dem fall habe ich das so gemacht dass ich jeden zweiten eintrag überspringen bedeutet wenn er in dieser liste suchen wollen irgendwie wollen zum beispiel die sieben suchen dann muss man nicht von der 2 ausgehen zu drei zu 57 sondern wir würden von der zwei die abkürzung zu fünf nehmen und dann 1 weitergehen zu 7 und wir können das auch als einen algorithmus beschreiben denn

wir würden als erstes immer die abkürzung gehen jetzt schauen was steht da hier steht eine 5 die fünf ist kleiner als die sieben also nehmen wir die abkürzung weil die drei spiele schon keine rolle mehr so als nächstes nehmen wir wieder die abkürzung zu elf die elf ist aber größer als die sieben also laufen an diesem weg hier nicht nach sondern wir gehen eine etage tiefer hier ein zweiter und handeln die sieben gefunden das ist schon die ganze idee jetzt sind meine listen natürlich normalerweise ein bisschen länger beziehungsweise es nützt mir wenig wenn ich nur

jedem zweiten eintrag überspringe ich möchte das ganze jetzt hierarchisch machen zum beispiel könnte das so aussehen für ein bisschen längere liste hier haben insgesamt zehn verschiedene schlüssel gespeichert und wir haben jetzt verschiedene ebenen einmal unsere verkettete liste ganz unten und jetzt eine ebene wo man jeden zweiten überspringen einer ebene wo man jeweils drei überspringen und dann nochmal eine ebene trüber und die idee ist dass wir von ebene zu ebene die anzahl der einträge die wir überspringen so in etwa halbieren so wie es hier gezeichnet hat das wäre schon eine idealvorstellung idealvorstellung deshalb weil das ganze

recht gut balanciertes vor uns mit der balance beschäftigen schauen wir uns nochmal die suche an wenn ich nach einem eintrag in einer skip lässt suchen möchte dann fange ich immer links oben an hase hier habe ich meine verkettete liste ich verwende damit noten head und tail ganz links und ganz rechts ich fang im head- knoten an und ich organisiere alle knoten so dass ich von oben nach unten eine liste von verkettungen hab ganz unten habe ich die verkettung meine eigentlichen liste und in den ebenen trüber meine abkürzungen ich fang ganz oben an weil ich immer

zuerst der abkürzung nach auf so jetzt habe ich wenn ich an dem knoten stehen drei fälle der erste fall der schlüssel an den knoten ist das was ich suche dann bin ich fertig der zweite fall ich gehe der next referenz am knoten nach und schaue mir den schlüssel dort an und der schlüssel dort ist kleiner als das was ich suche dann darf ich nicht weitergehen entschuldigung der schlüssel dort ist größer als das was ich suche wegen falscher dann gehe ich nicht weiter sondern dann steige ich eins nach unten ab ansonsten wenn mein schlüssel den ich

so größer ist als das was drin steht beziehungsweise so wie es gerade falsch gesagt habe wenn der schlosser den ich erreicht wenn ich den link nachlauf kleiner gleich dem schlüssel ist den ich suche dann folglich den link nach rechts schauen wir uns einfach gerade an den beispielen ich möchte hier nach der 13 suchen ich fahre hier oben links an so ich habe offensichtlich hier die 13 noch nicht gefunden hätte und tail kriegen jeweils noch einen wächter wert - unendlich und lust unendlich auf die art und weise kann ich vergleichen also ich habe hier das was

ich suche die 13 nicht gefunden also schaue ich zum nächsten knoten was da drinsteht dass es die 11 13 es aber größer als elf das bedeutet ich nehme diese abkürzung auf jeden fall und stehe jetzt hier so ich mache das gleiche wieder schaut die abkürzung weiter dann bin ich beim teil knoten der wert ist unendlich 13 es aber kleiner als unendlich also darf ich hier nicht weitergehen soll ich gehe eine etage tiefer dort mache ich das gleich ich nehme die abkürzung da steht mit 23 13 kleiner als 23 also brauche ich die abkürzung nicht nehmen

ich gehe eine etage tiefer 3 cents kleiner als 17 also darf ich auch diese abkürzung nicht nehmen ich gehe wieder eine etage tiefer ich bin bei der 11 g1 nach rechts 13 ist kleiner gleich 13 also ich gehe tatsächlich nach rechts das war mein dritter fall hier und jetzt habe ich den ersten fall ich habe die 13 gefunden und bin fertig noch ein anderes beispiel hier sucht man nach der 19 gleiche spiel wir nehmen die abkürzungen 19 ist größer als die 11 das heißt wir nehmen auf jeden fall diese abkürzung schauen jetzt hier 19 ist

aber kleiner als unendlich das heißt die hier nehmen nicht wirklich nach unten 19 ist kleiner als 23 das heißt die nehmer auch nicht weg nach unten 19 ist größer gleich 17 das heißt jemand tatsächlich nach rechts versuchen wieder nach rechts zu gehen da ist die 23 das ist zu groß also gehen wir wieder nach unten und gehen jetzt in dem fall noch eins nach rechts und haben die 19 gefunden und letztes beispiel gesucht nach der 29 der anfang ist wieder der gleiche wird können die erste abzunehmen hier kann man nicht weiter beginn 1 nach unten

wir nehmen die nächste abkürzung hier hier dürfen nicht weiter wir gehen nach unten hier darf man auch nicht weiter wir gehen nach unten und wir gehen noch einmal nach rechts und haben die 29 gefunden ich habe jetzt laute beispiele von erfolgreichen suchen gezeigt kann sich leicht überlegen wie eine erfolglose suche abläuft was mir gesehen hat ist diese drei fälle sind bisschen anders aber schon irgendwo auch ähnlich wie im binären such baum ich schaue immer was steht an meinem knoten welche schlüssel steht dort und entscheide mich dann für eine richtung links oder rechts und die dem

fall hier entscheide ich mich nicht links oder rechts sondern abkürzung nehmen oder nicht nehmen beziehungsweise nach rechts oder nach unten gehen zwar allerdings immer noch die liste die ich als idealfall dargestellt habe weil ich ungefähr immer die anzahl einträge von ebene zu heben halbiert habe das ist genau dass wir uns den idealfall auch vorstellen das heißt wenn wir in einträgen und zur liste haben dann haben wir noch zwei von vielen ebenen weil wir immer halbieren wenn ich suche dann muss ich pro ebene jeweils zwei knoten betrachten nämlich tut man so als stehe gerade hier gehen

die abkürzung ein zweiter schauen uns also an was da steht vergleichen und gehen nach unten das war der eine knoten der andere knoten wir müssen natürlich den knoten auf dem wir stehen selber anschauen ob wir den wert nachdem wir suchen schon gefunden also pro ebene muss ich mir zwei knoten anschauen den wo ich stehe und den wohin die nächste abkürzung mich führt wichtig ist hier diese zwei das ist ein konstanter wert und wir haben wovon locken viele ebenen und damit könnten wir in diesem idealfall die suche auch in von login durchführen bisher ist die liste

erst mal vom himmel gefallen aber das tut sie natürlich nicht sondern wir bauen uns diese liste auf indem er immer wieder einfügen so und jetzt fragen uns wie sieht denn jetzt die idealfall aus beziehungsweise wie müssen wir diese liste balancieren und die idee wird jetzt sein dass wir eben nicht versuchen strikt zu halbieren all nicht eine perfekte balance zu schaffen dass man im übrigen in balancierten binär bäumen auch nicht weder der hvl baum noch der rot schwarz baum sind perfekt balanciert wir lassen jeweils zu dass er auf der einen oder auf der anderen seite ein

bisschen über hin dürfen wir sorgen nur dafür dass das nicht beliebig viel überhang sein kann wir nehmen hier eine ähnliche idee im sinn von dass wir nicht strikt halbieren aber wir nehmen auch kein striktes balance kriterium das uns den schlechtesten fall auf jeden fall vermeidet oder das garantiert dass der schlecht dass der fall die entartung zur liste nicht eintreten kann den anspruch haben wir hier nicht dafür wird alles viel einfacher und gleichzeitig kann es uns auch relativ egal sein denn wir wollen nicht strikt halbieren sondern wir wollen die liste so organisieren dass wir im mittel

in der ebene 1 höher etwa die hälfte der einträge erwarten also der erwartungswert für die anzahl der einträge auf der höheren ebene soll etwa eineinhalb mal die anzahl der einträge auf der tieferen ebene sein so wenn ich hier schreibt wir wollen das erwarten dann bedeutet das wir dürfen hier zufall zu hilfe nehmen das heißt wir entscheiden einfach zufällig ob ein knoten auch auf der ebene 1 höher verkettet wird oder nicht zufällig bedeutet hier begeben denn einfach eine 50 50-chance dann haben wir hier wieder genau diese einen halb mit drin wir werfen einfach die münze und

plötzlich ist das einfügen ganz einfach das ist kein vergleich zu den rotationen oder restrukturieren israel oder rot-schwarz baum sondern es einfach einfügen in ein erstmal eine suche die haben gerade schon durchexerziert dann einfügen in der verkettete liste und danach einfach nur verkettungen höher mit nachziehen mit einfügen und zwar einfach nur anhand eines zufalls kriteriums dieses nutzen vom zufall nennen wir auch randomisierung oder randomization das heißt ich garantiere nicht die perfekte balance sondern ich sorge dafür dass der erwartungswert mir eine perfekte pendant eine perfekte balance liefert das wiederum bedeutet dass wenn ich dem knoten eingefügt habe

dann möchte ich dass die wahrscheinlichkeit dafür dass ich eine ebene höher eine verkettung hat ein halbes die wahrscheinlichkeit dafür dass ich zwei ebenen höhe den gleichen knoten auch noch für kette soll dann ein halb mann halb also ein viertel sein und so weiter und so fort und diese regel ist tatsächlich sehr einfach ich muss nur immer wieder eine münze werfen um zu entscheiden ob ich eine ebene höher noch für kette oder nicht das ganze ist sicher nicht perfekt balanciert das ganze kann auch entarten wenn meine münze immer wieder zahlt anzahl zahl zwar liefert also entweder

wenn sie gezielt das oder wenn ich wirklich sehr viel pech aber ich muss wirklich sehr viel pech haben es wird nämlich sehr unwahrscheinlich dass das ganze journalisten entartet also das suchen einfügen wieder ufern ändert und das einfügen an als erstes machen eine erfolglose suche danach hängen wir den neuen knoten in die unterste ebene also in unsere verkettete liste ein als nächstes werfen wir eine münze immer wieder so lang wie uns der münzwurf zahlen liefert das ist völlig willkürlich hier wichtig ist nur mit einer wahrscheinlichkeit von eineinhalb führen wir die schleife einmal aus und dann beginnen

wir das ganze spiel wieder von vorne was machen wir in der schleife wir sorgen dafür dass der knoten in der nächsthöheren ebene auch nochmal eingehängt wird so an der stelle muss man sich ein paar gedanken über die implementierung machen auf die ich hier nicht eingehen es ist nicht wirklich schwierig man muss ich bei der suche paar sachen merken dann kriegt man das mit dem einhängen die ebene höher ganz gut hin also unsere unterste ebene auf der herrlich ein dies immer da und jetzt ist ganz leicht wenn ich immer wieder die burg münze werfen beim ersten

münzwurf habe ich eine wahrscheinlichkeit von einem halb dass ich eine ebene höher auch verlinkt beim zweiten münzwurf habe ich eine wahrscheinlichkeit von ein viertel dann ein achten und so weiter und so fort und man zieht es wird sehr unwahrscheinlich dass ich besonders weit nach oben das ganze verkettet es wird unwahrscheinlich aber trotzdem wird's immer wieder knoten geben wo diese sequenz stückchen höher ist und zwar je mehr einträge ich jemanden liste habt desto mehr solche knoten wird es auch geben die noch weiter oben verkettet sind rum kann sie leicht überlegen dass das tatsächlich mir eine gewisse

balance schafft schaue man zum beispiel an ich habe mir hier münzwurf vorbereitet k steht für kopf head steht für zahl in dem fall jetzt nachgezählt müsste das sogar ausgeglichen sein obwohl man natürlich sieht dass dieses muster nicht unbedingt immer wieder zwischen kopf und zahl einfach nur abwechselt was sie hier sieht ist tatsächlich das ergebnis von einem zufälligen münzwurf beziehungsweise von einem simulierten zufälligen 0 12 ich füge wieder bringt sein in die liste ein und ich habe das hier schon mal gemacht für die zwei die drei die 711 die 13 1923 wurde die 29 ich habe

sie in der reihenfolge schon in die liste eingefügt das ist auch noch eine schöne eigenschaft da ich hier mit dem zufall arbeite gibt es jetzt keine reihenfolge die besonders gut oder besonders schlecht das ist es völlig egal wie ich meine knoten in die liste einfügt es kann immer mal zufällig besser oder schlechter gehen schauen wir uns an wie ich hier abgestrichen kann ich habe die zwei eingefügt in die liste ab kopf geworfen das heißt hier passiert nichts weiter habe die 3 eingefügt in der liste zahl geworfen das heißt die drei ist eins höher ein gehängt

worden dann nachhaltig kopf geworfen das war's mit der 3 ich habe die sieben eingefügt kopf geworfen da ist nichts weiter passiert ich habe die elf eingefügt zahl geworfen das heißt die elf ist eine edle drüber eingehängt werden nochmal zahl gebäude geworfen noch eine ebene darüber noch mal zahlen geworfen noch eine ebene drüber kopf geworfen und das war's mit der 11 an der stelle für die implementierung von skip test ich lasse hier zu dass ich tatsächlich mit dem münzwurf beliebig hoch geht tatsächlich ist es nicht unbedingt sinnvoll redundante ebenen oder die gleiche ebene noch mal einzuziehen

also man kann noch ein zusätzliches abbruch kriterium in die schleife mit drei machen auf der anderen seite es schadet uns hier auch nix also wir müssen uns gerade denken dass dieser ganze rechte teil hier noch nicht dabei war wir haben gerade die elf eingefügt er schadet uns in dem sind aber auch nix hier zwei gleiche verkettungen zu haben denn es ist ja unwahrscheinlich dass das besonders viele redundante verkettungen werden aber an der stelle in einer richtigen implementierung würde mir das ein kleines bisschen geschickter machen genauso wie man nicht münzen werfen würde sondern das ganze auch

machen kann indem er sich eine zufalls zahl holt und dann dort einfach zb die anzahl der führenden nullen sich anschaut und daraus die idee in einem zug berechnet so dann kommt die 13 zahl gewürfelt das heißt 1 weiter oben noch eingefügt kopf geworfen das war's die 19 genau das gleiche die 23 habe ich gleich kopf geworfen die 29 kopf geworfen so und dann sind fertig und jetzt fügten noch die fehlenden 1 das ist als erstes die 5 bei der 5 hatte ich kopf geworfen die wird einfach so in die liste eingefügt jetzt kommt die 17

war bei der 17 habe ich zahl zahl zahl und dann erst kopf geworfen das heißt sie habe ich drei ebenen auch drüber und jetzt kommt noch die 31 bei der 31 habe ich wieder kopf geworfen das heißt hier passiert nichts weiter so das ist eine mögliche darstellung hier als gibt es das hätte natürlich auch ganz anders kommen können wir machen jetzt das gleiche noch mal und zwar mit den verbleibenden müntz würfen hier ich zeige euch gleich das ergebnis wir fügen wieder die gleichen zahlen diesmal in der reihenfolge von 2 bis 31 1 indem wir hier

an der stelle weiter machen die zwei zahl gewürfelt ein zweiter oben eingehängt dann kopf gewürfelt die drei kopf geworfen passiert nichts weiter fünf kopf geworfen es passiert nichts weiter sieben kopf geworfen es passiert nichts weiter elf zweimal zahlt dann tropft also zwei ebenen darüber 13 kopf sitzen zwei mal zeit und kopf 19 genau das gleiche 23 zahl zahl zahl kopf auf drei ebenen drüber dann kommt die 29 die 31 und wir sind fertig als wir haben das gleiche noch mal gemacht mit einer anderen folge von zufälligen dürfen und wir kriegen natürlich eine andere liste raus

wie sie tatsächlich anders aus was das nochmal die von gerade und jetzt aber trotzdem werden wir gleich zeigen dass die in gewisser weise auch ausbalanciertes oder dass wir das erwarten dürfen da wir machen das noch mal mit der verbleibenden folge hier nochmal studium eines gitters auffangen hier an mit der zwei kopf geworfen die bleibt jetzt kommt die neun damen ein gewisser weise pech zahl zahl zahl zahl kopf das heißt zunimmt 39 das heißt lasst hierzu dass wir tatsächlich gleich vier ebenen noch höher gehen wie gesagt das kann auch anders implementieren dann kommt die 52 zahl

kopf und so weiter und so fort ganz am schluss habe ich mir noch ein paar entwürfe besorgt die vorher noch nicht in der tabelle waren ansonsten habe ich einfach weitergemacht und ab gestrichen und wenn wir jetzt vergleicht haben wir für verschiedene sequenz von entwürfen für die gleichen zahlen die wir eingefügt haben beim ersten mal war die einfüge reihenfolgen kleines bisschen anders weil man einige erst später eingefügt haben für nummer zwei und nummer drei war die einfüge reihenfolge jeweils gleich wir haben drei verschiedene es gibt es wir können aber jetzt auch sehen wenn es um das

gibt es das suchen dann brauchen ungefähr die gleiche anzahl schritte überall es wird hierbei keine der listen dramatisch schlecht man muss jetzt ehrlicherweise auch sagen diese listen sind relativ kurz wir sprechen wir hier von zufall und erwartungswert und wir wissen natürlich auch dass der erwartungswert ja umso aussagekräftiger für uns wird umso größer die zahlen sind oder auf den zufall verlassen können wir uns erst ferner wirklich mit großen zahlen arbeiten aber das ist ja genau das was wir wollen wir wollen ja viele einträge in sohnes gibt es speichern das in wird groß beziehungsweise dann wenn das

en gros wird dann sind wir insbesondere darauf angewiesen dass wir in logarithmische zeit suchen können und das wollen wir uns jetzt nochmal allgemein überlegen also wir analysieren es gibt löst und überlegen uns als allererstes dass die erwartete anzahl von ebenen von lok ennis warum auf der ebene 0 habe ich endnoten das ist unsere verkettete liste eine ebene trübe erwarte ich die hälfte der knoten weil ich erwarten kann dass die hälfte der münzwurf mir zahl liefert zwei ebenen darüber kann ich ein viertel der knoten erwarten welche zweimal die münze werfen muss zweimal zahl braucht damit ich

zur ebene 2 kommen für die ebene 3 bräuchte ich schon dreimal hintereinander zahl das kann ich für ein achtel der knoten erwarten und so weiter und so fort auf der ebene zweier logarithmisch von n ist die anzahl der knoten die ich erwarte 1 und wenn ich noch höher geht dann wird der erwartungswert plötzlich kleiner als 1 das bedeutet natürlich trotzdem dass ich da immer wieder knoten see das war mein beispiel auch gerade gesehen ja hier zum beispiel so was passiert aber es eben nicht besonders wahrscheinlich also ich erwarte eine anzahl von ebenen die beschränktes into

von login dass wir uns gerade überlegt so jetzt müssen wir uns noch überlegen was muss ich denn auf jeder ebene machen ich muss zeigen dass ich auf jeder ebene nur konstanten aufwand ab dazu schauen uns die suche wieder an aber wir schauen sie diesmal rückwärts an wir suchen hier nochmal nach der 19 sind also diesen pfad hier bis zu 19 gegangen wenn man es das rückwärts anschauen also müssen von den 19 wieder hier auf dann haben wir jeweils zwei möglichkeiten und zwar ich kann entweder zurück nach links gehen oder ich kann nach oben gehen und

die regel ist ich versuche immer nach oben zu gehen hier ging es nicht nach oben also gehe ich nach links hier gehe ich natürlich nicht nach links weil wenn es nach oben weiter geht dann bin ich auch von oben gekommen also ich gehe hier nach oben zurück nach rechts nach oben nach oben nach rechts ich habe also bei dieser rückwärts betrachtung zwei möglichkeiten entweder ich gehe zurück nach oben oder ich gehe nach links ich gehe wenn möglich immer nach oben weil wenn es nach oben weiter geht dann bin ich auch von oben gekommen von links

aus bin ich nur gekommen wenn ich über eine abkürzung gekommen bin also über den abkürzung oder über den regulären verkettung slink in jedem dieser rückwärts schritte ist die wahrscheinlichkeit für den ersten oder den zweiten fall jeweils ein halb warum die wahrscheinlichkeit dass es nach oben weitergeht ist ein halb nach der konstruktion wie man beim einfügen unsere knoten gestaltet haben wir haben immer wieder die münze geworfen also mit einer wahrscheinlichkeit von eineinhalb eine ebene höhe verlinkt genau diese wahrscheinlichkeit verlängere verwenden wir jetzt das heißt mit einer wahrscheinlichkeit von eineinhalb gibt's 1 obendrüber eine verkettung und wenn

es die gibt dann wird man die im rückwärts schritt auch gehen wenn sie j die anzahl der schritte bezeichnet die ich brauche um j ebenen nach oben zu gehen oder um von der iucn ebene nach oben zu kommen damit meine ich um hier zu der ebene wieder hochzukommen also wenn man in dem fall von oben zählen 123 um drei ebenen nach oben zu kommen also das sollte sie jetzt sein was muss ich machen ich muss auf jeden fall einen schritt gehen danach wo sich entweder noch cj - ein schritte gehen oder ich muss noch cj

schritte gehen abhängig davon ob dieser eine schritt nach oben gegangen ist oder nach rechts gegangenes nach oben und nach rechts bin ich jeweils nach oben nach links entschuldigung bin ich jeweils mit einer wahrscheinlichkeit von einem halb gittern das sind die fälle die wir haben und das reicht uns um jetzt eine formel für cj zu konstruieren also cj ist auf jeden fall einmal ein konstanter aufwand ich muss nach oben oder nach links gehen plus ein halb mal zu jot - einsplus einhalb mal cj das ist der aufwand den wir noch bleibt wenn ich nach oben gegangen

bin die ebene es um 1 kleiner geworden oder die ebene bleibt gleich wenn ich nach links gegangen bin beides geschieht mit der wahrscheinlichkeit von eineinhalb dazu j die erwartete anzahl schritte ist gewichtig hier mit den entsprechenden wahrscheinlichkeiten jetzt bleibt uns nur noch zu rechnen das ist unsere formel wir multiplizieren auf beiden seiten mit 2 dann steht links zwei cent auf der rechten seite stehen auch noch mal ziert ich kann links und rechts jeweils ein ziert wegstreichen und da bin ich im prinzip fertig denn wenn man jetzt noch uns überlegen dass wir auf der ebene 0

nichts zu tun haben bedeutet das ja dass wir beim übergang von einer von einer ebene zunächst in zwei größer werden das heißt insgesamt bekommen wir als geschlossene form jetzt cj ist zweimal j also nochmal die anzahl der schritte die wir erwarten um von ebene j nach oben zu kommen ist einfach zweimal j zweimal der index die ebene und da unsere anzahl ebenen also dass j.lo von lok ein beschränktes sehen wir damit auch dass die suche jetzt insgesamt von log in ist denn es passierte hier noch was konstantes und wir hatten uns das ganz am anfang

im idealfall schon überlegt dass wir zwei operationen pro ebene haben und hier ist es ist so wir haben tatsächlich zwei operationen pro ebene aber eben erwartet damit sie immer mit der analyse fertig und prinzip man damit es gibt listen auch gut verstanden ein vorteil ist auch noch anders als bei den balancierten zu räumen dass beides gibt liste das löschen ganz einfach wir müssen nämlich gar nichts besonderes machen wir müssen im wesentlichen nur unseren knoten aus der liste raus löschen und das war's also kein vergleich zu dem was wir in einen baum oder rot-schwarz baum machen

müssten dass man es auch in der vorlesung nicht angesehen damit sind es gibt listen eine schöne und interessante alternative zu balancierten such bäumen es gibt es noch ein paar andere vorteile wenn man an den daten parallel arbeitet aber das soll hier nicht das thema sein sie sind wir sehr einfache datenstruktur und was ich hier in dem kontext interessant fand es ist ein beispiel von einer randomisierten datenstruktur also wir den zufall verwenden um den schlechtesten fall den degenerierten fall zwar nicht auszuschließen aber sehr unwahrscheinlich zu machen und in der praxis genügt uns das in aller regel