Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
1 Einstieg Baumstrukturen der Informatik (Theorie und Algorithmen)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 121 Zeilen
- mit diesem video möchte ich mit euch um die baumstrukturen einsteigen baumstrukturen sind sehr informativ eigene datenstruktur und dem nrw
- zentralabitur jetzt in diesem bereich auch immer eine von vier aufgaben gestellt die baumstrukturen sind eine dynamische datenstruktur ich kann zur
- laufzeit neue daten an die neue struktur anhängen das hast du bist es zur laufzeit nicht begrenzt dies aber im gegensatz zum stapel liste und schlange
- nicht linear wenn die elemente sind nicht hintereinander angeordnet sondern eben entsprechend in einer hohen struktur angeordnet ein baum ist
- grundsätzlich erstmal ein grad in der informatik gibt es grafen und zwar bilden graphen eine wesentliche datenstruktur ab und bestimmte probleme
- abzubilden wir haben zum beispiel für das die verkehrs navigation die routenberechnung gibt es grafen und daten werden durch zwei verschiedene
- mengen definieren wenn ich einmal das kleine menge von knoten und als durch eine menge von kanten und bei dem verkehrs beispiel wäre es natürlich jede
- kreuzung eingeschoben denn dort kann ich von einer kannte auch die nächste übergehen also ist das grundsätzlich erstmal was ist dein warum grundsätzlich
- erstmal ein graf wieder brauchen ist ein grab aber nicht jeder graf ist ein baum der bäume müssen spezielle eigenschaften definieren letzteren ist natürlich ein
- baum eine menge von knoten und von kanten aber es gibt bestimmte bedingungen die existieren müssen damit wir das ganze in der informatik auch als
- boy bezeichnet wirken und zwar was er tut und freiheit gegeben sein suter freiheit bedeutet ich kann mir ein beliebiges knoten paar angucken und ich
- finde keinen zyklus der weg zwischen diesen beiden knoten ist eindeutig also wenn ich jetzt von diesen knoten zu diesen knoten möchte dann gibt es jetzt
- nicht zwei verschiedene wege sondern es gibt nur diesen eigenen weg dorthin es gibt jetzt nicht mehrere möglichkeiten und das gilt grundsätzlich für jedes
- knoten paar es dürfen keine zyklen enthalten sein das heißt wäre jetzt eine konstante noch enthalten hätten wir schon kein baum
- mehr denn dann gäbe es zwei verschiedene regeln ich könnte von diesem knoten zu diesen gelangen oder es könnte halt auch andersrum stock ist ja auch so zu sagen
- wie diese direkte verbindung nehmen dann hätte ich zwei verschiedene wege glaube ich jetzt also inneren finden die kanten gerichtet sind dann wären wieder beide
- wege geben das gleichgewicht so das darf nicht sein also der muss sitzen beisein der graf muss auch zusammenhängen sein damit er als traum bezeichnet werden
- grundsätzlich ist jetzt erst mal für einen grad nicht definiert dass er zusammen hängt dann muss das alleinige libyen könnte zum beispiel auch dass
- hier vorkommen das heißt man hätte zwei verschiedene bereiche und so das hier ist ja auch eine menge von knoten und kanten die miteinander verbunden und wir
- sind wirklich zusammenhängt und dass dafür ein baum nicht sein also ein baum muss grundsätzlich zusammenhängen und dann sehen wie hier auf der rechten
- seite dort ist von jedem knoten zu jedem anderen knoten auch einen weg was bedeutet zusammenhängen und die müssen ausgewiesen der wurzel haben denn es
- gibt irgendwo ein ursprung von einem baum romina informatik einfach umgedreht die wurzel ist im prinzip oben und die
- blätter befinden sich um jetzt gibt es den spezialfall eines wien er baums und zwar wird für den binär baum dass jeder knoten maximal zwei nachfolger haben
- darf von der wurzel aus gesehen es darf nicht mehr nachfolger gebe es muss jetzt nicht exakt 2 gehen wir sehen zum beispiel an diesem punkt das dann nur
- einen nachfolger hat das ist aber gar nicht schlimm für jede knoten in diesem grafen hier gilt dass er maximal zwei nachfolger hat
- und somit ist dieser baum auch ein gen er baut also jeder binär baum ist auch ein baum also sehr viel mehr brauchen natürlich
- auch ein graf aber man nicht jeder baum ist ein bewerber sofort war nachfrage wirklichkeiten über bäume sprechen zu können jetzt gibt es blätter und zwar
- bezeichnet man alle knoten als blätter die keine nachfolger haben jedes blatt gesetzt eine tiefe und zwar definieren wir das für uns die tiefe als
- die anzahl an kloten von der wurzel bis zum blatt oder zählen wir jetzt die rätsel auf millionen hätten wie die tiefe vier wenn wir haben eher 1234
- knoten also besitzt dieses platini tiefe 4 und die anderen blätter an wie kiefer 2 ein baum besitzt eine höhe und die höhe ist das maximum der tiefen aller
- blätter also um die hitze zurecht und kann man jetzt hier für jedes blatt einfach die tiefe berechnet und jetzt bilden wie er aus einem tiefen einfach
- das maximum und die höhe dieses baumes wäre hier also jetzt haben wir gerade bei den brauchen eben gesehen der ist jetzt für ein binär baum nicht ganz
- besonders sinnvoll verteilt jetzt könnte man auch sagen es wäre doch einfacher wenn die das laufen noch irgendwo hier wäre dann wäre er besser gefüllt und
- dafür haben wir auch noch eine bedürftigkeit gesprächen dann von einem vollständigen binär baum wenn alle blätter dieselbe tiefe haben und kein
- knoten existiert die wir nur ein kind hat wir haben hier einmal einen vollständigen bau alle blätter haben dieselbe tiefe das dilemma die haben
- andere t-shirts wo und es existiert kein klo ein kind hat war er ist nach dieser definition dieser baum ja vollständig
- und dieser hier ist unvollständig denn es existiert ein knoten wer nur ein kind hat das ist dieser hier und das widerspricht hier
- den zweiten punkt so wird es nie gebaut unvollständig so und dann haben wir auf der linken seite auch noch einen unvollständigen baum
- denn hier gibt es folgende blätter hier ist ein blatt und dieses 30 und auch blätter allerdings hat dieses blatt 4 und diese wette haben kiefer 3 und somit
- haben müsst alle blätter dieselbe tiefe somit ist nach den ersten punkt definitionen dieser baum als unvollständig zu bezeichnet das schöne
- an den bäumen ist jetzt wenn ich jetzt ein wiemer baum habe dann verdoppelt sich die anzahl an speicherbaren elementen in jeder ebene also oben auch
- der wurzel ebene kann es natürlich nur ein element abspeichern in der nächsten schon zwei in der nächsten vier dann acht dann 16 32 und so weiter also das
- wächst entsprechend der zwei jahre tänzen das ganze kann ich natürlich dann auch eine formel packen ich kann doch als
- summe ausdrücken wenn ich jetzt aus diesen zwei prozent sind wie summe bilde dann bekomme ich als ergebnis dass ich in den gesamten baum wenn jetzt in die
- höhe ist dann habe ich zwei drucker - ein element also wenn ich jetzt 10 geben an dem baum haben dann kann ich zwei hoch 10 also 1024 das 1 1020 elemente in
- dem beerbaum speichern wenn er vollständig ist also bis jetzt hatte ich dem baum immer nur so da stehen das doch keine
- enthalten wagt wenn es jetzt eine datenstruktur ist dann macht ist natürlich in jedem knoten auf irgendwo etwas gespeichert ich habe jetzt so
- einfachheit einfach mal ganz zahlen genommen also wir sagen jetzt wieder beim speicher ganz zahlen sowie das vielleicht in den elfer ja auch der fall
- wäre natürlich können dort auch objekt referenzen oder andere dinge gespeichert werden aber jetzt veranschaulichung ist das einfach nur zahlen natürlich einfach
- so wenn es eine ordnungsfunktion nach der das einsortiert ist da wir zum beispiel größer oder kleiner findet sich an ganz zahl dann spricht man von einem
- billigen such bauen das heißt die inhalte die dort abgelegte unterliegen einer ordnung in einem bestimmten prinzip einsortiert
- grundsätzlich wenn ich jetzt objekt referenzen habe kann ich natürlich auch sagen ich gerade auf irgendein beliebiges absolut diese objekte zu und
- und dann wäre das eine ordnung das muss jetzt nicht in den usa wie kann man jetzt suchen wien er in ihrem super also wir können jetzt natürlich das
- prinzip der wien ihren suche anwenden das hatten wir für das airrail schon gelernt betrachten erstmal das element in der mitte und macht jetzt ein
- vergleich wer wird die zahl 690 suchen vergleich erstmal mit der wurzel da ständig jetzt fest dass der knoten größer ist als die
- wurzel und dementsprechend weil ich ja weiß dass links und der wurzel nur kleinere elemente sind kann ich jetzt natürlich sofort die komplette linke
- hälfte ausschließen sagt nach der ersten frage habe ich schon mal den größten bereich ausgeschlossen und jetzt mache ich natürlich auf der
- rechten seite beitrag natürlich erst mal gucken ob ich jetzt hier beim nächsten knoten die diese zahl finden nein habe ich nicht
- also vergleiche ich jetzt wieder 840 ist kleiner setzen sich also kann ich wieder den linken teil baum ausschließen na ja also das hier wird der reifen 2
- markiert das ist der zweite bereich tätig ausschließe jetzt wirklich rechts davon weiter das finde ich jetzt 90 punkte auf meine besucherzahlen wann ist
- es nicht also mache ich wieder den verlagen wie 90 ist jetzt aber größer als die gesuchte zahl das heißt die 96 also meine gesucht die zahl kann nur
- noch in der nächsten album sein also wie der dritte bereich nicht ausschließe die weiße 3 jetzt bleibt nur noch ein element über dann über 50 das habe ich
- schon 90 gefunden dies aber jetzt ungleich der gesuchten zahl und somit habe ich festgestellt dass die gesuchte zahlen nicht in der datenstruktur
- enthalten und das habe ich jetzt innerhalb von vier schritten geschafft und das bedeutet ich kann den im baum jetzt natürlich in logarithmische zeit
- durchsuchen dann wird jede einzelne anfrage schließlich immer die hälfte des übriggebliebenen bereichs aus- und somit
- wird kann ich auch keinen problemen super genauso effizient arbeiten wie ich es auch auf einem apple mache wenn dort einzahlen so ziert sind und die
- gehversuche an wände also das suchen ist jetzt in dem zu einer baumstruktur erstmal nicht besonders schwer das kann man sich gegen sutter und recht gut
- vorstellen was jetzt viel spannender ist ist die frage wie kann ich denn eigentlich durch seine struktur durchlaufen
- denn wenn da jetzt zum beispiel an den eray denken dann schreibe ich mir einfach eine schleife sache lauf von vorne bis hinten und die einmal über
- jedes element in meine den gibt es auf der konsole aus oder sucht nach der zahl ich weiß nicht was bei der liste kann ich das natürlich auch machen ich
- schreibe eine schleife noch einmal von vorne ein bisschen durch das ist extrem einfach zu programmieren bei einer baumstruktur in das ja zum
- baumart ich auch gebraucht das ist das jetzt erstmal mit einem iterativen algorithmus überhaupt nicht einfach mitnehmen systematisch zu durchlaufen
- und wenn wir von einem systematischen durchlauf sich die knoten einer baumstruktur sprechende linie von einer präzisierung
- also vitra basiere die ich jeden baum die laufe ich dadurch da gibt es jetzt verschiedene verfahren in nordafrika oder und postbank mit der in order
- radierung an das ist jetzt erstmal das was an daneben ist denn wenn ich dazu einen wenigen südbahn habe und jetzt kommt irgendwann die anfrage an die
- datenstruktur bitte zeigt mir doch mal was du alles gespeichert hast was ganz normal lebt erst mal alles aus dann wäre es schön wenn ich das auch von vorne bis
- hinten einfach der reihe nach ausgegeben bekommen das heißt ich habe in seiner ausgabe jetzt in diesem beispiel von 3 4 5 6 7 8 9
- das soll raus brauchen so und das bietet sich jetzt extrem gute musik an bitte dazu nochmal meine playlist zur reprogrammierung beachten da könnt euch
- das noch mal genau angucken wie was die person angeht wie genau das funktioniert ich werde das jetzt hier ein bisschen schneller erklären weil ich davon
- ausgehe dass hier die reaktionszeit ist schon gesehen habe und das schon verstanden also ich muss jetzt für einen
- systematischen in order durchlauf einfach folgenden drei schritt auf jeder ebene des problems an denn erstmalig auf dem linken radweg auch dann verarbeite
- ich den knoten das bedeute ich jetzt in meinem fall missen möchten inhalt ausgeben er verarbeitet denken kann auch bedeuten
- dass ich jedes element sieht irgendwie um 1 addiert oder was auch immer irgendwie wird der inhalt bearbeitet oder verarbeiten oder manchmal spiele
- ich jetzt davon aus dass wird nun ausziehen wollen gegenhalten danach muss man sich auf dem rechten bonbon das gucken wir mal an sie funktioniert das
- genau dort allererstes kommt der erste aufruf auch der wurzel das heißt die republik order methode wird jetzt auf dem auch der wurzel
- ausgeführt also das ist also eine methode die der knoten bereitstellen so würde ich auf dem link noten auch das heißt wir wieder tief in die tiefe
- es gibt kommt wieder der aufsucht also startet er wieder oben in der methode widerwillig noch mit quoten auf und das macht da bis da unten ist da stellt er
- jetzt fest ich kann mich nicht weiter auf den link knoten aufrufen als auch den linken kind und dem entspreche hört jetzt hier erstmal der repressive
- selbst auch gut auf und diese methode hier unten kann jetzt erstmals zu schritt 2 gehen das heißt verarbeitet den knoten in unserem beispiel den
- inhalt aus so das ist jetzt fertig und jetzt würde der dritte schritt kommen wir sind bei dem aufruf unten auf dem knoten mit ja drei da mit der er
- versucht man sich auf dem rechten kind auch zu nutzen das funktioniert nicht das hat er jetzt gemacht das heißt diese drei befehle wurden jetzt auf die sache
- wert des problems ausgeführt und jetzt bringt er ja zu dem vorgänger zurück denn von dem vorgänger hatte er ja zunächst diesen bisher gemacht also hat
- sich auf den link knoten aufrufen so gast ist jetzt aber fertig das hat er erledigt das heißt jetzt können wir zu schritt 2 kommen verarbeitet den quoten
- gibt also den inhalt auch jetzt kommen die hierzu der 4 in den nächsten schritt wird er sich jetzt auch den rechten kind aufrufen das
- wäre jetzt dann der nächste schritt und dann geht das halt so weiter fruchtig erst dann noch zum rechten auch jetzt wieder auf dem niveau kind nein
- jetzt ganz nah dann gib den inhalt aus danach künftig auf dem rechten auch dann ist er hier fertig ergibt zurück dass wir hier fertig und dann ist er hier
- oben hier habe er dann sich auf dem linken aufgerufen jetzt gibt er zu nach diesen knoten aus und sich dann auf den westen auf und da fängt jetzt der
- drei schritten wieder von vorne an ruft ich auf der linken aufruft sich auf linken auch nein das nicht da dann 17 knoten aus buch sich auf dem rechten auf
- gibt es nicht zurück von hier aus gesehen hat er sich schon auf den linken auch zu nutzen dann sucht er den knoten aus bucht sich wieder auf
- den rechten aufzug sich erst auf den linken auch gibt es nicht gibt den knoten ausbruch sich aus dem rechten und dann hat ja genau den inhalt des bauen
- so wie er so fährt ist hat ja auch der reihe nach raus gegeben und das ist jetzt das kondom zu ihr haben oder haben das schleife und sagen einfach vorname
- und alle der reihe nach aus das ist jetzt direkt in order kreative also der musik unglaublich einfach zu programmieren
- wie ist das galt für die orthopädie all das ist die reihenfolge einfach ein bisschen anders es wird erst der inhalt ausgegeben dann
- ruft er sich auf den link kind auch dann auch den rechtlichen es gibt jetzt ja drei verschiedene varianten liegen diese drei befehle in eine zeitliche
- reihenfolge bearbeitet den knoten die biene also aus die sechs wird ausgegeben ruft dich auf den linken kind auch das macht er jetzt dafür fordern durch den
- quoten aus also wie die hier ausgegeben beruft sich auf den link auf das stimmt ja dann auch wenn fängt wieder von vorne verarbeiteten florentin auch künftig auf
- linken auch gibt es nicht 50 berechtigt sind auch gibt sich auch nicht also springt zurück und da sind wir dann fertig wird im
- zweiten schritt also kommen jetzt zu schritt 3 muss die durch den rechten kind auch da gibt es wieder los gibt den vierten aus durch technik und auch
- gibt's nämlich aufrechten gehen können auch nicht aufrufen und dann springe ich nach dem gleichen prinzip jetzt hier du nicht das heißt wir haben eine liebe
- ausgabe für den recorder durch wie es auch bei der post order durchlauf bei den pos oder durchlauf ist die verarbeitung ganz am ende also hinter
- den repressiven aufrufen das heißt jetzt kommt erstmal die außentür richtige familie auf das kind
- auch da gibt es keine kids mehr jetzt schritt 1 gefährt und beruft sich auf recht auf geht's auch nicht mehr jetzt kommt erst die aufgabe also geht erst in
- die tiefe und dann kommt die ausgabe jetzt hat ja von dem klo vier aus gesehen ja den ersten schritt ausgeführt also kommen sie selbst auf 5 auf der
- rechten auf dem rechten kind da geht ja dann rein jetzt muss er sich erst aufnehmen nur noch einen rechner auf die gibt es aber
- nicht also wieder da der knoten ausgegeben und dann ist das fertig sprint zurück und kann jetzt hier endlich auf der ebene den dritten start
- ausführen und ist dann oben bei der wurzel und ruft sich jetzt exklusiv auf der rechten hälfte das heißt das wäre jetzt dann hier unten
- die ausgabe für den post ordner durchlauf auf einen solchen wenigen suchen okay das sind dass man die wichtigsten
- grundlagen für bäume und begrifflichkeiten weiteren unterrichtlichen geschehen brauchen im nächsten durchlauf im nächsten video
- schauen warum es dann an wie sieht denn die nrw zentrale abiturklasse dafür eigentlich auch die wieder als schnittstellen beschreibung
- im zentralabitur dabei bieten und wir wollen natürlich dann auch im weiteren verlauf gucken liegt in saniert man mit solchen datenstrukturen und das dann
- alles in den weiteren videos an und sagt gerne an
Zum Nachlesen
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …
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 …
SuchbaumIn der Informatik ist ein Suchbaum eine abstrakte Datenstruktur, bei der die Menge von Elementen, in der gesucht werden soll, in einer Baumstruktur …
TraversierungDie beiden bekanntesten Verfahren sind die Breitensuche und die Tiefensuche. Für Binärbäume existieren spezielle Traversierungen, die man als Linearisierung …