Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Bäume / Binärbäume in der Informatik (Dynamische Datenstrukturen)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 144 Zeilen
- hallo alle zusammen wir haben uns in den letzten sitzungen mit dynamischen datenstrukturen beschäftigt dynamische datenstrukturen ist eine bestimmte art
- daten zu speichern und zwar auf eine art und weise so dass wir beliebig daten dranhängen können deswegen nennen die sich auch dynamisch also die
- datenstruktur kann immer weiter anwachsen ich kann weitere daten einfügen anhängen usw heute schauen wir uns die dynamische
- datenstruktur der bäume an was ein baum ist das erklärt eigentlich der begriff und auch dieses wort schon sehr anschaulich haben wir uns hier das bild
- des bäumchens war an einen baum hat eine wurzel und aus der wurzel kommen natürlich viele erste raus die erste verzweigen sich weiter und an diesen
- ersten da können auch blätter dranhängen wo brauchen wir das am computer das sehen sie beispielsweise hier bei der strukturierung von daten auf der
- festplatte oder auch auf ihrem smartphone ich habe jetzt zum beispiel den ordner eigene dateien und wenn ich da rein
- gehen dann spaltet er sicher weiter auf ich habe hier beispielsweise einen unterordner der heißt informatikunterricht ein unterordner
- bilder musik und so weiter also wie sie wissen dass gibt wirklich ich zeige ihnen das mal also hier einen ordner wie ich in etwa auf einem windows system
- habe also hier meine eigenen dateien wenn ich da reingehen dann habe ich ja unterordner und ich kann natürlich in einen dieser unterordner auch wieder
- reingehen ich kann den öffnen und dann geht es eben weiter das heißt sie sollten erkennen dass es durchaus sinnvoll ist daten in dieser
- art und weise zu strukturieren das heißt ich öffne etwas und dann geht es weiter ich habe einen verweis auf weitere elemente die sich aufspalten wie bei
- einem baum das zu verstehen ist also sinnvoll wenn man so eine datenstruktur programmieren muss hand aufs herz wir müssen das nicht programmieren wir
- werden das nie programmieren insofern werden wir jetzt ganz viele begriffe lernen ob das so schrecklich sinnvolles darüber
- kann man sich streiten wenn man nur begriffe lernen die man nie anwendet aber die gute nachricht ist es ist ziemlich leicht werden sie gleich sehen
- gucken wir uns mal an welche begrifflichkeiten hier wichtig sind dieses blatt das sich hier einsätze finden sie natürlich wie üblich
- im internet auf der website informatik bw.de
- hier gibt es dann nämlich die dynamischen datenstrukturen hier und da gibt es die bäume da finden sie hier dieses arbeitsplatz und das video
- das ich gerade erstelle das werde ich auch auf meiner eigenen webseite dem informatik keller da noch unterbringen wenn ich hier bei programmierung und
- dynamische datenstrukturen aber das video gerade schauen haben sie es gefunden wichtiger dürfte für sie das arbeitsblatt sein dass wenn sie dann
- wahrscheinlich auch im informatik keller finden oder hierauf informatik b g punkt de www berufliches gymnasium ok werfen wir also mal einen blick auf diese bäume
- und auf die begriffe die man bei den bäumen kennen muss es sind zwei begriffe die wir auf jeden fall kennen müssen wenn wir uns dieses
- bild hier mal anschauen wie sich beispielsweise hier dieser musik ordner verzweigt in diesem baum in diese unterordner dann sehen wir erst mal
- diese symbole mit den ellipsen das netzwerk die knoten uns diese knoten sind verbunden über kanten also die kanten sind diese linien
- zwischen den knoten knoten kannten ok können wir uns merken hier steht dann auch noch mal eine definition wann wir überhaupt von einem
- baum sprechen und baum liegt dann vor wenn es zwischen zwei beliebigen knoten immer nur einen einzigen weg gibt dh wenn sie sich das mal überlegen was
- also verboten wäre das wäre kein baum mehr wenn plötzlich hier diese zwei knoten noch zusammenhängen würden
- also wenn die knoten zusammenwachsen würden ist in einem baum ja auch nicht so dass die blätter wieder zusammenwachsen
- also sie können jeden knoten durch genau eine kante einen weg erreichen so es gibt aber noch mehr begriffe die
- wir kennen müssen ein begriff hatte ich schon mal verwendet im hinblick gerade auf das bild des baumes ganz oben bei uns ist die wurzel ist übrigens anders
- als bei einem echten baum in der natur bei einem echten baum in der natur ist die wurzel unten wir kippen unsere bäume aus praktischen gründen weil es für uns
- halt leichter ist diese struktur anwachsen zu lassen nach unten das platz geht halt nach unten weiter aber das prinzip ist gleich alles geht
- aus von einer wurzel die wurzel verzweigt sich weiter was müssen wir noch wissen die eltern die eltern oder der eltern knoten ist ein knoten aus dem
- weitere knoten abgeleitet werden oder die hier von dem eltern knoten kann ich zu weiteren kinder knoten springen und da habe ich
- schon den wichtigen beruf genanntes kind also das hier ist das kind dieses eltern knotens
- die knoten die dann sich nicht weiter verzweigen die also ganz unten in unserer struktur sind die nennen wir platz also knoten die keine kinder haben
- sind blätter okay was haben wir gelernt wurzel knoten sowieso dass es ein eltern knoten von diesem kind und diesem kind und das ist ein eltern knoten von diesem
- kind und diesem kind das hier sind blätter weil sie sich nicht weiter verzweigen dann können wir noch zwei bäume
- identifizieren ein traum ist ein knoten und alle seine kinder also wollen wir das mal hin dass da ist ein teil baum
- und das ist ein teil war was kein teil wäre ist zb dieses da das hier ist kein teil warum warum steht er da in zeil baum ist ein knoten
- und alle seine kinder haben wir plötzlich dieses kind hier vernachlässigt also das wäre kein teil dem alle kinder müssen dabei sein
- war schon mal begriffen sind ich kann auch die höhe eines baumes präzise bestimmen man fängt bei der wurzel an zu zählen da geht es bei 1 los und ich
- zähle jetzt einfach die knoten von der wurzel bis zu einem platz also hier sehen sie die anzahl der knoten von der wurzel bis zum
- bis zu platz muss es glaube ich heißen oder bis zum zum letzten knoten dann muss ich das blatt mal überarbeiten man versteht es aber glaube ich ein beispiel
- recht schnell dieser baum hat die höhe 312 bleiben wurzeln blatt werden mitgezählt und ich zähle bei 1 ich fange bei 1 an zu zählen
- so jetzt wissen wir ungefähr was ein baum es hier gibt es noch mal ein paar beispiele wo man diese dynamische datenstruktur der bäume verwenden kann
- wir gucken uns mal an was ist denn ein bewerber um das ist nämlich ein sonderfall der in der informatik sehr häufig vorkommt also ein spezialfall der
- sich dadurch auszeichnet dass jeder knoten höchstens zwei kinder knoten haben kann er kann auch nur einen haben aber
- höchstens 2 das sagt nämlich der begriff binär also auf der bass zwei es gibt maximal zwei kinder wir sehen hier
- beispielsweise einen birnbaum erkennt man sofort jeder knoten hat maximal zwei kinder daher hat zwei kinder der hier hat zwei kinder der hat ein kind was ja
- auch okay es maximal zwei kinder während das hier dann natürlich kein binär baum wäre das erschließt sich sofort weil eben
- schon hier die wurzel drei kinder hat das wäre also kein binär bauen ok haben wir gelernt es erschließt sich nicht so hundertprozentig warum wir das wissen
- müssen aber nehmen wir mal hin bin eher baum jeder knoten hat höchstens zwei kinder
- dann gibt es eine weitere art der bäume also wenn wir bei diesem spezialfall sind noch näher zu spezifizieren es gibt nämlich die geordneten binär bäume da
- ist also schon was sortiert und vielleicht zeigt ihnen das dann auch ein bisschen an warum man das gut verwenden kann nämlich um daten zu sortieren das
- möchte ich nämlich gerne haben oder meistens möchte ich geordnete binär bäume haben diese geordneten binär bäume die zeichnen sich dadurch aus dass der
- linke teil baum also zb dieser zeile hier dieser zeitraum nur kleinere knoten als die wurzel enthält das versuchen wir uns mal kurz hin zu malen also das hier
- war ja die wurzel und der linke baum enthält also nur knoten die kleiner sind also die 679 ist ja kleiner als die 10 und der rechte teil der enthält
- natürlich nur knoten die größer sind so und das gilt aber jetzt soll oder muss in einem geordneten bin eher baum für jeden knoten gelten also
- auch dieser knoten zeichnet sich dadurch aus dass der linke teil das ja auch ein knoten
- mit allen seinen kindern hat dort keine kinder dass der kleiner ist als eben dieser knoten und hier habe ich eine zahl die
- größer ist das bedeutet dass sehen sie hier in diesem tipp herausfinden wollen ist dieser baum
- geordnet dann ziehen sie alle knoten einfach mal nach unten das heißt schreiben sie alle elemente in eine reihe und wenn die dann
- sortiert sind also aufsteigend dann haben wir einen geordneten beerbaum 67 19 12 14 15 alles runter geschrieben und tatsächlich es ist eine fortlaufende
- aufsteigende reihe damit haben wir einen geordneten baum es gibt noch eine weitere einschränkung die man beachten sollte
- alle eltern knoten müssen ein linkes kind haben und können noch ein rechtes kind haben das heißt was verboten ist ist das ein knoten nur ein rechtes kind
- hat also was nicht gehen würde ist das also dass wir hier keinen linken knoten haben also dass es hier in eltern knoten er hat also kinder wenn also ein knoten
- ein kind hat dann muss er mindestens ein linkes kind haben ich kann also immer links an ich darf nicht nur ein rechtes kind haben nehmen sie das einfach mal so
- hin das ist also die anforderungen für einen geordneten binär baum haben sie gesehen linke teil bäume enthält nur kleinere elemente rechte teil bäume
- enthalten nur größere elemente und außerdem gilt für die eltern knoten dass sie ein linkes kind haben sie dürfen auch noch ein rechtes haben aber nur
- rechte kinder sind verboten und merken wir uns keine rechten kindern und noch ein begriff ich hatte sie ja gewarnt bei diesem thema
- bereiten wir ziemlich auf begrifflichkeiten rum jetzt lernen wir den vollen binär bauern kennen geordneten können wir schon jetzt gibt
- es auch noch die vollen binär bäume das ist aber ziemlich leicht das ist jetzt wirklich sogar sehr leicht jeder knoten platzt ok also bled das sind ja ganz
- unten das ist platz das ist ein blatt das ist ein blatt also jeder note nerz knoten platzt oder er besitzt zwei kinder nicht 1 nein der ist richtig voll
- der baum der hat nicht irgendwo lücken wo man vielleicht noch irgendwas unterbringen könnte nein nein nein jeder knoten hat zwei kinder
- oder hat gar kein kind insofern ist das hier ein voller power und damit das ganze nicht so einfach wird gibt es dann auch noch die
- vollständigen guinea bäume ein vollständiger bin eher baum ist dabei eine sonderform des vollen weniger bons das sehen sie auch hier an dieser
- definition ein baum der vollständig ist der ist nämlich voll also das ist die voraussetzung man muss voll sein also jeder knoten muss zwei
- kinder haben oder ein blatt sein also der baum muss voll sein und alle blätter befinden sich auf der gleichen höhe das heißt das hier ist ein vollständiger
- baum weil alle blätter die gleiche höhe einnehmen stellen wir uns also mal vor es gäbe dieses platz hier nicht und das blatt hier nicht dann wäre das dann
- platzt und dann wäre dieser baum nicht mehr vollständig weil wir dann drei blätter hätten dass das und das und die sich eben nicht
- auf der gleichen höhe befinden aber so haben wir eben diese vier blätter alle auf der gleichen höhe damit ist der baum vollständig im umkehrschluss heißt das
- auch wenn sie über prüfen sollen ob ein baum vollständig ist dann können sie gleich sagen ja wenn er
- nicht voll ist also wenn sie das vor getestet haben und sie haben festgestellt er ist nicht voll da müssen sie auch gar nicht testen aber
- vollständig ist denn voll zu sein ist ja die voraussetzung dafür dass ein baum überhaupt vollständig sein kann also nochmal vollständiger beerbaum ist eine
- sonderform des vollen bienia baums so und dann machen wir an dieser stelle mal die aufgaben die sie auf diesem
- blatt finden erste aufgabe begründen sie ob es sich beim nachfolgenden schaubild um einen baum handelt
- da möchte ich jetzt folgenden appell loslassen bitte halten sie das video an und machen sie sich mal selbst ständig gedanken ist das ein baum wenn sie genau
- aufgepasst haben müssten sie sofort auf die antwort kommen ja oder nein ist natürlich nicht ausreichend als antwort sondern sie müssen begründen warum es
- diesen baum oder warum ist es keiner wenn es nicht sofort sehen plätze an diesem ort zurück gucken sie sich mal einfach dieses arbeitsplatte am anfang
- noch mal an wie wir einen baum definiert haben also bitte kurz anhalten und dann schauen wir uns gemeinsam die lösungen
- so dann gehe ich mal davon aus sie haben das video angehalten und sie wissen dass es sich hier nicht um einen baum handelt nein das ist kein baum denn wir hatten
- hier oben ja die definition eines baumes es handelt sich dann um einen baum wenn es zwischen zwei beliebig wählbaren knoten nur einen weg gibt
- sie kommen auf einem weg hier zum knoten topf und das ist da unten eben anders bekommen zb zum knoten de über b und es gibt noch den weg über c deswegen ist
- das kein baum also wenn sie das aufschreiben wollen es wäre nicht schlecht sich das zu notieren können sie aufschreiben es handelt sich um kein
- baum weil es zwischen zwei beliebigen knoten zwei wege gibt oder mehr als einen weg gibt [Musik]
- das wäre dann auch schon die lösung für die aufgabe nummer eins so spielen wir dasselbe spielt mal mit der aufgabe nummer zwei markieren sie
- einen baum im nachfolgenden baum sie sollen einen teil baum zeigen machen sie das mal bitte und dann sehen wir uns gleich wieder
- so ist es glaube ich ziemlich ziemlich offensichtlich was hier ein baum ist nämlich dass da das hier ist ein teil baum ein teil baum war ja ein knoten und
- alle seine kinder ich bin also daran sich das hier wäre auch ein teil baum das ist knoten und alle seine kinder es gibt keine weiteren
- kinder aber das offensichtliche ist natürlich zu sagen das hier ist ein teil warum es ein schöner teil warum
- weil da sehen wir auch noch gleich die kinder dazu [Musik] gut dann springen wir gleich mal zur
- aufgabe nummer drei jetzt wird es ein bisschen schwieriger beurteilen sie ob der nachfolgende baum vollständig aber vollständig ist voll
- und ob er möglicherweise noch geordnet ist da müssen sie mal ein bisschen länger darüber nachdenkt man sich die
- definitionen dieser drei begriffe geordnet voll vollständig nochmal anschauen machen sie das mal bitte und dann sehen wir uns hier gleich wieder
- so bei dieser aufgabe haben sie wahrscheinlich gemerkt da wird es jetzt schwieriger ist dieser baum geordnet man würde
- eigentlich fast denken dass er geordnet ist denn es gab ja diesen 17 sie alle knoten mal nach unten schreibt sich und marlies hin also
- 57 dann kommt die 10 usw 19 20 21 mann würde denke ja der ist geordnet aber ich gehe noch mal zurück es gab noch eine anforderung an diesen geordneten
- binär barum den wir nicht außer acht lassen dürfen alle eltern knoten müssen den linkes kind haben und können noch ein recht das
- kind haben also nur rechte kinder sind verboten hatte ich vorher gesagt und genau das haben wir hier aber hier liegt nämlich ein knoten vor der nur ein
- rechtes kind hat damit ist der baum nicht geordnet also sie könnten hier aufschreiben nicht geordnet weil ein knoten nur ein rechtes kind hat
- so ist dieser baum voll da müssen wir uns noch mal anschauen was war noch mal ein voller power ein voller baum ist einer bei dem jeder knoten ein
- blatt ist oder zwei kinder hat ein kind ist also verboten und wenn wir uns das anschauen sehen was sofort nähe da ist wieder dieser knoten fünf der ist kein
- platz der hat ein kind aber keine zwei also deswegen ist der baum auch nicht voll weil es ein knoten gibt ja nur ein kind hat und genau so könnten wir es hin
- schreiben der baum ist nicht voll weil ein knoten nur ein kind hat der baum ist also nicht geordnet er ist
- nicht voll und damit wird es leicht denn jetzt müssen wir noch die frage beantworten ist ja wenigstens vollständig naja ein baum der nicht voll
- ist kann auch nicht vollständig sein denn ein vollständiger baum ist ja eine sonderform des vollen baums also ein baum der nicht voll ist ist auch nicht
- vollständig das bedeutet der warum es nicht geordnet nicht voll nicht vollständig sie könnten eben als begründung bei vollständig hinschreiben
- nein weil der baum nicht mal voll ist und dann kommen wir zur letzten aufgabe überführen sie die knoten 25 und so
- weiter in einen vollen und geordneten den er baut hier gibt es jetzt möglicherweise nicht nur eine lösung sie können verschiedene lösungen finden hier
- können sie mal ein bisschen knobeln also erstellen sie jetzt mal einen baum der voll und geordnet ist das wäre dann glaube ich auch eine relativ typische
- aufgabe für das abitur wie sie ihnen über den weg laufen könnte machen sie das mal bezogen wir sehen uns dann gleich wieder
- und hier sehen sie eine lösung eine mögliche lösung sogar mit einer alternative dabei es gibt nämlich mehrere möglichkeiten wenn man das ganze
- lösen kann also der baum sollte ja voll ungeordnet seien voll heißt ja jeder knoten ist ein kind ecuador jeder knoten platzt oder er hat
- zwei kinder das haben wir hier etwa geordnet dass er auch wenn es um alles runter ziehen dann merken sie ahadi reihenfolge stimmt es gibt auch wenn wir
- einen eltern knoten haben hat er zwei kinder es gibt nicht nur rechte kinder also ist der vollen geordnet oder hier alternativ auf der rechten seite das
- gleiche so könnte man es auch lösen dann springen wir mal zur aufgabe nummer fünf sie merken da kann man bei den
- bäumen relativ viele viele aufgaben dazu machen die nummer fünf führen sie den folgenden baum in einen den er beim wir sehen ja sofort es ist kein bin eher
- baum weil dieser knoten ihr drei kinder hat ich schnappe mir also diese ganzen knoten und muss den baum umstrukturieren so dass ein p näher baum groß wird legen
- sie mal los so sehen gerade eine mögliche lösung vor sich es gibt viele viele lösungen die man hier entwerfen kann denn die aufgabe
- ist ja ziemlich netz der sabine baum muss ja nicht voll sein er muss nicht geordnet sein und so weiter wir haben keine keine besonderen anforderungen an
- diesen baum ist muss halt ein binär baum sein das heißt jeder knoten hat höchstens zwei kinder und da könnte ich auch das ganze völlig
- anders durcheinanderwirbeln und diesen knoten zum beispiel woran das hinhängen man muss ja nicht geordnet sein damit können wir sofort zur aufgabe
- nummer sechs übergehen das wäre dann auch die letzte aufgabe für dieses arbeitsplatz finden sie
- nacheinander die knoten b und a in den gegebenen beerbaum ein okay das ist leicht aber achten sie darauf dass der baum weiterhin geordnet ist
- geordnet machen sie sich mal an die arbeit so und jetzt habe ich jetzt zwei lösungen das hier ist die lösung aus den
- offiziellen materialien für das für die abiturvorbereitungen sieht witzig aus aber tatsächlich essen binär baum
- und er ist auch noch geordnet merken sie wenn sie hier alles mal abc.de wenn sie alles runter ziehen und es gibt auch keine rechten kinder also dass wir eine
- möglichkeit das ganze zu lösen ich persönlich habe es anders gelöst so geht es auch dann noch das ist ja offensichtlich unbelehrbar er ist
- geordnet a b c d und es gibt nicht nur es gibt keine keine eltern knoten die nur ein rechtes kind haben also auch hier ein geordneter binär baum
- mehr lösungen sind wir jetzt zum jetzt nicht eingefallen wenn sie noch etwas anderes gekommen sind zeigen sie es mir und dann müssen wir darüber diskutieren
- ob auch dass eine mögliche lösung wäre und damit haben wir es dann für heute geschafft dh wir haben das thema der
- bäume kennen gelernt es gibt hier noch weitere übungen die mache ich mit ihnen dann live oder in dem ich auch noch mal ein eigenes video dazu erstellen bis
- dann [Musik]
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.
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 …
Baum (Graphentheorie)Ein Baum ist in der Graphentheorie ein spezieller Typ von Graph, der zusammenhängend ist und keine geschlossenen Pfade enthält, d. h. ein Graph, …