das kapitel zu suchen und gerne mit einem ausblick beenden und dabei noch mal ein paar andere datenstrukturen wenigstens kurz vorstellen das erste sind die sogenannten display displaytyp sind binäres bäume die aber nicht balanciert werden raphael bäume oder rot-schwarz bäume sondern stattdessen den rotationen verwendet einträge die ich oft suche möglichst nahe richtung wurzel zu bringen es gibt also kein balance kriterium im hinblick auf die höhe oder auf die folge von roten und schwarzen kloten sondern stattdessen das kriterium alles was oft verlangt wird soll auf einem möglichst kurzen pfad erreichbar sein das hat den vorteil dass ich
damit viele suchen beschleunigen kann dass ich unter umständen auch meine hardware die sogenannten caches besser ausnutzen kann caches und schnelle zwischenspeicher das hat allerdings auch den nachteil dass ich beim lesen auch schreibzugriffe machen muss denn ich muss ja rotieren es gibt noch einen weiteren nachteil dieses play bis hin zu konstruiert dass sie zu listen degenerieren können das heißt der schlecht dass der fall der worst case für eine suche ist eine suche in ufernähe in lineare zeit allerdings ist es durch die konstruktion auch so dass dieser schlecht dass der fall sehr unwahrscheinlich ist was man hier
wieder betrachten kann ist die sogenannte amortisiert laufzeit wir schauen uns die kosten im schlechtesten fall an und betrachten das dann aber relativ zur anzahl der operationen der suchen die wir durchgeführt haben und kommen dann im mittel amortisiert tatsächlich wieder auf den aufwand von von locken das heißt wir können tatsächlich in der praxis effizient suchen diesen begriff amortisierten laufzeit den kann man sich für displays noch mal schön anschauen wir hatten ihn schon mal kurz im ersten block als es um listen gehen als bei den vektor immer wieder in der anzahl einträge verdoppelt oder vervielfacht haben und
damit gezeigt haben dass die einzige operation am ende das push back in konstanter zeit möglich war ein ähnliches argument würden wir für display trees verwenden eine ganz andere klasse von bäumen sind traffics bäume oder im spezialfall digitalen bäume die funktionieren ganz anders als die sucht bäume die wir uns bisher angesehen haben bisher war es bei allen bäumen so dass wir uns in den knoten schlüssel gespeichert haben und dass diese schlüssel eine reihenfolge für die kinder des knotens definiert haben im präfix baum gehen wir davon aus dass unsere schlüssel zeichenketten sind nehmen 1 und 2 zum
beispiel normalerweise würden wir die schlüssel in knoten speichern im präfix baum werden die schlüssel dargestellt durch pfade von der wurzel bis zu einem knoten dabei probiere ich entweder den ganzen schlüssel oder einen teil davon und ich fang von vorne an und deswegen einen traffics des schlosses das bedeutet wichtig sind jetzt weniger die knoten als die kanten die mir sagen dass für die einzige als erstes eine kommt dann ein dann 1 n dann ein ass und auf die art und weise habe ich in dieser liste in dem fall das wort 1 kodiert so jetzt manchmal aus
der liste den baum in denen wir die zwei einfügen ja als erstes zeichen dass z dann das bsp und dann das wir werden gleich nochmal beispiele sehen wichtig ist hier die schlüssel sind jetzt fade in unserem baum wobei wir an jedem knoten entscheiden über welche kannte es weitergeht nach unten ich habe den baum gedreht also dem tor nach rechts und zwar entscheidend anhand das nächste das nächste zeichen die kannten die von der wurzel ausgehen stehen für die unterscheidung im ersten zeichen des schlosses die kanten eine ebene tiefer für die entscheidung das zweiten anhand des zweiten
zeichens und so weiter und so fort damit man das machen können braucht man natürlich ein alphabet wir müssen einmal vereinbaren wie unser zeichenketten gebildet werden können und die anzahl der zeichen diesem alphabet definiert mir dann den verzweigung sgx rad bzw den maximalen verzweigung scart im bau im einfachsten fall sind meine schlüssel einfach die folge von bits das heißt man alphabet hatten nur zwei zeichen und wir bekommen als präfix baum einen binär baum einen digital baum ich unterscheide immer zwischen nach links und nach rechts je nachdem ob das entsprechende ebit gesetztes oder nicht gesetzt ist die
andere bezeichnung für den präfix baum ist drei meinen augen die geläufige bezeichnung 3 ist ein kunstwort aus text retriever in dem ja wenn ich spreche dann auch das englische drei versuchen mir schau mal ob er den schlüssel im baum finden drinnen steckt es funktioniert genauso wie gerade eben beschrieben und in der konsequenz ist jedes wort jede zeichenkette die wir in diesen quartieren einfahrt von der wurzel bis zu einem blatt dabei muss ich mich unbedingt den kompletten schlüsse kodieren sondern es reicht sich nur einen präfix anzusehen und zwar so weit zu gehen bis es keinen anderen
schlüssel mehr gibt der den gleichen präfix hat schauen wir uns ein beispiel ich hab hier mehrere worte in den baum eingefügt abend aber krawallen chaos chor und von der wurzel an verzweigen wir jetzt über den anfangsbuchstaben dass es für diese paar worte jeweils entweder a b oder c alle worte die mit anfangen sind in diesem teil baum der durch diese kannte hier mit der wurzel verbunden wird alle worte die mit b anfangen in diesem teil baum alle worte die mit sie anfangen sind im rechten teil sorgt mit b haben wir tatsächlich nur ein wort das
ist der ball wir codieren nun den präfix bedeutet hier wir müssen einfach nur die tat zu rekrutieren dass wir als erstes zeichen in b hatten und dann es kann jetzt irgendein wort mit b sein würde mir natürlich hier in dem blatt den ball einmal speichern wenn man tatsächlich nur dem präfix codiert haben und dann wissen wir dass das wort ball im baum ist und wenn man danach suchen einfach nach dem ersten zeichen verzweigen und dann schauen wir den ball gefunden haben oder ob er nach dem anderen wort das mit baby kind gesucht haben das tatsächlich
nicht im bus so hier auf der linken seite ähnlich auf der rechten seite sehen wir dass wir hier mehrfach verzweigen aber abend und aber unterscheiden sich nicht im ersten nicht im zweiten und auch nicht im dritten zeichen und dementsprechend haben wir hier den relativ langen gemeinsamen tat auf dem beide worte den gleichen präfix von erst in vierter zeichen unterscheidet sich das ganze da hab ich für den abend ein und für aber ein den acker haben schon vorher unterschieden das war gleich das 2 2 nachdem hier sieht man schon eine schwachstelle die wir auch reparieren kann
in den preis es kann passieren dass sich schlüssel hat die tatsächlich lange präfix gemeinsam haben so dass ich über einen längeren weg in dem fall hier einmal diesen diesen einen knoten der eigentlich überflüssig ist weil diesen teil des pfades muss ich immer gehen für abend und für aber können sich jetzt hier was einfallen lassen wie immer noten die redundanz sind weil sie für gleiche präfix entstehen vermeidet sagt gleich noch ganz kurz was dazu gleichzeitig sieht man dass die suche in diesem präfix baum sehr einfach ist ich habe an jedem knoten fall unterscheidung auf der ebene
ii nach den nieten zeichen in einer zeichenkette in meinem schlüssel einfügen es ähnlich einfach ich mache eine erfolglose suche bis ich an einem knoten bin buhs für meinen präfix nicht mehr weitergeht und fügt dann die entsprechende kannte ein anwendungen für preis sind zb text indizierung 1 per scheck oder auch eine suchmaschine im weiteren sind ich möchte einfach eine menge von begriffen codieren und jeweils entscheiden ob ein begriff da ist oder nicht da ist denn die rechtschreib rechtschreibprüfung den space checke ich möchte einfach schauen ob ein gewisses wort korrektes also existiert in meiner liste von wörtern
oder nicht eine ganz andere anwendung von zeiss ist die kompression von daten hier beim kreis oft als ein vor verarbeitungsschritt verwendet weil ich die worte wenn ich sie im 3 hat gegebenenfalls für die eigentliche kompression danach geschickter agieren kann ein anderes beispiel für kreis dass ich hier nicht beschreiben in der vorlesung sind sogenannte hoffmann bäume oder hafen coding ganz grob vergleichen mit ich bau mir eine art morse alphabet auf morse deshalb weil es gibt genau zwei zustände lang kurz oder eben 0 1 für die zustände von einem bett und ich bau mir dieses morse alphabet
auf gemäß den relativen häufigkeiten von zeichen in einem text was dabei entsteht ist auch wieder ein kran den verwende ich einmal um die codierung zu beschreiben also um mir dieses morse alphabet zu erzeugen und zum anderen dann auch um zu codieren oder zu dekodieren so habe ich noch mal aufgeschrieben half men coding ist ein anderes anwendungsbeispiel ein problem bei diesen preis können lange gemeinsame teil worte seien nehme als beispiel die rechtschreibprüfung dann in deutscher sprache wo wir beliebig lange worte zusammensetzen können was dabei schnell passieren kann dass ich im baum knoten hat die keine information
tragen hier im beispiel heben war dass dieser knoten hier auf dem weg zum abend aber auch zum aber muss ich diesen knoten passieren habe ich habe hier keine wahlmöglichkeit mehr anders abzusteigen indem sie ist der knoten redundant ich brauchen aber hier für die codierung auf diese art und weise können auch reis unausgeglichen sein ein lösungsansatz dazu sind die sogenannten betrüger bäume das ist eines der schöneren akronyme in der informatik die findet auch ein buch von gunten sage nochmal schön beschrieben die idee ist ganz einfach ich möchte solche knoten die keine information halten vermeiden möchte also
die entsprechenden zeichen oder teil worte überspringen und was ich dazu macht ist im try trägt nicht nur die kante eine information also was ist das nächste zeichen sondern gleichzeitig auch noch der knoten dort speiche ich eine zahl wie viele zeichen ich noch überspringen darf darauf gehen wir jetzt nicht mehr ein für uns soll es das mit kreis und drei fixe bäumen erst mal gewesen sein wir merken uns die idee die ist ganz einfach preis eine sehr einfache datenstruktur ich speichere eine menge von schlüssel zeichenketten nicht in den knoten sondern als fade hin bauen das ist
eine idee die man tatsächlich oft auch mal in der praxis gut brauchen kann damit sie mir schließlich auch am ende von dem kapitel zu sucht räumen wir hatten uns binär besuch bei mir angeschaut balanciert suche mir angeschaut verschiedene kriterien für balance angesehen und gesehen dass wir damit abstrakte datentypen pz oder web implementieren können führung noch mal ihr findet beispielcode und demos zu allen such bäumen die wir uns genauer angeschaut haben insbesondere allgemein zu binären zu bäumen bäumen zu den balancierten sucht bäumen binär war das vl und rot schwarz aber auch zu den zwei 34 und
bäumen ihr könnt mit hilfe der demos bäume erzeugen knoten immer wieder einfügen mit bein research freaks ampel die rotationen oder auch lokalen restrukturierungen auch das löschen nachvollziehen mit den anderen beispielen jeweils einfügen für vl und rot-schwarz wird jeweils die verletzung der eigenschaft vorher kurz festgehalten danach wird restrukturiert also ihr seht den zwischenschritt zumindest in teilen ähnlich für die zwei 34 und die bäume wenn der knoten in anführungszeichen zu groß wird also wenn ich den fünf knoten hätte oder ich in den knoten b baum einen eintrag zu viel einfügen möchte dann sehe ich das einmal als
verletzung einer eigenschaft danach wird geteilt und hochgezogen all das könnte euch grafisch anzeigen lassen ihr könnt damit auch relativ große bäume erzeugen für leidlich große bäume gibt es noch anderes demo das heißt ränder tree der unterschied ist dass für alle demos hier interaktiv eingefügt wird also nach jedem knoten wird wieder der baum visualisiert für energy wird alles einmal eingefügt und danach könnt ihr euch die pdf oder svg datei ausgeben lassen und an schaut euch meine beispiele anschaulich aber gerne auch die beispiele in der literatur an zum beispiel die die mit dem buch von untersagt gekommen
aber auch die von bachelor master oder sekt zum beispiel was mir wichtig ist ich habe eine mögliche implementierung angegeben es gibt aber immer noch weitere varianten und es ist wie so oft im leben es gibt nicht unbedingt die bessere sondern jede hat ihre vor und ihre nachteile und ich finde es ganz schön wenn man sich verschiedene implementierungen anschaut und über diese vor und nachteile auch mal nachdenkt also ich habe mit sicherheit nicht die weltbeste implementierung hier geliefert ganz im gegenteil versucht möglichst wenig code zu schreiben um den preis dass man sich es auch ein bisschen
ineffizientes was andere einfach an der städte besser machen und das bin ich es wert sich mal anzuschauen hier findet auf den folien im anschluss auch noch mal eine reihe von fragen dass man auch vorschläge über was man nachdenken kann oder an welcher stelle man sich vielleicht mal in die implementierung bisschen einarbeiten könnte bzw auch wo man vielleicht anfangen könnte das zu tun schaut euch das einfach jeweils noch mal selbst an