herzlich willkommen zur nächsten vorlesung diesmal geht es um bäume wir kennen schon listen und verkettete listen die idee von der verkettung wären wir wieder aufgreifen da wo einer verketteten liste jeder knoten bis auf den letzten genau einen nachfolger hat lassen wir jetzt für bäume zu dass es mehr als einen nachfolger geben da da wo die liste eine sequenzielle aneinander jung war verzweigen wir jetzt in die richtung nach unten da wo wir bisher eine lineare datenstruktur eine liste hatten die wir einfach von vorne nach hinten durch laufen könnten kommt jetzt noch was dazu üblicherweise stelle ich
mit bäumen hierarchische beziehungen da und wir kennen schon beispiel aus dem wintersemester als wir die objektorientierung uns angesehen haben und gesehen haben dass es sinnvoll ist klassen in einer vererbungslehre zu modellieren und unser beispiel war die abstrakte figur immer gesagt dann eine ellipse ist eine figur ein rechteck ist eine figur ein dreieck ist eine figur ein kreis ist eine ellipse ein quadrat ist ein rechteck usw die vererbung beziehungen vom allgemeinen zum spezielleren von oben nach unten haben wir in einem baum modelliert wobei klar ist dass es natürlich mehr als eigene figur gibt das heißt wir
haben hier mehr als eine verzweigung nach unten zu den immer konkreteren implementierungen ein anderes beispiel ist das dateisystem das könnte auch alle hier ist ein ausschnitt aus der verzeichnisstruktur wo ich meine folien erstellen also ich habe ein verzeichnis algorithmen und datenstrukturen da liegt der quellcode für die folien da liegt aber auch der quellcode für die programmierer beispiele der definiert ein java package a und d ich hab auch wieder unterverzeichnis und in diesem unterverzeichnis sind wieder weitere unterverzeichnisse wir verzweigen also wieder von oben nach unten ein anderes anwendungsbeispiel von bäumen ist die darstellung von thermen dass
wir hier in der vorlesung auch immer wieder als beispiel verwenden wir haben das tatsächlich im schule gemacht haben das rechen baum genannt und haben damit punkten verstrich und klammern setzen vorrang von operationen geübt bzw das visuell dargestellt indem beispiel hier thema der term beschreibt ein summe der linke summend ist ein 2 der rechte sondern ist ein produkt das besteht aus den faktoren drei und vier tatsächlich können nicht nur therme als bäume darstellen sondern alle arten von dokumenten die hierarchisch gegliedert sind und das sind sehr viele denkt man zum beispiel an im text den wir schreiben
und untergliedern in einzelne kapitel abschnitte unter abschnitte usw das ganze könnte formal oder formaler auch machen in html oder xml oder latex oder einer anderen beschreibungssprache oder einem dateiformat baggern bäume codiert so wie wir hier in welchen baum zur darstellung von thermen verwendet haben könnte aber auch kompliziertere dinge darstellen zb programm brot ihr kennt das vielleicht aus eurem editor woher dinge auf und zuklappen könnt also euch für jede klasse nur die methoden namen beziehungsweise signaturen anzeigen lassen könnte und die konkrete implementierung auf klappt nur dann wenn er sie sehen wollte und das ganze geht in
beide richtungen noch weiter dieses auf und zuklappen oder falling von code im editor benutzt natürlich einen baum und wir machen immer an einem knoten entweder nur den knoten selber oder alles was noch dranhängt sichtbar das ganze funktioniert natürlich nicht nur zum visualisieren von code sondern der java compiler verwendet auch baum datenstrukturen der schabak compiler übersetzt java code in beit code und ein zwischenschritt ist die erzeugung einer sogenannten abstrakt sind extremes wenn uns das in sehr einfachen form noch anschauen ja wo auch wie in dem rechen baum alle operationen die in diesem programm definiert sind codiert
werden nur dass man natürlich sehr viel mehr operationen zu lassen als hier ein beispiel um uns nur produkt und summe anschauen als nächstes einige begriffe zu bäumen den ersten kennen wir schon ein baum besteht aus einzelnen knoten auf englisch notes genau wie unsere verketteten listen auch die knoten sind miteinander durch kanten auf englisch ages verbunden technisch genau das gleiche wie die verkettung in der liste nur haben wir bei der liste dem ganzen nicht extra den namen gegeben jetzt sagen wir kannten dazu bäume wachsen und informatik üblicherweise von oben nach unten also nicht so sondern so
rum das heißt der oberste knoten die wir hier sehen dass es die würze von unserem baum wir können uns das so vorstellen dass mit den baumwurzeln knoten aufhängen was ist jetzt ein baum wir können den baum rico sie definieren ein baum ist ein knoten der wiederum andere knoten als kinder haben kann die anzahl der kinder ist dabei nicht beliebig sondern wir legen eine maximale anzahl fest dass es der sogenannte verzweigung ska auf englisch oft degree von dem baum im beispiel hier ist dieser maximale verzweigung skat zwei der knoten hat zwei kinder der knoten hat zwei
kinder der knoten zwei kinder der knoten hat einst ein kind und diese vier knoten haben jeweils kein kind jetzt wenn man die eigene richtung gegangen vom knoten vom elternteil zu den kindern wir können natürlich auch rückwärts gehen jeder knoten ist mit einem oder keinen eltern knoten verbunden alle knoten die wir hier sehen bis auf den obersten bis auch die wurzeln haben genau einen helden knoten die wurzel als einziger knoten hat keinen eltern knoten damit ist ein baum auch ein zusammenhängender zyklen freier graf den ausdruck wärmer in einigen kapiteln später kennen lernen wir immer noch mal
zu unserem beispiel von dateisystemen zurückgehen bedeutet das dass wir keine links hat links oder symbolik links zu lassen das bedeutet dass wir zum beispiel sowas hier was man im unix dateisystem mit zb allen strich es machen könnten also so zu tun als wäre ein unterverzeichnis von src dass das in den baum nicht zulässiges das was ich jetzt gezeichnet hat ist kein baum mehr sowas hier darf nicht passieren ich hab die begriffe eltern und kind schon verwendet wenn man von oben nach unten im baum gehen dann haben wir weiter oben die eltern und nach unten kommen
jeweils die kinder auf englisch sprechen wir von parent und chats oder titel ich habe gerade eben angesetzt und gesagt wir können den baum rezessiv definieren das bedeutet auch dass jeder knoten gleichzeitig einen teil baum definiert und das ist der baum der an diesen knoten als wurzel aufgehängt hat also wenn ich an diesen knoten hier stehen dann kann ich mir vorstellen dass ich diese kantige kappe oder definiert mit dieser knoten auch diesen teil baum wenn ich mich an den anderen knoten stellen hier her könnte jetzt auch hier wieder karten und habe hier auch wieder ein teil
baum also jeder baum besteht damit auch regressiv aus einzelnen teil bäumen oder sat 1 wir haben in jedem baum einen ausgezeichneten knoten das ist die wurzel das ist der knoten der keinen eltern knoten hat es gibt einen davon an diesen stellen wir uns vor ist der baum aufgehängt und an anderen ende haben wir die sogenannten blätter ein blatt auf englisch lief ist ein knoten der keine kinder mehr hat also alles was hier mit dem stern oder jetzt grün markiert ist das sind blätter wir verwenden manchmal auch den ausdruck dass ein blatt ein sogenannter externer knoten
ist und dass alle anderen knoten sogenannte interne knoten sind ich habe alle bäume hier schon so skizziert wie was üblicherweise visualisieren und zwar so dass jeder knoten auf seine entsprechenden ebene manchmal sagen auch niveau auf englisch level liegt und üblicherweise fangen wir bei der null an zu zählen das bedeutet dass die wurzel ganz oben auf der ebene null liegt und die direkten kinder der wurzel auf ebene eins deren kinder also die enkel der wurzel auf ebene 2 die urenkel auf ebene 3 und so weiter und so fort so dass wir von ebene zu ebene jeweils
eine kante mehr durchlaufen müssen dieses durchlaufen bringt uns auch schon zum begriff von einem pfad einfahrt ist eine folge von knoten die durch kanten verbunden sind üblicherweise gehen wir genau in eine richtung die wir mal an von buch von unten nach oben oder von oben nach unten in den baum können wir dabei keinen knochen doppelt erreichen also dass wir zum beispiel ist einfach von der wurzel zu diesem knoten so wie bäume definiert haben bedeutet das dass zu jedem knoten tatsächlich ein genau einfahrt zur wurzel hin also von unten nach oben existiert und umgekehrt natürlich auch
ich erreiche jeden knoten auf genau einem möglichen pfad von oben nach unten von der wurzel aus also zum beispiel diesen knoten hier wenn ich dabei zähne wie viele kannten ich durchlaufe also wie viele ebenen ich maximal erreiche wenn ich von der wurzel bis zu den entferntesten knoten gehen das müssen blätter seien dann ist das maximum aus dieser anzahl die höhe des knotens also damit die anzahl ebenen oder wenn man von null anfangen zu nummerieren die der index der letzten ebene +1 wir werden die meiste zeit eine bestimmte klasse von bäumen betrachten unter sind sogenannte binär
bäume oder binary tree was bedeutet dass ein binär baum ist ein baum mit verzweigung skate 2 das heißt jeder knoten hat höchstens zwei kind knoten da es höchstens zwei knoten sind ist es leichter nicht 0 1 oder 1 2 durch zu nummerieren sondern wir können das ganz anschaulich als das linke und das rechte kind bezeichnen bemerkung ein baum mit verzweigung skaten heißt auch ein nrk sie immer verzweigung scart zwei das happy the prefix oder bei wem binary tree beziehungsweise binär baum ein binär baum ist voll wenn jeder knoten entweder keine kinder hat dann ist dieser
knoten ein blatt oder wenn er genau zwei kinder hat schauen wir uns ein beispiel an dieser baum ist ein voller binär bank die wurzel hat zwei kinder dieser knoten ja hat zwei kinder die restlichen drei knoten sind blätter die haben keine kinder mehr ein voller binär baum heißt vollständig wenn zusätzlich noch alle blätter auf der gleichen ebene sind das ist hier nicht der fall können den baum vervollständigen indem wir diese beiden kinder noch mit rein nehmen es ist klar dass im vollen binär baum jeder innere knoten genau zwei kinder hat denn es gibt ja nur
knoten mit genau zwei kindern oder keinen kindern die ohne kinder das sind die blätter und gleichzeitig wissen wir dass ein vollständiger binär baum der höhe m2 hoch n - 1 kloten hat er wird so locker flockig gesagt wir wissen dass schauen uns kurz anderem dass auf der ebene 0 bei der wurzel habe ich ein ich habe jetzt einfach mal behauptet wir wissen dass das ist schauen wir uns gerade an warum oder was das bedeutet dass ein baum der höhe m 21 knoten hat auf der ebene 0 habe ich die wurzel das ist ein knoten auf
der nächsten ebene habe ich die beiden kinder der wurzel das um zwei knoten auf der nächsten ebene habe ich die enkel der wurzel das sind die kinder der kinder ich habe zwei kinder jedes hat wiederum zwei kinder also habe ich zwei mal zwei sind vier knoten und so weiter und sofort mit jeder ebene verdoppelt sich die anzahl der knoten das heißt ich habe auf ebene 0 20 auf ebene 120 1 auf ebene 22 hoch zwei und so weiter viele knoten wenn ich wissen will wie viele knoten ich im baum hab da muss ich über all
die zu mir das heißt ich behaupte gerade das wenn wir über alle ebenen von null bis auf summieren die anzahl der knoten auf dieser ebene da sind zwei hoch dann ist das ergebnis zwei hoch endlos 1 - 1 ich habe von null bis ein zoom irrt das heißt ich bin hier von der höhe von 1 ausgegangen ich habe sich um 1 verschoben ich habe hier eine höhe von enplus 1 angenommen umgekehrt hätte ich auch von null bis minus 1 auf summieren können ich habe die formel so hin geschrieben weil wir haben die schon mal gesehen
als wir uns beim vector überlegten was die amortisierten kosten sind wenn ich jedes mal wenn ich vergrößern um kopieren muss die größe des rektors verdoppeln genau die gleiche form und jetzt wollen wir mal kurz nachrechnen beziehungsweise zeigen dass das auch tatsächlich stimmt ihr müsst mir das natürlich nicht ungesehen glauben wollen wir beweisen dass weber und wir wollen es auch zwei art und weisen tun das erste ist eine wiederholung vom letzten semester wir verwenden die vollständige induktion bietet sich in dem fall an wir kennen das ergebnis schon die behauptung und jetzt wollen wir zeigen dass das
tatsächlich stimmt wir machen das wieder in drei schritten der erste ist der induktions anfang der einfache fall das ist in dem fall denn gleich null also es gibt eine ebene die nolte ebene wir haben also ein baum der höhe 1 für englich 0 habe ich in der summe nur noch einen zu machen nämlich zwei hoch 0 und das ist eins und das ist auch richtig der baum sieht so aus der besteht einfach nur aus dem bezirk noten und das ist ein knoten der zweite schritt ist auch ganz leicht unsere induktions voraussetzung sagt das behauptung gilt
gilt für alle kleiner gleich in also für alles zwischen 0.20 binder induktions annahme ist und jetzt macht man als letzten schritt den induktions schluss wir zeigen dass das ganze auch noch für en plus eins gilt das muss man einfach hin schreiben als wir summieren jetzt vom gleich null bis plus 1 über zwei hoch wie jetzt haben einen summenden mehr dazugekommen gespalten denn einfach nochmal ab ich schreibe ihnen zuerst da muss ich nicht klammern setzen bzw die sanierung ist klar dass es zwei hoch endlos 1 unser letztes mitglied plus gleich null bis ein über zwei hoch
die summe die wir gerade von handeln so jetzt verwenden wir unsere induktions voraussetzung denn nach induktions voraussetzung wissen wir dass dieser termin 2 hoch 1 + 1 - 1 und das heißt also wenn da stehen zwei auch in plus einschreiben +2 hoch + 1 - 1 ist gleich jetzt haben wir hier zwei mal zwei hoch in +1 also - 1 das heißt wir an insgesamt zwei hoch n +2 -1 und das ist genau das ergebnis das wahr haben wollen wir haben also gezeigt dass wir für n 1 auch wieder die gleiche formel rausbekommen dies machen
wir als ergebnis 2 12 - 14 knoten wenn ich die höhe um 1 erhöht habe und dabei das immer und immer wieder machen können haben wir das jetzt für alle vollständigen linear bäume gezeigt es gibt noch eine andere möglichkeit das zu zeigen an der stelle braucht man eine kreative idee bei der vollständigen induktion mussten wir einfach nur rückwärts rechnen also wir wollen schauen was kommt heraus wenn ich die zweier potenzen zwei hoch wie gleich null ist ein auf summiere und ich nennen diese summe sn wie sie diese summe aus naja das 2 0 also 1
+ 2 1 und 2 des zwei quadrat sind 42 13 8 und so weiter bis zwei hoch ein ich nehme jetzt die gleiche summe noch mal und multipliziert das ganze einfach mit 2 was kommt dann raus dann habe ich 24 plus 8 + 16 plus und so weiter bloss zwei hoch + 1 denn diese 1 x 2 gibt die zwei diese zwei mal zwei ergibt vier diese vier mal zwei gibt die 8,8 wird die 16 kostet zwei wochen wird zwei hoch ein plus 1 das ganze ist natürlich gleich zweimal sn jetzt kommt der eigentliche trick
ich nehme zwei sn und sie davon sn apa wenn ich das so macht dann sehen wir sofort zwei sn - einmal sn gibt als differenz tatsächlich sm macht das ganze hier auf der rechten seite auch noch mal an was einmal kurz unter einander schreiben dann habe ich zwei sms 24 plus 8 plus unserer +2 hoch + 1 darf und sich ab sn das ist eins plus 24 plus und so weiter +2 hoch m und jetzt sehen wir schon bei dieser summe werden diese man die ich versucht habe untereinander zu schreiben immer gleich zu null und
zwar von der 2 bis 2 hoch n und was übrig bleibt ist diese -1 hier und am ende zwei hoch denn +1 und damit sie mal fertig das ist unser ergebnis zwei hoch im plus 1 - 1 wir werden diese formel tatsächlich noch öfter brauchen deswegen sollten dass wir uns auf jeden fall merken und es ist auch nicht schlecht zu wissen wie muss zeigt bzw dass man mit vollständige induktion sowas sehr schnell zeigen können damit sie mal fertig für dieses einführungs kapitel zu bäumen und wir machen im nächsten kapitel mit binär bäumen weiter