Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Informatik 1 — Chapter #11 — Video #049 — Binärbäume, Visualisierung, Applikationen, (btree-of t)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 293 Zeilen
- so ich grüße euch zusammen hätten wir wieder das ist das kapitel 11 aus der vorlesung informatik 1 servus und größe diesmal wieder aus der wartungshalle
- aufgabe in vier hinter mir stehen die xbox schon aufgereiht und fertigt dem staat aber meine gedanken gehen nur ehen das in die richtung des kapitals 11 und
- in dem kapitel 11 werden wir uns eine neue datenstruktur wie an land ziehen bisher war unsere goto datenstruktur eigentlich die liste klar wir haben
- einen ausflug in die streams gemacht und diesen ausflug später auch noch mal fortsetzen aber jetzt kommt eine neue datenstruktur auf dem tisch eine die
- wirklich so ungeheuer wichtig ist dass ich sagen würde mensch wenn ich nur eine datenstruktur mit auf eine einsame insel nehmen würde dann wäre es die
- datenstruktur die wir hier im kapitel 11 besprechen werden und das sind die bäume die binäre bäume in diesem ganz bestimmte kapitel ok ich
- hab' das binär hier schon mal so ein bisschen in klammern gesetzt um schon so ein bisschen anzudeuten ja es wird noch andere formen von bäumen geben und das
- ist tatsächlich so wir werden noch andere arten von bäumen dieser vollzogen anfassen im kapitel 12 zum beispiel werden wir eine bestimmte
- art von borrmann fassen die zwar auch binär ist aber trotzdem in ihrer struktur wie anders aussehen wird ihr werdet das sehen auf übungsleitern
- werden wir auch noch andere bäume wie anfassen aber baumstrukturen das ist das thema für die nächsten paar videos vier oder fünf videos während werden dass es
- vielleicht ein etwas kürzeres kapitel aber nicht weniger wichtig im gegenteil ok dann lasst mal schauen was wir finden wenn wir hier die tat leid über blättern
- und wir landen mitten mitten gleich in der definition von binär bäumen ok oder den sogenannten binary tree hier sind sie okay genau wie wir für uns
- für andere container datentypen strukturen wie zum beispiel die streams stream auf de oder für die listen list auf den eigene signatur gebaut haben
- werden wir uns hier eine eigene signatur für diese binär bäume für die binary tree is oder wie sie hier genannt habe für die seiten beatrice dadurch gleich
- noch was zu sagen gebaut haben und das wird auch eine parametrische signatur sein denn genau wie listen elemente einer signatur t für
- und aufbewahrt haben werden diese daten strukturen die wir jetzt bauen werden die binär bäume uns auch elemente wie wenn sie bisschen anders nennen aber
- elemente einer signatur t aufbewahren ok alle in so einem baum aufbewahrten elemente werden die signatur tragen das sind homogene container oder homogene
- strukturen wie sie bisher immer gesprochen haben wir besprochen haben ok und auch die art und weise wie wir uns der definition von diesen
- datenstrukturen nähern ist alles bekannt wenn euch wie wenn jetzt euer hirn zurückgespult und auf die entsprechenden slides zurück blättert wo wir uns die
- listen gegriffen haben und die listen irgendwie handhabbar gemacht haben dann gibt es ein großes debüt all das was man hier an der stelle sieht muss doch
- irgendwie schon mal gelaufen sein denkt man sich und tatsächlich ist es eine variation des themas zur eco sieben listen okay also so ein binär baum kann
- zwei formen an dem entweder er ist der sohn alte lehre binär baum und wir werden ihnen durch den durch den wert md trillian der stadt darstellen
- okay das hört sich doch schon mal an wie empty die lehrer liste okay die andere formen die einzige andere formen diesen binär baumann nehmen kann ist wenn er
- nicht lesen und wenn er nicht leer ist dann trägt so einen binär baum mindestens ein element ok und hier ist ein elementares und elementis dass wir
- in unserem beerbaum speichern werden und klar das hat die signatur t genau wie hier im gerade schon versprochen habe ok ja wenn wir jetzt an die listen denken
- würden dann würde zudem element zu dem kopf element ex dass wir in so einer liste speichern würden noch eine rest liste gehören
- ok genauso sieht es hier bei den bäumen aus bloß dass wir zwei rest bäume würden wir sie vielleicht nennen wollen hier am wickel haben ich nenne sie den rest
- bäume ich nennen sie teil bäume weil das offizielle sprech in der informatik da draußen ist okay also nicht der baum speichert ein element
- dass der signatur tw nennen sixx und zwei teil bäume zwei teil bäume die selber wieder bäume silber wieder binär bäume sind selber wieder beatrice of
- these okay ist klar wenn das hier dass mp3 die möglichkeit ist so ein lehrern baum zu konstruieren wie konstruieren wir dann in nicht deren bau mit hilfe
- dieses konstrukt mit hilfe des konstrukteurs may not und der hat natürlich genau 33 argumente okay das element ist dass wir speichern wollen
- steht zwischen dem sogenannten linken und dem rechten teil baum l und er wie es hier sehen könnt ok l und er sind selber wieder wien er bäume okay da kann
- sich das beliebig groß ist rindt dahinter verbergen vielleicht ist er lehrer baum vielleicht ist er ein nicht lehrer baum und ist damit wieder einen
- knoten der ein anderes element six strich trägt usw genau hier in der stelle steht die revision genau an der stelle klappte die
- möglichkeit eigentlich beliebig große baumstrukturen irgendwie zu konstruieren alles da gut das ist schon die rezessive definition an der stelle
- wer da keinen vergleich ziehen kann zu der welt der listen das würde mich doch sehr verwundert hier unten ist auf der folie explizit
- hervorgehoben wie sich die ganze sache so vergleicht ok ja noch ein bisschen zu technologie auf der nächsten seite habe noch ein bisschen der mehr theologie
- nachzuliefern aber jedes dieser elemente die wenn sie in binären speicher werden werden wir knoten nennen ok also ein baum es entweder leer gebaut
- durch ntt oder er ist ein knoten der ein sogenanntes labels trägt okay das ist unser element von dem wir gerade gesprochen haben so tricks und hat auch
- noch einen linken und einen rechten teil baum l bzw r damit haben die ganzen komponenten die sich hier in diesem konstrukt irgendwie
- einfügen und wie ihr benanntes label ticks linker teil baum l rechter teilbar mehr das ist alle diese drei komponenten
- machen einen nicht lehren binär baum aus und man kann irgendwie sehen warum die ganzen dinge binär baum heißen weil so und knoten nämlich genau zwei genau zwei
- nachfolger oder teil bäume besitzt ja da ist der erste da ist der zweite das ist ein binär beim wort binär steckt schon die 2
- die expedition drin und ihr könnt euch denken wie ein ernährer baum aussieht der hat nämlich in jedem knoten genau ein label ickx und dann drei bäume ok
- alles klar ich denke das war eigentlich schon die die die ganze definition hier an der stelle
- ihr seht hier diese flaggen die ich wieder auf der folie angebracht habe in den letzten körper in den letzten kapiteln und auf den letzten folien hat
- sich diese flaggen markierung so müssen eingestellt immer dann wenn es uns um revisionen ging ja ich habe die weiße flagge benutzt immer dann wenn es um
- rico sohns abbruch gingen und tatsächlich ist der lehre baum und wieso das ende der rezessiven definition dieser datenstruktur binär born wie
- unter einem oder in einem leeren binär baum versteckt sich nichts weiter in der lehre binär warum steht für sich selber das ist der abbruch der rezessiven
- konstruktion und des baumes ja wenn wir nicht lehren baum france haben dann hat er 22 teil bäumen linken und rechten teil baum die selber wieder beatrice of
- these die selber wieder binär bäume sind hier steckt leicht zweimal region brennen ok wo in der liste wir mit eine restliche zufrieden waren haben wir
- jetzt hier zwei teil bäume entwickeln und das macht die struktur der binär bäume eine ecke flexibler als die struktur
- der listen in welcher genau weise halten welcher art wie das definieren wollen dass in wien eher baum flexibler ist als eine liste das werden wir im laufe des
- kapitels noch genauer beschäftigen besprechen ok alles klar wir hatten uns relativ am anfang in dem kapitel über listen und
- eine visualisierung herangezogen einfach um besser bei listen sprechen zu können um dort mit dem finger drauf zeigen zu können hey das ist die liste die hier
- dieses kopf element hat um diese rest liste hast du wer hat und wir haben solche spies aufgezeichnet das war diese visualisierung die zu den listen gehörte
- die datenstruktur binär baum kommt mit ihrer eigenen visualisierung der her und ich würde vorschlagen dass wir im rahmen dieser vorlesung die visualisierungs
- sprache die vokabeln die grafischen vokabel benutzen die hier auf der folie 3 1 geführt sind okay wir werden der notation dafür benutzten energie
- benötigen um den lehrern baum darzustellen den mp3 und dazu werde ich einfach hier diesen kleinen dieses kleine quadrat
- benutzen ja das hat uns keine weiteren eigenschaften passt sehr gut und mtv hat nämlich sonst auch keine weiteren eigenschaften in mp3 trägt kein label in
- mp3 hat keine weiteren teil bäume die irgendwie in ihm irgendwie gespeichert sind ein mp kiel steht einfach nur so für sich selbst
- anders sieht's aus mit nicht lehren binär bäumen okay so nicht ihrer wiener baum trägt auf jeden fall label ich habe dass jemand x0 rheinland um ein
- konkretes label während ziehen das label 60 und natürlich gibt es einen linken und den rechten teil baum und ihr seht schon wie ich die hier wie notieren
- möchte links und rechts vom label hier hängt wie die restliche teil baumstrukturen wie und runter weil ich hier jetzt in dieser notation hier in
- der mitte der slide 3 und wenig weiter rein zoomen wollte was ich denn direkt in diesem teil baum finden werde werde ich hier einfach diese schwarzen
- quadrate benutzen und die schwarzen quadrate tatsächlich so für mich die notation seien für internet und schwarz quadrat befindet sich irgend etwas
- beliebiges irgendein beliebiger teil bauen könnte leer sein könnte aber auch irgendwie einen baum seine idee noch was für sich hunderttausende von knoten mit
- entsprechend hunderttausenden von labels unternehmen weiß ich zu diesem zeitpunkt nicht mein blick mein fokus ist zurzeit auf diesen knoten
- hier mit seinem label 60 und beliebigen teil bäumen lr ok konstruiert wird das ding hier natürlich durch eine konstrukte aufruf make not mit label x0
- links und rechts stehen die entsprechenden teil bäume okay einen etwas konkreteren baum in dem ich genau die anzahl der knoten festgelegt habe
- nämlich genau zwei knoten ja findet mir ganz rechts in der darstellung das ist die gleiche darstellung wie wir sie hier in der mitte befinden gefunden
- haben bloß dass ich in die teil bäume jeweiligen gesucht habe er hier unter dem knoten x0 befindet sich natürlich einen rechter teil baum ok unter dem
- label x0 finde ich den rechten teil baum hier sieht man jetzt konkret okay es ist der lehre teil baumann ist lahm auf der linken seite befindet sich nicht lehrer
- teil baum und tatsächlich findet sich hier relativ die notation für unsere nicht lehren teil bäume wieder jetzt habe ich sie eine stelle gerade
- ein geklingelt okay also genauso wie die datenstruktur ist genauso wie kursiv ist unsere darstellung und die grafische darstellung ok ansonsten würde das nicht
- gut zusammen passen alles klar also ist das hier ein licht ihrer teil baum mit label x1 der 2 teil bäume hat hier sieht man die grafische
- darstellung der teilweise ja sind jeweils zwei mp3s damit ist der baum mehr an der stelle schon fertig wie dargestellt und lässt sich auch relativ
- kompakt konstruieren die konstruktion mit den entsprechenden mp3 und mate not konstrukteuren die findet sich jetzt hier in der
- eingekesselten box dieser baum besteht aus genau zwei knoten mit labeln x1 und es verwundert nicht dass wir genau zwei make not
- konstrukt uhr aufrufe an der stelle finden ok alles klar der oberste knoten der oberste knoten der hier den label x0 trägt der wurde
- konstruiert durch den äußeren macnotes aufruf und tatsächlich trägt hier den label x0 okay der rechte teil bei uns der empathie hier ist der rechte teil
- warum hier sehr entsprechend wie angegeben der linke teil baum der mit label x1 findet sich in seiner konstruktion
- eingestellt hier ok genau so verschachtelt wie die baumstruktur hier oben ist genau so verschachtelt werden hier unten die
- konstrukteuren die make not konstrukteuren und wie an das ist ein teil baum mit label x1 jeweils links und rechts stehen die mp3s
- ihr seht hier die verabredung mp3 wird hier in der darstellung hier auf der folie in et abgekürzt einfach damit auf die folie passt alles klar ja ich denke
- die make not konstruktionen und die grafische darstellung die wir oben drüber sehen passen gut zusammen alles darf das ist die einfache
- visualisierung für binäre bäume die wir benutzen werden die werdet ihr auf dem herzen slide jetzt in den folgenden kapiteln wie sehen die waren immer
- wieder auftauchen hundertprozentig tauchen auf den übungsleitern entsprechenden notationen zu solchen bäumen auf wir werden sie immer in
- dieser entsprechenden grafische notation besprechen okay noch ein bisschen mehr terminologie wird ja auf der folie versprochen und
- tatsächlich haben die einzelnen die einzelnen knoten her die wir in unseren bäumen sehen bestimmte namen je nachdem wo sie sich in den baum befinden an
- welcher position sie sich in den bau befinden gibt es spezifische namen für diese knoten ganz besonders ist dieser knoten hier oben ausgezeichnet der über
- dem nichts weiteres sitzt ja geht das ist der oberste knoten links und rechts hängt davon beliebig große teil bäume jeder knoten 60 und das ist hier ganz
- genauso aber dieser knoten und ausgezeichnet dessen der notation hier und auch der konstruktion der oberste oder der äußerste okay und dieser knoten
- nennt sich die root oder der die wurzeln des baumes okay ihr seht also die informatiker zeichen ihrer bäume mit der wurzel oben und dem rest des baumes und
- wieder unten gezeichnet das ist genau irgendwie 180 grad gedreht das ist einfach die konvention der da draußen findet die wurzel des baumes steht oben
- oder hier die wurzeln des baumes befindet sich im äussersten make not konstrukt okay dann gibt s time teil bäume hier in in unserer mutationen die
- leer sind es gibt bestimmte knoten die nur leere teilweise besitzen ok also dieser knoten x1 hier der hat zwei teil würde wie jeder knoten jeder
- knoten in den binären baum zwei teilnehmer die ware beide leer sind okay ein knoten dessen beide teil bäume leer sind nennen wir auch blatt oder lief not
- ok also x1 ist tatsächlich ein blood knoten ok x0 ist keine blatt knoten denn wir haben zwar einen werden teil baum aber hier auf der linken seite
- befindet sich nicht ihrer tagung x0 ist kein blatt x1 ist ein blatt das jung ist kein blatt das ist ein mp3 alle knoten die keine blätter sind alle kommunen die
- keine blätter sind sind sogenannte innere knoten als sie legen wie im inneren des baumes nicht irgendwie am rand unten unterhalb des baums sozusagen
- ok also alle knoten die nicht blätter sind sind in rück noten und damit hier auf diesen knopf dem bau wir geschaut dass hier dieser knoten x0 hier das ist
- ein innerer knoten er ist also wurzel und innerer knoten gleichzeitig okay wie sieht's aus mit dem knoten x0 hier das ist auf jeden fall die wurzel dieses
- baumes hier in der mitte ob er einen blattes könnte ich erst dann feststellen wenn ich genau darüber bescheid weißt was ich hier in diesem zurzeit
- unbekannten black box oder black jungle kyle bowman und er befindet ich kann zu diesem zeitpunkt noch nicht sagen x0 könnte blatt sein wenn elo der leer sind
- x0 könnten in ra knoten sein wenn sich in ellund oder er hier noch weitere knoten und wir befinden würden okay das ist die terminologie die zu unseren
- binär ball mehr gehört oder allgemeinheit die zu baumstrukturen gehört ein ganz großer schluck wasser
- ok ganz hervorragend ich habe auf der nächsten zeit noch ein paar beispiele mitgebracht für für bäume zwei beispiele
- die uns in den kommenden slide immer wieder wie beschäftigen werden darum haben die sogar im eigenen namen verdient das hier ist der baum t1 und
- das ist der baum t2 die hier aufgezeichnet habe ok ihr seht dass beide bäume jeweils mit drei knoten daher kommen die ich jemals hier mit den
- labels 1 2 und 3 versehen habe auch hier label 1 2 und 3 das sind offensichtlich beatrice of india oder numbers oder wie wir oben
- da sehen in der überschrift das leid das sind zwei beatrice of natural ok alle labels gehen die knoten gespeichert werden sind tatsächlich werte der
- signatur natural natürliche zahlen okay wenn wir ein bisschen auf dem baum tier-1 gucken dann sehen wir das hier wie so ein bisschen rechtslastig ist wer
- die ganzen linken teil bäume die hier in den entsprechenden knoten hängen die sind tatsächlich leer alle linken teil wärme sind tatsächlich leer
- ok damit ist die gesamte interessante struktur aus der sicht eines einzelnen knotens gesehen jeweils immer rechts zu finden ok links gar nicht zu finden
- rechts ist beliebig interessante struktur zu finden in diesem baum ok aus der sicht von 1 befindet sich die gesamte weitere informationen diesem
- baum gespeichert ist auf der rechten seite und aus der sicht des knotens 2 ist es ganz genauso okay sämtliche weitere informationen steht hier
- eigentlich im rechten teil bau dieser baum ist rechts tief - auch nicht das ist eine besondere art und weise diese bäume wie anzuordnen ein rechts
- tiefer bei ok noch mal unsere technologie bezüglich wurzeln innerer knoten und blätter trainiert auf jeden fall ist der knoten mit dem label 1 die
- wurzel dieses baumes knoten mit dem label 3 ist blatt des baumes tatsächlich die beiden teil bei mir sind leer diese beiden knoten hier eins und zwei
- sind keine blätter denn sie haben jeweils nicht länger teil das sind innere knoten okay das maibaum t1 t2 das aufbauen 1 knoten 1
- entschuldigung ist anstelle wenn dieser stelle wurzeln des baumes okay zwei und drei sind jeweils zwei blätter dieses baumes ok und der einzige in druck
- noten der sich in diesem raum befindet ist der knoten mit dem label ein state leid ich auch der wurzel knoten ist klar das ist die das layout dieses baumes t2
- dass mir allgemein so ein bisschen symmetrischer wie balancierter vorkommt wie der baum t1 sehr sehr sehr rechtslastig war recht tief war und
- tatsächlich ist der baum t2 ein sogenannter balancierter bauen okay ein balancierter baum darauf diese definition oder diese benennung bezieht
- sich nicht nur auf diese schöne grafische darstellung die hier für den baum gefunden habe sondern es ist tatsächlich ein formal definierter
- begriff der sagt und ihr seht dass hier auch unten an der auf das leid markiert alle teil bäume ok alle teile die ich auf der gleichen höhe finde
- ok also hier ja das ist die der wurzel diese beiden und rückten die sind schon hier in der höhe etwas niedriger angeordnet wie in diesem winter in
- diesem binär baum alle teil bäume die hier irgendwie auf einer dieser höhe nicht wie angeordnet sind haben die gleiche anzahl an knoten
- ok also wenn ich mir hier diesen knoten jahren schaue und ich gucke mir seine teil bäume an zwei davon hat er dann hat der linke teil baum ein knoten und der
- rechte teil war mal ein knoten okay also in der hinsicht aus der sicht einzige aus der sicht des kunden 21 ist das ganze schon mal balanciert okay aber ein
- echter balancierter baum in einem echten magneten baum gilt es für alle knoten dass die linken und rechten teil bäume einer ebene oder einer höhe hier
- sozusagen die gleiche anzahl knoten haben okay also hier der zweier der tatsächlich zwei teil bäume derweil weiter knoten der 3er auf der gleichen
- höhe jeweils zwei teil bäume die jeweils 0 knoten haben ja tatsächlich das ist eine vollkommen symmetrisch situation das ist ein so genannter balancierter
- bau okay der baum hier ist hundertprozentig nicht balanciert wenn ich auf alle knoten schaue die hier auf dieser ebene leben das ist nur ein
- knoten ja dann hat der linke teil baum 0 kloten und der rechte teil wird ein knoten ja das ist schon im wie aus der balance geraten
- dieser baum ist tatsächlich recht tief ok balancierte bäume sind oft bäume die besonders schöne eigenschaften haben wenn wir algorithmen über solche bauern
- mehr schreiben werden ob wir das im rahmen der informatik 1 hier besonders tief beleuchtet werden kann ich empfehle steht noch nicht sagen
- ab und zu wird das bestimmt mal wie auf den plan kommen und wir werden das system begriff der balancierung noch mal benutzen und wenn wir ein bisschen
- angeschaut haben wie algorithmen auf solchen bäumen funktionieren dann kann man auch schon erahnen warum balance also ein baubudget zwei besonders schöne
- eigenschaften hat ok bäume sind überall diese binär baumstrukturen sind einfach überall ich habe vorhin schon mal gesagt die baumstruktur ist die struktur die
- ich mitnehmen würde wenn ich nur eine mit auf eine einsame insel nehmen dürfte warum ist das so weil die informatik dafür zahllose applikationen kennt wenn
- die bäume gibst baue ich hab mir daraus viele andere datenstrukturen die die informatiker die baue ich mir mit bäumen einfach nach aufbäumen lassen sich viele
- algorithmen ungeheuer elegant ungeheuer effizient implementieren das ist einfach die rezessive datenstruktur die die informatik kennt
- die die black applikationen sind zahllos und die ihr könnt euch denken dass diese liste hier diese liste aus beispiel applikationen die bäume in der
- informatik haben natürlich mit einem fetten punkt punkt punkt durch fortgesetzt werden müsse und ich habe mich richtig schwergetan dieses leid 5
- zu entwerfen um hier eine auswahl von applikationen irgendwie drauf zu packen die irgendwie der vielfalt gerecht wird die man tatsächlich in den baum
- applikationen informatik finde ich habe dieses leid habe ich sieben mal umgestellt und umgeschrieben dinge rausgeschmissen und drauf genommen
- einfach um irgendwie irgendwie nie einigermaßen akzeptable auswahl der vielen applikationen an der stelle zu finden ok auf jeden fall kann man mit
- binär bäumen sogenannte suchalgorithmen session implementieren dazu wandelt man bäume in such bäume um ok sucht bäume sind eigentlich normale
- bäume in deren die labels die wir an die knoten heften nicht in beliebiger art und weise angeheftet werden sondern wenn man mir das label eines stimmt knoten
- zeigt dann kann ich daraus schon wie vorhersagen treffen wie denn die labels links und rechts in den teilräumen unter mir aussehen werde
- und wenn ich solche vorhersagen machen kann kann ich mich bei der suche in solchen wollen manchmal sparen in den linken und oder in den rechten tagung
- wir ein zu suchen okay ich denke solche sucht bäume werden wir irgendwie auf den übungsleitern thematisieren das ist eine sehr effiziente art und weise sehr große
- datenmengen so zu organisieren dass sich ratz fatz nach bestimmten werten den schlüssel werten in diesem bäume wie suchen kann ok wie einige von euch
- wissen eigentlich bin ich kein informatik einser oder record ii oder wie sowas eigentlich bin ich mit meinen jungs hier diesen der stube treiben ich
- bin daten becker okay wenn man intern also ein datenbanksystem reinschaut und es gibt vorlesungen die wir anbieten die genau das machen so und da banksystem
- aufknacken und die datenstrukturen und die algorithmen sich darin finden die mega spannend sind okay man daran findet genau analysiert dann findet man da
- verschiedenste baumstrukturen drin da findet man auch den sogenannten b + baum zum beispiel in allen datenbanksystemen die mir bekannt sind implementiert b +
- bäume sind such bäume die mir erlauben mich in giga terabyte weisen von von daten effizient zu bewegen und zu navigieren
- selbst wenn die größte teil dieser daten sich auf der von der speicher wie zum beispiel ssds oder anderen langsamen speicher formel wie befindet ok also
- keine datenbank systeme ohne die entsprechenden räume die diese systeme benutzen um schnell schlüsselwerte in ihren riesigen datenmengen wie
- aufzufinden ihr geht eigentlich dauernd mit datenstrukturen der form baum um wenn ihr in dem file system eure rechner wie
- navigiert mit change directory oder cd punkt punkt also sich an der aktuellen wir nach oben bewegen je nachdem welche in welchem player von betriebs sehen wir
- unterwegs seid habt ihr versprechen verschiedene möglichkeiten euer file system zu navigieren und genau darauf geschaut so ein file system ist in form
- von einer hierarchie von directories organisiert wird man da genauer drauf schaut und vielleicht wenn wir das auge bis hin zu kneift sieht man die
- hierarchie von feiert in eurem direkt in eurem file system ist in wirklichkeit in form eines baumes organisiert okay das ist eine hierarchie von files
- organisiert wird das ist in wirklichkeit eine ein einbaum datenstruktur die für euch auf eurem sekundär speicher für euch verwaltet wird okay im allgemeinen
- ist die darstellung von hierarchien super geeignet durch die bäume repräsentiert zu werden ja es gibt da verschiedene die regionen wie darstellen
- wollte in informatik vielleicht zum beispiel die vererbung beziehung zwischen bestimmten daten wie zb objekten
- daraus ergeben sich sehr schnell hierarchische und baumart igge strukturen allgemein so ist teil von beziehungen ja also ein teil iv liegt
- vielleicht an der wurzeln eines baumes besteht aus mehreren anderen teilen die wieder sub teile haben die wieder sub sub teilhaben und die könnte ford sehen
- wir aus nicht rasch entsteht und wie man daraus eine baumstruktur bauen kann um sie intern im rechner zu repräsentieren andere strukturen sind von vornherein
- als bäume angelegt worden hat gar keine andere wahl als die bäume zu konstruieren um dieses dokument strukturen zu konstruieren jeder von
- euch hat schon mal von xml gehört von der extensible markup language eine art und weise dokumente zu strukturieren in dem man in systematischer art und weise
- so spitze klammern ineinander schachteln und weiter heraus entstehen baumstruktur nichts anderes kann man an der stelle beschreibe nix html also der aktuell der
- dom oder der der moderne html5 standard der von allen browsern und dem ganzen tag draußen gesprochen wird das ist eigentlich ein bestimmter xml dialekte
- bestimmte art von bäumen das ganze web besteht ausbauen datenstrukturen jason ist andere art strukturiert die die wir auch schon kennen gelernt haben als wir
- mal von der star wars database glaub ich geredet haben da kann man viel essen wie mit ins spiel auch wenn man darauf schaut ist das nicht iranische
- darstellung von daten die in wirklichkeit in baumstrukturen daherkommen was wir in der vorlesung näher besprechen werden und zwar im
- kapitel 12 den summen half men trilogie eine bestimmte art von bäumen die uns erlauben datenkompression wie zu zu implementieren okay also etwas
- passiert gar nichts mehr zu tun hat sondern aus einer ganz anderen ecke kommt nämlich der kompression von großen datenmengen wie sie zum beispiel in jpeg
- standard im mp3 standard im sieb standard gebraucht wird das wird merkel von bäumen von hofmann trees und decodiert und weil das so eine
- interessante applikationen ist werden wenn eigenes kapitel dafür verwenden um da genauer drauf zu schauen und wenn ihr euch die internen repräsentation von
- code von programmen record programmen javascript programmen c program eure lieblings sprache programm in eurem rechner anschaut dann sind diese
- programme intern nicht repräsentiert als lange zeichenketten nicht die zeichenketten die in unsere meditieren oder im editor ein gibt sondern sobald
- er an den intern peter oder einen compiler auf diese programm schaut und ein bisschen struktur in eurem kroos versucht zu erkennen
- werden diese strengen darstellung eure editor darstellung von programm intern im baum darstellung gebrachten sogar term darstellungen die den compiler mehr
- informationen darüber geben mit wo findet sich hier ein ausdruck wo befindet sich ein teil ausdruck wo es in diesem teil ausdruck ein weiterer teil
- ausdruck gespachtelt usw ihr seht schon wieder die baumstruktur niveau und die hierarchien zu zum zuge kommen auch hier spielen bäume eine
- rolle also die die einsatzfelder für bäume sind zahllos einige davon können jetzt in der informatik 1 diskutieren jeder informatiker und jede
- informatikern muss baum fällen werden darum werden auch in informatik zwei weder baumstrukturen verschiedenster art und weise wie diskutieren
- ihr kommt an der diskussion von bäumen 0 vorbei in der informatik okay aber das war mal eine werbe folie für baumstrukturen ja und wenn sie denn so
- super sind dann müssen wir sie auch irgendwie in racket implementieren das ist das letzte was mit euch hier in diesem video in wien auch machen möchte
- ich möchte euch eine möglichkeit zeigen wie man in racket mit den sprach mitteln die wir uns schon jetzt geschaffen haben wien er bäume repräsentieren kann und
- die gute nacht entsteht ist es gibt an der stelle eigentlich überhaupt nichts neues zu lernen wir müssen einfach nur konsequent dass anwenden was wir uns
- einstellen wie schon angedeutet haben hier ist eine vorschlag für eine darstellung von nicht lehren und von lehrern binär bäumen
- ok also ja dann gucken sie doch erstmal wie wir die nicht lehren bäume darstellen das waren knoten dieser form dienen
- label sa stellen müssen und in den linken und den rechten teil wie auch immer der guard sein mag und tatsächlich werden uns dazu records
- neben records die genau drei komponenten haben eine elle komponente die x0 komponente und die er kompetent er wir werden die komponenten allerdings
- läuft brunch label wright branchen ok also bauen uns eine neue rekord die natur die wir not nennen werden und so notar drei komponenten lew brunch label
- wright brunch ok also 60 und r linke baum label und rechter taiwan genau das ist glaube ich auch zu erwarten gewesen mac not und not dazu
- überhaupt nichts weiter zu sagen das ganze ist polymorph weil wir die möglichkeit haben wollen knoten zu erstellen die ihre in den labels die in
- ihren labels meist rings mal julian schmahl listen von pixeln mal was ich beliebige dinge speichern wollen genauso wie polymorphe listen konstrukteuren und
- gebaut haben werden wir uns polymorphe binär baum konstrukteuren bauen ok und not ist die halbe miete da an der stelle alles klar
- ihr seht die entsprechenden signaturen die sich dabei einstellen ja natürlich wird unter konstrukt uhr unter konstrukteur hier drei argumente
- besitzen der linke teil baum das label und der rechte teil baum uns daraus den entsprechenden knoten bau ja und diese lektoren hier lässt man wird uns einfach
- den linken teil baum der signatur prozent heraus operieren und so weiter und so fort hier gibt es in der stelle überhaupt gar nichts neues zu lernen
- ok wie sieht es aus mit dem leeren teil baum der lehre teil baum dafür werden wir uns auch nur eigene signatur schaffen an der stelle ist überhaupt gar
- nichts podium auf es gibt nämlich genau einen leeren teil baum der eine lehrer teilen die wir benutzen werden um die konstruktion von allen beliebigen
- bäumen wie jeweils abzuschließen und den unteren enden sozusagen es baum ist genauso wie es genau eine lehre liste gab gibt es einen leeren bau okay der
- wird die signatur haben die dmt ok und ihr seht ihr die entsprechende konstrukteuren hier weichen wir ganz ganz wenig von unserer von unserer von
- unserer notation oder von unserer konvention auch die konstruktion zu benennen wir nennen das die dinge einfach mc pg und nicht mehr gewährt
- ecri okay und ja das ist der entsprechende dass die entsprechende prädikat dazu so ein lehrer baum hat null eigenschaften hat keine weiteren
- eigenschaften ihr seht die liste der eigenschaften der record komponenten die wir an der stelle speichern würden ja die ist lehrstelle und genau so sieht
- dann auch mit unserem konstrukteurs das ist der mcafee konstrukt das ist nur 0 stetiger konstrukteur der hat gar keine weiteren argumente zu bekommen
- er wird einfach unseren mtv konstruieren ohne das irgendwie weitere argumente wie benötigt samstag damit haben wir die entsprechenden die
- ansprechende bausteine in der hand um tatsächlich und solche bäume zu konstruieren dann fehlt uns nur noch die signatur
- beechey auf t genau wie wir damals list of her gebaut haben fehlt uns jetzt noch petri auf t das ist das letzte was ich euch hier
- zeigen will in der auf der slide ist es okay also die budget auf die signatur schön parametriert damit wir die labels der des der signaturen erstellen wie
- flexibel einsetzen können petri oft hier wird das ganze gebaut das wird eine signatur sein so ein binär baum ist entweder leer
- ok darum kommen wir mit einem mixer er ist entweder leer und dann ist das hier die signatur des leeren baumes oder er ist nicht leer
- dann ist es einen knoten ok und die signatur der knoten haben ja gerade eingeführt das ist die polymorphe novikov signatur links steht rego sie
- fand ein entsprechender link hat ein baum hier steht das label signatur t und die hier steht der rechte teil bauen ihr seht wie es schon öfter gemacht habe
- die rezessiven beziehungen die sich hier aufbauen oder die doppelte region die sich an der stelle findet bei dem binär bäumen die finanzielle direkt in der
- definition mit unserem budget oft eh wieder okay jeder knoten enthält zwei teil bäume okay
- das wird bei den beiden funktionen die wir nachher über über bäume und konstruieren werden zu zweifacher rekursen wie ihr euch denken könnt ich
- habe euch in einem der kapitel schon gepredigt dass die struktur der daten ja die struktur der signaturen die wir gerade aufbauen
- die struktur der funktionen bevor schreibt wir haben ihn rezessive datenstruktur vorliegen die funktionen über daten struck dieser daten kultur
- werden genauso riesig sein die datenstruktur ist doppelt so tief wie ihr sehen könnt linker und rechter teilbar genauso
- doppelt oder zweifache kursiv werden die meisten die typischen funktionen sein die wir über diese datenstruktur über den binär bäume wir konstruieren werden
- genau das ist das was diese box hier sagt und tatsächlich der hier ist nicht übertrieben eine ungeheuer wichtige einsicht okay also es wahrheit hat sich
- wieder die datenstrukturen bestimmen die bestimmen die struktur der berechnungen die visa daten struktur wie ihr durchführen werden okay was cooles wir
- werden sehen dass sich oftmals potenzial für parallelität ergibt weil so eine funktion oder ein algorithmus gleichzeitig von einem knoten aus ihnen
- den linken und rechten teil baum potenziell absteigen könnte einige der algorithmen können das nicht viele der algorithmen können das potential machen
- und könnten zwei cpu us einsätzen und zwei rechenressourcen in unserem rechner um sich über das parallel um den linken und den rechten teil baum zu kümmern das
- war bei den listen nicht ganz so listen sind fast wie unehre bäume jedes element hat eine entsprechende westküste in dir würden wir abzutauchen
- haben da ist das potenzial für parallelität gegeben aber nicht ganz so offensichtlich hierbei den beerbaum springt es einen geradezu an
- ok ab und zu wenn wir das noch eine stelle erwähnen ein bisschen convenience gar nicht nur noch statt wie dieses make mtv ihn
- schreiben zu müssen ja den den konstrukteur für unseren lehrern baum und zwei konstrukteur als 0 stetige funktion hier in runden klammern
- eingefasst ohne jegliche weitere argumente werde ich mir einfach hier wie gewünscht die den identifier mp3 besorgung der mir
- genau den einen hier ist extra vogel den einen leeren baum konstruiert den ich dann unter dem namen mtv dann tatsächlich immer wieder leicht wieder
- verwenden kann ok so wie es waren wie in diesem video überhaupt noch gar nicht trüben in doktor racket ihr das machen wir jetzt
- noch schnell aber noch ganz kurz ich möchte die ganzen definition zum beispiel definition der es nicht ihrem baums oder des knotens des knotens mit
- seinem left branch und rheydt brunch und seinem label die möchte ich hier noch hätte meinen was rüber kopieren da habe ich so ich habe auch die entsprechende
- definitions im leeren bauen da da ist es daten unter lehrer baum man sieht hier so ein mac mp3
- tatsächlich das ist null städtischen struktur genau so wie wir sind wir frei von angesagt haben und die convenience ja den einen leeren baum und wie einfach
- konstruieren zu können einfach durch eine idente feier mp3 die möglichkeit schaffe ich mir hier ihr seht hier wieder nur stetige konstrukteur einmal
- für mich aufrufen wird das ergebnis dass sich dahinter befinden wird das ist der lehrer bei dem die queen ich hab jetzt benutzen kann
- ok ja und dann noch die signatur die rekurse signatur die parameter sie trikot siwe signatur für petri auf t ok also auch hier nichts neues zu
- beobachten das ist genau das was wir eben gerade auf der auf der es leid gesehen haben ja so ein binär baum kann genau zwei formen annehmen darum hier
- die mixed sie natur wären wir sehen könnte mal ganz kurz übersetzten ob ich da schon wie fehler ein gebastelt haben ein funktioniert alles wunderbar dann
- können wir jetzt zum abschluss dort kurz die die bäume die in wien eher baum t1 den recht tiefen binär baum definieren den gti auf natural leben wir eben schon
- auf das leid gesehen haben ich werde mal ganz gut auch die slide zurück und zeigt in der ich noch mal die ist unser bond der einst von dem ihr von dem rede ich
- gerade an der stelle ok hier baut er ans den würde ich jetzt gerne konstruieren mit hilfe der mac notebook mit hilfe der mtv ii
- konstrukteuren die ich mir geschaffen habe um den tatsächlich auch in recke tipp wie man zum leben zu erwecken okay also das wird also in die fein t1 das
- sehr gut dann habe ich den einsatz zur verfügung für den ganzen rest des chapters denn der pt 1 warum kommt ab und zu malen beispielen vor
- ok der oberste knoten der wurzel knoten von meinem vom einen baum der hatte der hatte das entsprechende label 1 ok also muss doch und wie der
- baum in seiner konstruktion und wieso aussehen ok ja also hier ein wurzel knoten mit label 1 okay hier ist der linke teil beizutragen hier ist der
- rechte teil beizutragen okay ich weiß der linke teil baum in diesem t1 baum der rechts tief war rechtslastig war die winken time das waren immer die mdgs
- okay aber hier rechts niveau ist die punkte stehen da die weitere interessante struktur gefunden okay zum beispiel weiß ich dass der
- nächste knoten hier diese form hatte der nächste knoten hatte das label 2 und der linke teil baum von dem ding der wahl wieder leer
- ok alles klar der rechte teil da dagegen die entsprechende interessant weitere informationen zum beispiel der teil baum der das blatt 3 beinhaltet okay also
- hier das ist der knoten mit dem label 3 und ich weiß noch aus meiner diskussion der entsprechenden slide dass der knoten mit dem label 3 1 blatt knoten war ein
- blatt knoten er trägt links und rechts jeweils dem mp3 als teil damit ist dass die definition eines
- baumes t1 diesen rechts tiefen baum den ich gerade auf das leid gesehen habe mal schauen ob das im wiki of natural ist laut unserer definition ist es okay
- ja weil ich diese situation nun dass mich die co2 leiten die diese situation bei der konstruktion von bäumen immer wieder vor treffen werde
- ich möchte blätter konstruieren ja also blätter dienen label tragen aber links und rechts einen leeren teil baum werde ich mir ein bisschen convenience noch
- bauen eine hilfsfunktion konstruiere ein blatt mit labels ok und diese funktion für die make life nennt du gibst mir ein label
- dann baue ich daraus kleinen binär baum einen kleinen binär warum einer der aus einem blatt alleine so besteht das müsste eigentlich möglich sein mit lief
- okay du gibst mir den labeln labels zum beispiel dann braucht ihr daraus einen knoten der nmt trägt der einen seite dann das label ickx und auf der anderen
- seite ebenfalls das den entsprechenden lehren baum und das ist die art und weise wie ich ein blatt mit labels konstruieren das könnte ich dann hier
- oben gleich um die zum einsatz bringen auch lass uns doch hier oben einfach stehen und etwas einmal explizit gesehen haben und wir sehen wie wir auf dieses
- pad angekommen sind dass wir tatsächlich blätter konstruieren wir können ja weg lief gleich einsetzen wenn wir jetzt und einen zweiten baum noch konstruieren
- wollen der zweite baum war der finanzierte baum hier ist der organisierte baum mit drei knoten 1 einer wurzel als einziger
- innere knoten 23 sind blätter ok superschön balanciert links und rechts die gleiche anzahl oder gleiche menge an informationen ok alles klar das wird
- also der bau mir hab ich das geschrieben bienen er warum genau also das ist der wien er beim t2 okay von den slides das wird kaum sein der ebenfalls mit
- natürlich zahlen labels daherkommen die 2 er hatte kurze knoten der ebenfalls das label 1 trägt genauso muss die kiste aussehen und links von der
- einst dahin blatt dahin ein blatt mit label 2 und rechts davon plattenlabel 3p es doch eine konstruktion schon einigermaßen übersichtlich und man kann
- schon so ein bisschen erahnen dass hier tatsächlich eine balancierte struktur 1 1 stellt sozusagen links von der einst unrecht von der 1
- hängen eigentlich identisch symmetrisch konstruierte strukturen okay war einmal kurz ausführen der 1.2 sind definiert worden das
- einzige bisschen wehmut dass hier um die ganze kiste rein schippen muss ist wenn ich mir in der regel diese bäume auszugeben ausgeben also obwohl ich hier
- in der macht der abstraktion bin die betriebe der baum signatur ist keine eingebaute signatur in racket es gibt keinen besonderen support dafür keine
- besondere ausgabe oder eingabe formate dafür wenn ich mir den entsprechenden baum t1 hieraus geben lasse dann sehe ich hier ja das ist max not mit wurzel 1
- links davon hängt der lehre baum rechts davon etwas interessanteres was tieferes was wahrscheinlich um funde 2 trägt und war die idee schon das ist ungeheuer
- schlecht zu passen ist zu lesen dass märchen c2 bauen dazu ausgebe dann wissen wir dass t1 und t2 in wirklichkeit nicht dieselbe bäume sind
- der eines rechts tief der anderes passiert aber dass aus diesem klammer aus diesem klammer bergen raus zu lesen und sofort im blick dafür zu entwickeln
- mensch das ist tatsächlich das ist tatsächlich passiert der bohrstelle ungeheuer schwierig darum werden wir in einem der kommenden videos nimmt ein
- bisschen zeit darauf investieren und eine routine zu bauen die uns solche bäume in einer art und weise ausgeben wird hier in der apple die einem nicht
- kopfschmerzen bereitet sondern an der man sofort die struktur der bäume und der tat so dass sofort wie ablesen kann ok solche pretty printing routinen zu
- bauen ist ein interessantes thema an sich darum ein eigenes video nachher dazu werden im laufe dieses kapitel 11 sehen aber nicht mehr jetzt das video
- läuft schon 43 minuten und 40 sekunden auf jeden fall zeit um deckel drauf zu machen ich danke euch für die aufmerksamkeit das ist das zdf und wir
- werden auch weiter gewonnen sprechen ich hoffe ihr bleibt dabei
Zum Nachlesen
BinärbaumBinärbäume sind in der Informatik die am häufigsten verwendete Unterart der Bäume. Im Gegensatz zu anderen Arten von Bäumen können die Knoten eines …
Baum (Datenstruktur)In der Informatik ist ein Baum (engl. tree) eine Datenstruktur und ein abstrakter Datentyp, mit dem sich hierarchische Strukturen abbilden lassen.
B-BaumEin B-Baum (englisch B-tree) ist in der Informatik eine Daten- oder Indexstruktur, die häufig in Datenbanken und Dateisystemen eingesetzt wird.
Binärer SuchbaumIn der Informatik ist ein binärer Suchbaum eine Kombination der abstrakten Datenstrukturen Suchbaum und Binärbaum. Ein binärer Suchbaum, häufig abgekürzt …