Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Grundlagen der Informatik 5 (Abstrakte Datentypen)

Name: Grundlagen der Informatik 5 (Abstrakte Datentypen)
Uploaded: 2026-05-31T09:47:47+00:00
Duration: 1 h 14 s
Channel: LOST IN A WAVE
Description: Ein abstrakter Datentyp kombiniert Datenstruktur und erlaubte Operationen. Die Implementierung bleibt verborgen, der Zugriff läuft nur über die …

LOST IN A WAVE1:00:14 76 Aufrufe veröffentlicht 31. Mai 2026 Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 411 Zeilen

Herunterladen

Ja, willkommen zum Kapitel 5, Teil 1. Hier geht es um abstrakte Datentypen. Für ein guten Start überlegt euch mal, was die Begriffe first in, First Out und
Last in, First Out bedeuten könnten. Abstrakte Datentypen. Die Kombination von Datenstrukturen und Operation auf den Daten heißt abstrakter Datentyp,
auch als ADT bezeichnet. Ein ADT soll den korrekten Gebrauch der Daten sicherstellen. Die Implementation der Daten ist von außen nicht sichtbar.
Der Zugriff auf die Daten ist nur über die Operationen möglich. Das ist die Trennung von Implementation und Schnittstelle.
Ein ADT wird definiert durch die Operationen, die mit den Daten erlaubt sind. Für die Nutzung des abstrakten Datentypens muss die Schnittstelle
spezifiziert werden. Ich versuche es noch mal ganz kurz ja so zusammenzufassen in anderen Worten. Also die Schnittstelle, das sind die
Operationen, die auf den Daten möglich sind. Ja, ich werde euch dann gleich auch Beispiele zeigen, damit das alles deutlicher wird. Es geht darum bei
abstrakten Datentypen, dass wir die Möglichkeit haben, die Implementation für uns so zu gestalten, dass es gut ist. Also die Menschen, die diesen
abstrakten Datentypen implementieren, können die Implementation auch verändern, ne? Wenn es jetzt neuere Algorithmen gibt, die effizienter sind,
z.B. in der Speicherverwaltung, kann das alles geändert werden. Solange die Schnittstelle nicht verändert wird, können die Menschen ja diesen ADT
nutzen. Das ist also der Riesen Vorteil. Ja, Beispiele für abstrakte Datentypen, das sind Warteschlangen oder auch QS genannt, die Prioritätswarteschlange,
ein Stack, eine Menge, Grafenbäume, eine Matrix und so weiter und so fort. Ihr werdet im Laufe, also auch natürlich dieses Kapitel jetzt Beispiele sehen,
aber wenn ihr dann anfangt zu programmieren, ne, schaut euch da meine Vortragsreihen dazu an, zur Java Programmierung. Da seht ihr dann, wenn
wir mit Collections arbeiten, dass da auch abstrakte Datentypen natürlich drin sind. Ich denke, für den Anfang ist erstmal ein bisschen schwierig zu
verstehen, warum das auch abstrakte Datentypen heißt. Stellt euch das einfach so vor. Ähm, nehmen wir jetzt hier mal so ein Stack. Ich werde euch
gleich erklären, was das ist. Also, ein Stack, das ist ein ist ein Stapel, ne? Da könnt ihr dann was drauflegen. Genau, jetzt geht's darum, ihr könnt was drauf
legen. Dem abstrakten Datentypen ist egal, was ihr da drauf legt. Es muss halt nur derselbe Typ sein, ne? Und deshalb nennen wir das abstrakter
Datentyp. Wir haben also einen Datentypen, der Dinge aufnehmen kann, ja, ohne vorher zu wissen, was ist das, ne? So müsst ihr euch das vorstellen,
warum man das so genannt hat. Ne, also Abstraktion ist ja eine Komplexitätsreduktion. Habe ich ja auch schon drüber
gesprochen. Ähm jetzt geht's einfach darum, dass ich die Begriffe ein bisschen einordnen möchte, warum man das ADT nennt, ne?
Ähm, ihr habt die primitiven Datenten kennengelernt, z.B. so ein Integer, da ist klar, ne, da steht der Wertebereich fest, ja, und auch die Operationen da
drauf. Und hier bei abstrakten Datentypen haben wir ja auch Operationen, spricht, das ist die Schnittstelle. Wir können Objekte drauf
legen auf den Stack, dann können wir sie runterholen, wir können einfach mal nachschauen, was liegt da oben und so weiter. Und die Schnellstelle ist
definiert, aber wie gesagt, was wir jetzt wirklich für Objekte auf diesen Stack packen, das ist diesem Stack egal, ne? Wir müssen es vorher sicherlich mal
anmelden, ne? Da schaut euch mal auch dann Videos dazu an. Äh hier zu dem entsprechenden Kapitel. Ich werde das auch verlinken natürlich hier in der
Videobeschreibung, ne, bezüglich der der Java Collections, dann wird das alles klarer für euch. Okay, genau so ein Stack, das eine lineare
Liste. Klingt erstmal wieder komplex oder kompliziert, ne? Also das Shtck und dann sind da Atome drin. Das sind die Elemente, die dieser Stack aufnehmen
kann. Und jetzt noch mal, was das jetzt für Elemente sind, also von welchem Typ, ob wir da jetzt Spielkarten drauf packen oder Personen, ne? Äh, also Objekte aus
der Klasse Person nur als Beispiel, das ist dem Stack egal. Ja, die Elemente werden wie gesagt Atome genannt. Atome können nur am Anfang der Liste eingefügt
werden oder entnommen werden. Das ist dieses Last in First Out. Ja, dieser Stapel, das ist ganz wichtig. Das haben wir sehr häufig, dass wir sowas
brauchen. Auch bei der Analyse von arithmetischen Termen brauchen wir sowas. Ja, ihr hat werdet auch so Begriffe wie Kellerspeicher in dem
Kontext hören. Wir brauchen Informatik solche Stacks immer wieder. Schauen uns mal die Schnittstelle an. Wir haben hier ein Init. Ja, da initialisieren wir den
Stack und ihr seht, dass wir so ein bisschen hier euch das näher bringen wollen mit Vorbedingung, Nachbedingung. Denkt noch mal bitte an Design bei
Contract. Also die Vorbedingung ist der Zustand von unserem Stack, der ist beliebig und die Nachbedingung ist, dass S leer ist, ne? Und er wird einfach
initialisiert. Dann haben wir sowas wie ein Mempty. Das liefert wahr. Wenn es leer ist, dann haben wir ein full. Ist klar, dann kriegen wir halt ein True,
wenn der Stack voll ist. Also bevor man ein Objekt ablegen möchte, sollte man das überprüfen. Natürlich in modernen Programmiersprachen,
wenn wir so Collections haben, da laufen die selten über und wenn haben wir sowas wie Exception Handling, das heißt, wir legen einfach ein Element drauf und
kriegen eine Exception, dass der also der keinen Platz mehr hat, dann können wir drauf reagieren, ne? Also wie gesagt, moderne Programmiersprache mit
Exception Handlegen, da würden wir nicht immer fragen, also wenn der Stacker also nicht voll ist, dann packe ich erst was da drauf. Aber es gibt ja auch nicht
objektorientierte Programmiersprachen oder wo wir kein Exception Handling haben. Dann sollte man das natürlich überprüfen, bevor wir was drauf packen.
Der also praktisch die Operation, um Element abzulegen, nennt man im allgemeinen Push. Ja, da übergebe ich halt einfach das Atom, was ich oben auf
dem Stack legen möchte. Da haben wir auch wieder Vorbedingung. S ist nicht voll, ne? Und die Nachbedingung S erweitert um A. Dann haben wir das Pop,
das entfernt das oberste Atom. Die Vorbedingung S ist nicht leer, ne? Also, ich kann ja keinen Pop aufrufen, wenn nichts da ist. Die Nachbedingung S
vermindert um A. Und ihr seht, üblicherweise sollte man auch sowas wie ein Top haben und manchmal nennt man das auch Peak. Also, wie man jetzt diese ja
Methoden äh nennt. Äh man sollte sich schon an die Geflogenheiten halten, aber manchmal haben wir auch andere Begriffe, ne?
Also, ich kenne dann auch Stack Implementierung heißt das Peak. Das gibt das oberste Atom zurück, aber eine Kopie. Ja, die Vorbedingung S ist nicht
leer und die Nachbedingung S ist unverändert. Wir wollen da vielleicht einfach nur mal schauen, das liegt oben auf dem Stack, dann rufen wir halt das
Top auf und ja, fertig. Jetzt noch mal zu Design bei Contract, ne? Sie müssen ja als nutzende Person von diesem abstrakten Datentypen die Vorbedingung
einhalten und wenn hier steht, dass die Vorbedingung es ist nicht voll ist, dann müssen wir das überprüfen außen, ne? Also die seign bei Contract. Wir sind
also per Vertrag ja verpflichtet, das einzuhalten. Also sollten wir vorher einfach schauen, dass es nicht empty ist, ne? Ich denke, ihr habt eine gute
Vorstellung, was ein Stack ist. Der wird sehr, sehr häufig eingesetzt. Ja, wie gesagt, der Verweis äh auf meine ja Videos so Java Collections, da schaut
ihr einfach mal rein. Ich denke, dass ich auch Beispiel für ein Stack habe. Ja, Beispiele für den Einsatz eines Stacks. Überprüfung der korrekten
Klammerung von Termen, Stackpointer bei Mikroprozessoren, Rücksprungadresse bei Methodenaufrufen sichern. Dann haben wir PAS, also Paser, die wandeln z.B. für
Text, die HTML in eine andere Datenstruktur. Ja, die nutzen auch solche Stacks. Implementierung von realen Objekten wie ein Stapel aus
Spielkarten in Software. Okay, wie gesagt, schaut euch das noch mal im Detail an. Hier in Grundlagen der Informatik müssen wir jetzt erstmal nur
verstehen, dass sowas wie abstrakte Datentypen gibt und wofür die da sind, ne? Und wenn ihr dann euch die Vortragsreihe anschaut hier
objektorientierte Programmierung mit Java, dann werden euch dann paar Konzepte da noch deutlicher dann im Einsatz.
Ja, dann haben wir Warteschlange. Eine Warteschlange ist eine lineare Liste, ne? Also hier Abkürzung Q, also einfach Q und dann haben wir auch Atome da drin.
Hier ist jetzt einfach der Unterschied, das ist ein First in First Out. ist klar. Warteste, also die Person oder das Objekt oder das Atom, was als erstes
sich anstellt, ne, soll auch als erstes bedient werden. Ja, wir haben übliche Schnittstelle, wir haben das Init empty, full push pop und hier haben wir das
Front genannt. Ja, ähm schaut euch das an. Prinzip ist auch klar. Warteschlangen haben wir auch sehr häufig im Einsatz. Ja, besonders bei
Prioritätswarteschlangen. Mal ganz kurz zuhören, worum es da geht. Also Warteschlangen werden häufig gebraucht, z.B. eine Simulation von
Transportprozessen oder zur Entkopplung asynchroner Prozesse, z.B. Spool Dateien für die Druckerausgabe. Die Elemente in einer
Prioritätswarteschlange besitzen eine Priorität, die z.B. durch eine ganze Zahl repräsentiert wird. Das heißt, Elemente werden in die
Prioritätswarteschlange nach ihrer Priorität eingefügt. Das ist der Unterschied, ne? Sind dann, ich meine, wenn alle Elemente dieselbe Priorität
haben, dann ist es wie eine Warteschlange, also wie eine Q. Aber oft ist es einfach so, dass wir es noch mal unterscheiden wollen. Ähm, wenn wir
jetzt z.B. wer bekommt jetzt z.B. ein Prozessor oder sonst was, dann kann es ja sein, dass der Prozess mit einer hohen Priorität sich in der
Warteschlange ein anreihen muss, also ganz ans Ende und kommt einfach nicht dran, obwohl er eine hohe Priorität hat, ne? vielleicht auch Sicherheitsgründen
oder Sensoren sollen abgefragt werden, dann möchte man diesen Prozess natürlich nach Priorität dann einsortieren in dieser Warteschlange. Okay,
Prioritätswarteschlangen werden z.B. im Betriebssystem, ne, für die Prozessplanung verwendet, in den die wichtigen Prozesse zuerst die Ressource
CPU zugeteilt bekommt, ne? Und dann gibt's noch ganz ganz viele Anwendungen. Also ich fasse mal zusammen. So ein Deck ist wichtig, ne, dass wir die Dinge oben
drauf legen können, auch nur von oben entfernen können. Aber Warteschlangen sind genauso wichtig, ne? Einfach andre. Wer zuerst kommt, malt zuerst. ist so so
ein Sprichwort im Deutschen, so müsst ihr euch es vorstellen und Prioritätswarteschlange, dass die Elemente nicht einfach praktisch ans
Ende der Schlange gesetzt werden, sondern nach Priorität in die Warteschlange einsortiert werden. Dann haben wir noch sowas wie eine
Menge. Das ist ein Set. Oft ist es so, dass das auch als Back bezeichnet wird, also Beutel, wenn man das mal so möchte. Es gab Implementierungen,
Programmiersprachen. Kann ich mich dran erinnern, dass es so ist. Ihr müsst euch so vorstellen, dass das auch Sinn macht. nehmen jetzt einfach mal die Menge der
natürlichen Zahlen. Ja, wenn wir da so ein Element drin haben, ja, und es entfernen, dann ist es in der Menge hier dann nicht
mehr drin. So müsst ihr euch das vorstellen. Und natürlich die Menge der ganzen Zahlen ähm die ist natürlich unendlich,
aber es geht einfach drum, ich möchte euch so Beispiele geben, damit ihr verstehen könnt, wo so solche Mengen halt verwendet werden können. Äh im
Prinzip ist wie gesagt, deshalb heißt es auch manchmal Beutel. schmeißt einfach alles rein, was ihr da wollt. Wir haben üblicherweise wir Init empty und full.
Hier haben wir jetzt ein Insert. Hier haben wir die Vorbedingung S ist nicht voll und A nicht Element von S. Das ist jetzt der Unterschied. Deshalb ich das
Beispiel mit der mit den natürlichen Zahlen genommen, ne? Wir haben die ein dann nur einmal drin, ne? und die zwei und so weiter. Also, das müsst ihr euch
einfach vorstellen. Ist also jetzt das Atom A da nicht drin, dann kann ich das da reinpacken. So, deshalb haben wir hier so eine Schnittstelle Member, also
eine Operation, die liefert wahr, wenn A in S ist. Also bevor ich ein Insert aufrufe, habe ich also die Verpflichtung, weil das die Vorbedingung
ist, erstmal zu überprüfen, ob A nicht schon in der Menge drin ist. Natürlich, wenn die Menschen, die jetzt so ein so ein ADT Menge implementieren, die müssen
das natürlich überprüfen, ne? Man geht immer davon aus, die Vorbedingungen sind klar, dennoch, ne? Die Leute halten das meisten nicht ein, wir sollen das robust
implementieren. Ruft also jemand ein Insert auf, dann sollten wir erst selbst mal überprüfen, ob das A da drin ist. Ja, vielleicht kann man auch einen
Hinweis geben, dass das A dann schon da drin ist und fertig. Dann haben wir ein Eas, das entfernten Atom. Ja, ich denke euch ist das klar. Also
auch Mengen sind sehr nützlich, wenn wir einfach Elemente da reinpacken wollen, um einfach zu überprüfen, okay, z.B. ein Mitglieder, ne, ist das da drin oder oft
in der Spielprogrammierung kommt das vor, dass wir einfach eine Menge haben von den Objekten, die sich praktisch gerade bewegt haben, ne? Die müssen wir
dann neu rendern. Nur so als Beispiel und da ist es dann egal. Ähm, dann braucht man nicht unbedingt ein Stack oder eine Queue zu haben. Manchmal macht
das natürlich auch Sinn, ne? Stichwort Zbuffer. Daher habe ich, glaube ich, auch ein paar Videos schon dazu gemacht. Aber es geht einfach darum, wenn es
jetzt egal ist, wer da jetzt zuerst da drin ist oder nicht, sondern es nur zählt, ob überhaupt jemand in der Menge drin ist. Starten wir in den Teil 2.
Hier geht's jetzt um sogenannte implizite Datenstrukturen. Na ja, okay. Worum geht es jetzt? Wir haben gerade gelernt, was ein abstrakter Datentyp
ist. Und jetzt möchte ich euch diese impliziten Datenstrukturen vorstellen, mit denen man dann äh solche ADTs implementieren kann.
Okay. Implizite Datenstrukturen dienen als Mittel zur Implementierung von abstrakten Datentypen. Die wichtigsten impliziten Datenstrukturen sind Array,
Listen und Hashpeicher. Ja, wir wissen jetzt vielleicht noch nicht, was ein Hashspeicher ist. Das werde ich euch äh später in einem
Kapitel mal ein bisschen so erklären. Ich will es ja hier nur erwähnen, aber Array und Listen, ich glaube, da habt das schon Begriff. Ich werde euch
natürlich ja gleich erklären, was das alles ist. Ein abstrakter Datentyp wie ein Stack kann mit einem Array oder auch einer Liste implementiert werden. Ja,
für die Person, die den Stack verwendet, bleibt die tatsächliche Implementation verborgen. Das Geheimnisprinzip, ne? Ich denke, das habt ihr verstanden. So kann
auch eine bestehende Implementation geändert werden oder sogar komplett ersetzt werden. Das macht dann Sinn, wenn man vielleicht dann jetzt neuere
Algorithmen entdeckt hat, ne? Stichwort mal so Matrizenmodultiplikation. Ähm für die, die das vielleicht noch nicht so wissen, also
Matrizenmodifikation, das sind ganz ganz häufige Operationen, die tagtäglich, wenn ihr z.B. Computerspiele spielt eingesetzt werden. Also, wir haben
massiv Millionen, Milliarden oder vielleicht sogar Billionen von Matrizenmodultiplikation jeden Tag in den ganzen Computern und da wird immer
noch aktuell daran geforscht, wie man äh Algorithmen entwickeln kann, um diese Matrizenmultiplikation zu verbessern. Ja, und dann kann man ja so ein Matrix
abstrakten Datentypen haben. Man kann dann diesen ADT verwenden und falls dann wieder ein Algorithmus entdeckt werden sollte, der diese Matrizenmodifikation
beschleunigt, dann kann man den ADT aktualisieren, ohne dass jetzt die Menschen, die ihn benutzt haben, davon betroffen sind. Ja. Ja. Die
spezifizierte Benutzungsschnittstelle bleibt also unverändert. Jetzt klären wir einfach, was ein Array ist. Ein Array ist eine ja ein oder
mehrdimensionale Tabelle fester Größe, die Elemente der gleichen Typs aufnimmt. Diese Elemente können wiederum Errays sein. Somit kann ich also
mehrdimensionale Arrays aufbauen. Auf ein Element der Tabelle wird über den Index zugerriffen. In den meisten Programmiersprachen werden die Zeilen
und Spalten ab null gezählt. Ihr müsst euch, bevor ihr dann anfangt zu programmieren, mit irgendeiner Programmiersprache, einfach mal in der
Spezifikation anschauen, ob das zeilenorientiert oder Spaltenorientiert indiziert ist. Also, wenn man jetzt hier so ein Beispiel hat, ich markiere das
mal, also hier so groß A, ja, da haben wir jetzt 2 und 4, das sind die Indizs. So, und hier jetzt, wenn wir von Jahre ausgehen, ist es äh das Element in der
dritten Zeile und fünften Spalte. W wir wir beginnen bei null. So, so müsst ihr euch das einfach vorstellen. Es gibt aber auch ähm Implementierung von, ich
sag mal dann also bei Programmiersprachen, wo auch bei Mikroprozessoren, also es war früher so, da hat man das spaltenorientiert erstmal
gemacht. Ja, warum man das macht, hat dann viel mit der Hardware zu tun, was man da zugrunde liegen hat. Aber wie gesagt, in den letzten Jahren verlasst
euch einfach erstmal drauf, Zeile und dann kommt Spalte. Das ist einfach so üblich. Aber wie gesagt, es gab auch mal andere Implementierungen. Führt oft zum
Problem. Ich gebe euch mal hier jetzt einfach ein Beispiel, weil mir das jetzt einfällt. Ihr fragt euch manchmal, warum ich so viel dann dazu sage. Ähm, ich
habe ja viel mit der Robotik zu tun. So und wenn man Roboter programmiert, das ist mir also dann passiert, ich hatte dann mit Kawasaki Roboter zu tun und die
haben dann Linkskoordinatensysteme im Einsatz gehabt aus lizenzrechtlichen Gründen. Das wusste ich vorher nicht und es ist ein riesen Unterschied, ob man
ein Rechtssystem oder ein Linkssystem hat. Und wenn ihr mal mit Errase programmiert und ihr wundert euch, warum das nicht funktioniert auf irgend so
Mikroprozessor oder so, dann kann das durchaus sein, dass das der erste Index dann halt die Spalte ist und nicht die Zeile. Also deshalb nachschauen. Okay,
ein Array wird in den meisten Programmiersprachen im Speicher zeilenweise gespeichert. Das wollte ich jetzt einfach nur mal zum
Abschluss da sagen. Okay, ich habe mal so ein Bild mir geholt. Ich habe die Quelle hier angegeben. Ich finde diesen Vergleich eigentlich nicht schlecht mit
so einem Apothekerschrank als Metapher. Das habt ihr schon mal gesehen. Wenn ihr vielleicht in die Apotheke da reingeht, dann zielen die die Schubladen auf. Also
das heißt, die Schubladen selbst sind wiederum Arrays. Ja, also der Apothekerschrank ist ein Array. Ich habe euch das mal hier mit den Indizes hier
bis 5 und 7 mal mit angegeben. Das sind also die verschiedenen Schubladen, die man aufziehen kann. Jetzt muss man erstmal wissen, okay, hier z.B. 24, ich
glaube, ich kann es nicht mal, oh, ich kann es markieren. Wunderbar. Also hier die Schublade 24, da wissen wir, dass jetzt die ganzen Jahmerzmittel da drin
sind, ne? Mir fällt jetzt gerade nichts anderes ein. Dann zieht man diese Schublade auf und da drin haben wir dann wiederum auch sortiert dann die
Medikamente da drin. Ja, also das erste Array, das heißt hier dieser Apothekerschrank, den wir gerade sehen, nimmt wiederum Arrays auf, was dann hier
als Metapher, das sind dann die Schubladen. Stellt euch das vor, die Schublade wird aufgezogen und dann haben wir dann auch geordnet von Position 0
bis, weiß ich nicht, Position 100. Ja, nur als Beispiel haben wir dann die Medikamente und dann weiß man ganz genau, wo liegen diese Medikamente.
Natürlich kann ich dann die Medikamente nach Namen sortieren, um sie dann halt schnell zu finden. Gut, ich denke, dass es dann noch deutlicher geworden ist,
was Erays sind. Gut, die nächste implizite Datenstruktur, die wir uns anschauen, das sind verkettete Listen. Hier geht's mir erstmal nur darum, dass
ihr ungefähr versteht, was das ist. Eine linear verkettete Liste ist eine Folge von Zellnen, die durch Zeiger verkettet sind. Ich werde gleich auf einen
abstrakten Datentypen Graf eingehen und euch da Beispiele zeigen und da werdet ihr es bisschen besser verstehen können. Die Länge ändert sich während der
Programmlaufzeit dynamisch, indem Zellen angehängt oder gelöscht werden. Also linear verkettete Listen haben dann einen Vorteil bezüglich Arrays, wenn wir
äh also nicht abschätzen können, wie viel Elemente jetzt wirklich in unserem abstrakten Datentypen so ungefähr drin sein werden. Race haben dann den
Vorteil, ich gehe jetzt noch mal die Folie zurück, ne? Wenn wir jetzt abschätzen können, dass wir auch genauso viele Schubladen haben, vielleicht mal
ein paar mehr oder auch weniger, aber wir haben ungefähr immer bei der Verwendung von unserem abstrakten Datentypen, ja, z.B. Stack können wir
abschätzen, dass wir immer so 100 Elemente haben. Dann machen Ers dann durchaus Sinn, weil wir viel viel effizienter dazugreifen können. Haben
wir aber eine gewisse große Schwankung da drunter, macht es Sinn, diesen abstrakten Datentypen eher mit so einer verketteten Liste äh zu implementieren.
Ich will euch hier nur so ein bisschen erzählen, wo dann die Vor und Nachteile sind. Ja, für uns als benutzende Person des abstrakten Datentypens ist es ja
egal, wie es implementiert ist. Also da müssen sich halt die Leute Gedanken machen, die sowas implementieren. Mittlerweile, also wir haben das Jahr
2026, wenn ich mir die ganzen Collections anschaue in Jahre ist das total effizient. Ja, und da müssen wir uns dann wirklich gar keine Gedanken
mehr machen. Gut, der Zugriff auf ein Listenelement erfolgt halt über diese Zeiger im Vorgängerelement, ne? Also, habe ich jetzt das Element 7,
dann habe ich da den Zeiger auf das Element 8. So kann ich halt dann auf das Element 8 zugreifen. Dann versteht ihr auch so, ich kann jetzt nicht so mittend
drin reingreifen. Ich kann dann immer nur ähm, wenn ich halt so mittendrin halt wäre, immer nur den den äh ja praktisch dann äh Nachfolger ermitteln,
aber jetzt nicht so mein Vorgänger. Da das dann halt manchmal ein Problem ist, haben wir auch doppeltverkettete Listen. Da haben wir halt zwei Zeiger,
ne? Wir haben so ein Element, ja, und da haben wir dann den Zeiger auf den Vorgänger, aber auch den Zeiger auf den Nachfolger. Gut, jetzt schauen wir uns
mal ein ganz wichtigen abstrakten Datentypen an, den Grafen. Der wird extrem oft eingesetzt, auch in der Spieleprogrammierung eigentlich überall.
Ja, also jetzt konzentrieren. Jetzt ist ganz ganz wichtig, dass ihr erstmal zuhört. Ein Graf besteht aus Knoten und Kanten. Jede Kante gehört zu einem Paar
von Knoten. Also Kanten verbinden, also Knoten. Kanten können attribuiert sein. So können diese Attribute Kosten oder Entfernung darstellen. Stell einfach mal
vor, wir wollen jetzt die Städte, sagen wir einfach jetzt die Hauptstädte der Bundesländer einfach über eine Bahnstrecke verbinden und dann
sind diese Städte könnten jetzt die Knoten repräsentieren und die Kanten werden jetzt, ich sag jetzt mal die ja, die Schienen, also die Verbindung und
dann könnten wir dann an diesen Kanten einfach die Entfernung Kilometer dahin schreiben. Ja, sind die Kanten gerichtet, dann ist der Graf ein
gerichteter Graf. Auch hier nehmen wir jetzt wieder das Beispiel. Wir waren jetzt gerade bei den Hauptstädten unserer Bundesländer, die wir jetzt über
Schienen verbunden haben. Jetzt kann es ja durchaus sein, dass man jetzt z.B. nur von Hannover nach Hamburg fahren kann, aber nicht von Hamburg nach
Hannover. Ja, also dann hätten wir eine gerichtete Kante. Okay, es kann auch sein, dass wie gesagt, das werdet ihr gleich sehen.
Natürlich kann man das auch so einbauen, dass man jetzt Hannover äh mit Hamburg dann verbindet, aber dann über eine andere Schiene, das ist dann auch eine
andere Kante. Okay, ein gerichteter Graf hat nur gerichtete Kanten. Das ist ganz wichtig. Also Grafen sind entweder gerichtet oder
ungerichtet, aber nicht gemischt. Ja, wenn eine Kante von Knoten Ni zum Knoten NJ führt, dann heißt NJ Nachfolger von NI und ni ist der Vorgänger von NJ. Ja,
ist jetzt so ähnlich wie bei den Listen. Wir haben Vorgänger und Nachfolger, aber für uns ganz wichtig, also noch mal, wenn eine Kante ne von Knoten Ni zum
Knoten Njürt, dann ist Nj ja der Nachfolger von NI. Eine Folge von Knoten N1, N2 bis NK. Ja, ist der Knoten NJ. Also noch mal, also
wenn wir so eine Folge haben, Entschuldigung, ne? Also hier unten in der Knoten NJ Nachfolger von Knoten NJ -1 ist, ja, für j,
dann ist das ein Fah. Uh, ja, also ihr müsst euch das einfach so vorstellen. Manchmal wollen wir auch das Stellt euch das als Untergraf vor. Ja. Und jetzt,
wenn wir so eine Folge von Knoten haben, in der der Knoten NJ Nachfolger von Knoten NJ -1, ne, für praktisch alle J von 2 bis k, dann haben wir einfach ein
Fad. So müsst euch das vorstellen. FE sind ja ganz wichtig, ne? Wenn wir auch Dinge suchen und und hier geht's mir jetzt erstmal darum, dass ihr jetzt
hoffentlich verstanden habt, was ein Graf ist. Dann müssen wir auch jetzt weitermachen. Da kommt jetzt echt viel dazu. Jetzt schauen wir uns mal an, wie
wir so ein Grafen implementieren können. Ja, jetzt werden wir Matrizen, also Adjaenszmatrix jetzt ähm benutzen und da sehen wir jetzt einen gerichteten
Grafen. Ich habe euch jetzt hier mal ein Beispiel gegeben. Wie gesagt, ihr könnt ja auch Stopp machen, ihr könnt zurückspulen. Das ist der Vorteil in
diesen Videos. Ja, ich werde euch erstmal vorlesen, was hier unten steht. Ein Graf kann mit einer Adjazenzmatrix dargestellt werden, in der eine 1 an
einer Position Ij meint, dass es eine Kante von Knoten I zu J gibt. Die Adjazenmatrix eines ungerichteten Grafen ist symmetrisch zur Diagonalen.
Ich glaube, wir fangen mal bei den ungerichteten Grafen hier rechts an. Ja, also den hier. Hier seht ihr das da. Jetzt habe ich es mal markieren können.
Damit fangen wir jetzt mal an. Wir haben die Knoten 1 2 3 4 und 5. Okay, jetzt haben wir eine Kante von 1 zu 2. Jetzt müssen wir also hier einfach mal
schauen, ne? Wir haben hier die ein, wir haben hier die ein und so weiter. Und jetzt nehme ich einfach die ein raus und schauen mir hier den Knoten 2 an. Da
steht eine 1. Also, wir haben eine Kante zwischen 1 und 2. Das ist also richtig. Dann haben wir noch von 1 zu 4 eine Kante und von 1 zu 3. So, das ist genau
das, was diese erste Zeile hier, die kann ich leider nicht markieren, aber hier die erste Zeile, ich fahre mir hier mit Mauscurser hin und her,
repräsentiert. Also, wir greifen uns hier die ein raus und schauen, mit welchen anderen Knoten die ein verbunden ist. Und wir haben ja gerade gesagt, äh
das ist jetzt symmetrisch. Ja, und das heißt, wenn ich jetzt die Z rausgreife als Knoten, die ist natürlich mit der ein verbunden, ja, weil wir hier
diese Verbindung haben, die ist ungerechtet. Also tragen wir das auch bei der 2 ein, dass sie mit der ein verbunden ist. Wenn wir den Unterschied
uns gleich angucken wollen, hier das linke Beispiel gerichtet, ne? Ich nehme die ein und sehe jetzt, dass da ein Pfeil dran ist. So, zwei, hier habe ich
die ein und da ist eine ein eingetragen als, ich sag jetzt ja Symbol, dass eine Kante zwischen 1 und 2 gibt. Es gibt eine Kante zwischen 1 und 3 und 1 und 4.
Jetzt nehme ich die zwei als Knoten hier im gerichteten Grafen. Habe aber jetzt eine 0:1 da stehen, weil ne, es gibt ja keine Kante, ja, von 2:1 und das ist
halt der Unterschied zum ungerichteten hier rechts. Gut, ich denke, das habt ihr soweit verstanden, ne? Wenn ich jetzt hier den
Knoten 5 mir anschaue hierbei gerichtet, der hat gar keine Kanten zur anderen. Schaue ich mir das dann beim Ungerichteten an, hat er natürlich zum
Knoten 4 eine Verbindung. Es gibt aber auch Adjaenszlisten, um solche Grafen zu implementieren. Ein Graf kann mit einer Adjazsliste dargestellt werden, in der
jedes Element einen Knoten darstellt. Von jedem Element startet eine Liste mit ein Knoten, die mit dem Element verbunden sind. Gut, am besten schauen
wir uns wie das im Ungerichteten zuerst an. Also hier der Teil wieder rechts. Da nehmen wir jetzt das Element 1, also den Knoten 1 und dann tragen wir in einer
Liste. Ja, also hier werden wir die implizite Datenstruktur Liste dann verwenden. Bei der Adjazen Matrix nehmen natürlich die implizite Datenstruktur
zweidimensionales Array. Ja, also hier sind wir jetzt bei der Adjazliste und ausgehend vom ersten Knoten tragen wir dann in einer Liste halt die Knoten
ein, mit denen halt der Knoten eins verbunden ist. Also schauen wir uns das hier einfach Beispiel nehmen wir zwei von zwei haben
wir zu dre von 2 zu ein also tragen wir die ein und die 3 ein. Natürlich wäre schön, wenn wir die Elemente auch irgendwie sortieren, falls wir da
irgendwie was suchen, aber das muss jetzt erstmal nicht sein. Gut, noch mal das Beispiel hier bei Ungerichteten nehmen wir die vier, ne? Springen wir
hier zu vier. Ihr seht ja den Curser ist halt mit der ein und mit der fünf verbunden, ne? Vier mit ein verbunden, vier mit fünf verbunden. Schauen wir uns
das jetzt beim Gerichteten an. Wir nehmen wir die ein. Da fangen wir an. Da sind wir mit 2, 3 und 4 verbunden. Und jetzt nehmen wir die 2. Die 2 hat dann
nur eine gerichtete Verbindung zum Knoten 3. Na ja, die 4:5, 5 zu gar nichts. Ich denke, ihr versteht, was Sache ist. Das Tail ist vielleicht noch
wichtig. Wir müssen immer erkennen, wann wir sozusagen ähm ja, wo das Ende unserer Liste ist, wenn wir jetzt noch mal einen neuen Knoten eintragen müssen,
ne? Aber das sind jetzt Details, die die Leute wissen müssen, die jetzt so eine Adjazenzliste implementieren wollen. Jetzt müssen wir ganz kurz noch mal die
Frage stellen, wann benutzen wir was? Ich gehe jetzt noch mal zurück zu Adjozens Matrix. Wenn wir also ungefähr die Anzahl der
Knoten im voraus kennen und es abschätzen können. Ich habe es ja schon vorhin gesagt. Ähm, dann nehmen wir Arays. Also, wenn wir jetzt ähm jetzt so
ein so ein Grafen implementieren wollen und sagen, na ja, wir erwarten so ungefähr 100 Knoten, ja, dann sollte man schicht ein Array von 110 nehmen, ja,
und das dann soweit aufbauen und gut ist. Der Nachteil könnte dann sein, äh wenn wir jetzt kaum Kanten in unserem System haben, dass wir echt
Speicherplatz verschenken. Ja, der Vorteil wäre, dass wir sehr sehr schnell auf die einzelnen ähm ja Knoten und Kanten zugreifen können über die
Indizierung der Errays. Das müsst euch einfach mal so vor Augen führen. Ich will euch jetzt ja nur sagen, wann verwendet man was. Also, wenn wir
ungefähr abschätzen können, äh wie viele Knoten wir haben und wenn wir auch ähm ich sag mal davon ausgehen können, dass viele Knoten miteinander verbunden sind,
dann macht so eine Adjazenszmatrixe. Ist es aber so, dass wir erstmal überhaupt nicht abschätzen können, wie viel Knoten haben wir überhaupt, dann
würde ich erstmal eine Adjazliste nehmen. Dann füge ich einfach die Knoten da rein, entferne sie wieder und und hier kann es aber sein, dass wir, wenn
wir jetzt, wenn so ein Knoten dann mit ganz vielen anderen Knoten verbunden ist, dass das hier ein bisschen entartet. Mit entarten meine ich, dass
wir dann auf einmal ganz lange Listen haben, in denen wir vielleicht dann andere Knoten suchen müssen. Oder wenn wir z.B. Pfade in unseren Knoten äh
suchen, also wo kommt man jetzt z.B. von Hannover dann nach Berlin, ne? sagen wir von Hannover müssen wir erstmal nach Hamburg fahren, dann von Hamburg müssen
wir nach Berlin fahren. Sowas so als Beispiel, wenn wir sowas suchen. Hier in dem Beispiel ist klar, da ist es egal, ob wir eine Liste oder eine Matrix
haben. Aber wenn ihr euch jetzt vorstellen könnt, dass wir ganz ganz viele Knoten dann haben, mit denen der Knoten 1 hier verbunden ist, dann
müssten wir in dieser Liste dann hier suchen. Das ist dann der Nachteil von solchen Adzenlisten. Also, ihr seht, es gibt immer wieder vor Nachteile. Oft ist
es so, dass die Menschen, die diesen Grafen dann implementieren, das gar nicht so abschätzen können. Aber jetzt kommt's noch mal. In modernen
Programmiersprachen haben wir extrem effiziente Collections. Z.B. haben wir in Java die Array List. Ihr seht, ne, schon vom Namen her ist verbindet äh die
ja, ich sag mal die Vorteile von Arrays mit Listen. Also, da können wir uns schon drauf verlassen, dass wir uns nicht mehr so viele Gedanken machen
müssen. Das haben andere für uns schon getan, aber für uns hier in der Einführung ist schon wichtig, das abschätzen zu können. Gut, dann gehen
wir mal weiter an Teil 3. Da reden wir jetzt über Bäume. Also Bäume sind spezielle Grafen. Ein Baum ist ein gerichteterzyklischer
Graf. Das heißt, es ist ein gerichterter Graf. Das ist, glaube ich, gut zu verstehen, was bedeutet azyklisch. Wir haben einfach keine Zyklen. Ja, also das
ist wichtig, dass wir es verstehen. Ich zeige auch gleich ein Beispiel. Jeder Knoten hat genau einen Vorgänger. Nennen wir einfach Eltern Knoten oder Parent.
Mit Ausnahme des obersten Knotens. Der hat nämlich gar keinen Vorgänger. Und dieser Knoten, warum nennen wir den obersten Knoten? Ähm, na ja, weil der
steht dann, wenn wir es grafisch darstellen wollen, so ein Graf dann ganz oben. Der hat also kein Vorgänger und dieser Knoten, der wird Wurzel genannt
oder Root. Manchmal habe ich ähm ja, Darstellungen bewusst äh genommen, um ich sag mal, was heißt meine Studierende zu verwirren? Ich will ja einfach nur,
dass die darüber nachdenken. So ähnlich wie, wenn man eine Landkarte hat und dann immer über oben und unten redet. Das halte ich für unprofessionell. Es
gibt Norden, Süden, ne, Westen, Osten, dann weiß jeder, worüber ich spreche, aber links und rechts hängt ja davon ab, wo ich gerade hingucke. So ähnlich ist
es hier. Wenn wir jetzt sagen, der oberste Knoten, na ja, schaut einfach, welcher Knoten keinen Vorgänger hat in so einem Baum. Das ist die Wurzel. Ja,
ein Knoten ohne Nachfolger heißt Blatt oder auch lief. Ein Baum des Datentyps T ist eine leere Struktur oder ein Knoten des Typs T mit verbundenen Bäumen. Das
nennen wir dann auch Teilbäume. So kann jeder Knoten als eigener Baum betrachtet werden. Hat jeder Knoten nur einen Nachfolger. Solchen Nachfolger nennen
wir dann auch Kindknoten oder auch Child. Dann degeneriert der Baum zu einer verketteten Liste. Ist ein Knoten X auf Ebene i, dann ist der Nachfolger
von X auf Ebene i + 1. Die Wurzel ist auf Ebene 0. Die Anzahl der Ebenen -1 ist die Höhe des Baums. Die Ebenen Nummer eines Knotens ist seine Höhe. Ja,
ihr werdet euch jetzt Fragen stellen, warum ihr das alles wissen müsst. Das ist extrem wichtig, wenn wir bestimmte Algorithmen einsetzen. Hier geht es
jetzt erstmal darum, ja, Grundlagen der Informatik. Ich will das Niveau jetzt auch hier bei YouTube nicht extrem hoch bringen, aber schon so. Ich möchte euch
auch fordern, also ich gehe davon aus, dass meine Videos von Leuten geguckt werden, die auch wirklich Interesse haben, hier mehr Information zu bekommen
und nicht in, ich sag jetzt mal 3 Minuten erklärt bekommen, was ein Baum ist, weil es geht gar nicht. Man kann sowas nicht in 3 Minuten erklären.
Glaubt solchen Leuten nicht. Ihr müsst euch einfach Zeit geben. Ich will auch noch was sagen, äh was so die Ebenen angehend. Äh, da gibt's in der
Informatik äh ja, was heißt ein Glaubenskrieg? Aber manche ähm sagen, es beginnt bei Ebene 0, manche sagen bei Ebene 1, na ja, schaut einfach dann mal
äh nach. Also, es kommt in der Literatur mal so und mal so vor. Das wollte ich nur mal erwähnen. Kann verwirren, ne? Bei uns hier in unserem Kontext ist die
Wurzel auf Ebene null. Ja, schauen wir uns mal jetzt endlich so ein Baum an. Äh, ich gebe jetzt mal gleich ein Beispiel von so einem binären
Baum. Ein binärer Baum, der hat keinen einen oder maximal zwei Nachfolger. Wir schauen uns mal hier die 20, ne? Also, das ist jetzt ein Knoten. Ähm, der hat
noch einen Wert ähm einfach den Wert 20. So, dann hat gibt es zwei Zeiger. Der eine Zeiger zeigt hier auf die 11, der andere auf die 23, aber es gibt nicht
mehr als zwei Nachfolger. Ja, und äh jetzt schauen wir uns hier unten die 18 an. Das ist ja ein Blatt. Er markiert wieder nur alles. Also hier unten ist
ein Blatt. die 18 und ihr seht, wenn da so ein schwarzer Punkt eingetragen ist, das hat man einfach mal so gemacht, dann ist es ein sogenannter Nullpointer, der
referenziert halt auf nichts, ne? Und somit hat die 18 hat gar keine Nachfolger, die 13 hat einen Nachfolger und und ähm ich hatte ja auch vorhin
gesagt, dass so ein auch so ein Binärbaum natürlich entarten kann. Sagen wir mal die 20 hat nur als Nachfolger die 23, dann die 23, die 22 und so
weiter und so fort. Das kann dann wie eine Liste aussehen. Da macht so ein Binärbaum vielleicht auch nicht wirklich Sinn. Warum nutzen wir häufig
Binärbäume? Na ja, das werden wir auch gleich sehen. Wir können die Elemente auch gleich sortieren, ne? Binäre Bäume werden häufig dazu verwendet, um
Elemente sortiert in aufsteigen oder absteigender Reihenfolge abzulegen. Solche Bäume sind binäre Suchbäume. Wow, das ist cool. Also im Prinzip geht's
darum, hier haben wir die 20 und jetzt sagen wir, die 11 ist kleiner, die 23 ist größer. So haben wir das jetzt hier abgelegt.
Dann schauen wir uns die 11 an. Dann haben wir, wie gesagt, das ist eine grafische Darstellung jetzt eines binären Baums, indem ich jetzt die acht
einfach links geschrieben habe, so nach dem Motto, die acht ist kleiner als die 11 und die 13 ist größer als die 11. Wie gesagt, da kann man auch Leute
verwirren, die jetzt einfach glauben, ja, was wings steht, ist kleiner und blablabla. Nee, ihr müsst genau drauf achten, äh was ihr da macht, ja, nicht
wie jetzt die Darstellung ist, weil intern Computer sieht das ja nicht so aus wie hier in der grafischen Darstellung des Grafen. Gut. und die 18
ist größer als die 13. Deshalb ist jetzt grafisch hier rechts dargestellt, ne? Und wie gesagt, wenn sie jetzt hier links stehen, würde es auch vollkommen
egal, weil es geht einfach darum, ob es halt der erste oder der zweite Zeiger ist oder der nullte und der erste Zeiger, wo was dann halt äh referenziert
wird. Okay, ich denke, ihr habt das verstanden. Binäre Suchbäume sind extrem wichtig. Haben wir immer wieder jeden Tag überall, ne? Ihr wisst, ich habe
viel mit Robotern zu tun, aber auch Spielprogrammierung immer wieder binäre Suchbäume. Extrem wichtig, ne? Grafen sind für uns Informatikmenschen
eigentlich das Wichtigste. Ähm, nur mal so ein kleiner Hinweis, ich erzähle euch hier Sachen, wo ich z.B. im Informatikstudium an der TU Braunschweig
eine ganze Vorlesung hatte, wirklich, die hieß diskrete Strukturen, hauptsächlich Grafen, Grafen, Grafen bis zum Abwinken. Ihr könnt euch gar nicht
vorstellen, was man da als Informatikmensch alles mit machen kann. Gut, die maximale Anzahl von Knoten auf Ebene iht dann 2 hoch i und die maximale
Anzahl der Knoten eines binährten Baums der Höhe h ist dann halt 2 hoch 0 bis also wenn man addiert bis 2 hoch h, also 2 hoch h + 1 -1. Okay, also ihr seht,
wir habe ich ja gerade gesagt, ne, in den diskreten Strukturen, dann lernen wir Dinge kennen. Wir können Grafen einfärben. Ihr könnt euch da ganz viel
anschauen, ne? Es ist ist nur alles Mathematik. Das ist vollkommen klar. Ja, ein vollständiger Binärbaum ist ein Baum mit maximaler Knotenanzahl auf jeder
Ebene mit Ausnahme der Unterste. Um ein bestimmtes Element in einem sortierten vollständigen Wärb mit NKnoten zu finden, braucht es nur log,
also Logarithmus dualis n Schritte. Oh, wenn ihr jetzt nicht wisst, worum es jetzt hier geht, macht nichts. Hört euch das einfach mal an. Ich werde später
noch ein bisschen was so Notation sagen. Es geht einfach darum, wenn wir solche binären Bäume haben und die sind z.B. vollständig, dann können wir
garantieren, dass wir halt nur diese log n Schritte brauchen. Ja, in einem balanzierten Baum differieren die Höhen des linken und rechten Unterbaums eines
jeden Knotens um nicht mehr als eins. Warum gebe ich euch das an? Also, wir müssen unterscheiden, sind Bäume vollständig, sind sie balanciert? Weil
wenn wir sie vollständig und balanciert hinbekommen, dann können wir bestimmte Algorithmen implementieren und dann auch wie gesagt garantieren, dass es maximal
so lange dauert, um Element z.B. zu finden. Ja, wenn wir solche binären Bäume traversieren, was bedeutet das? Es gibt
drei Möglichkeiten, einen Binärbaum zu durchlaufen. Das ist diese Traversierung. Wir haben erstens Preorder, das bedeutet zuerst den Knoten
zu besuchen und danach den linken und rechten Teilbaum. Inorder bedeutet zuerst den linken Teilbaum zu besuchen, danach den Knoten und zum Schluss den
rechten Teilbaum. Und Postorder bedeutet zuerst den linken und den rechten Teilbaum zu besuchen und danach den Knoten.
Wann wir wie was machen, hängt davon ab, was wir wollen. Ja, ich wollte euch jetzt hier nur sagen, wie wir Bäume traversieren können und ja, ein
sortierter Binärbaum hat bestimmte Eigenschaften. Er ist entweder leer oder es gilt für jeden Knoten. A. Alle Schlüssel des linken Unterbaums sind
kleiner gleich der Schlüssel des Knotens. Alle Schlüssel des rechten Unterbaums sind größer gleich der Schlüssel des Knotens und drittens, alle
Unterbäume sind selbst sortierte binäre Bäume. Okay, die Schlüssel sind die Elemente, die sortiert werden und dann und nach
denen im Baum gesucht werden sollen. Ja, also wir wollen ja suchen, deshalb nutzen wir diese binären Suchbäume. Jeder Knoten hat einen Schlüssel und
verweise zum rechten und linken Teilbaum. Operationen können leicht rekursiv formuliert werden, weil jeder Knoten selbst auch Teilbaum ist. Ja, es
wird immer komplexer und komplizierter. Ich gehe jetzt mal Folien zurück. Schauen wir uns das hier an. Wir haben ja diese grafische Darstellung von
diesem Binärbaum. Das ist ja ein binärer Suchbaum, das habe ich euch schon erklärt. Also, wir nehmen jetzt einfach mal so ein Element, also so ein Knoten.
Hier haben wir einen Schlüssel. Da steht eine 20 jetzt als Wert drin. Also noch mal, jeder Knoten hat einen Schlüssel. Und dann haben wir in dem Sinne
Vorgänger und Nachfolger, aber wir haben ja jetzt diese Regeln. Jetzt gehe ich wieder Folien nach vorne. Ja, wir haben ja wieder Regel. Alle Schlüssel des
linken Unterbaums sind kleiner gleich. Ganz ganz wichtig, ne? Also Unterbaum. So müssen wir das aufbauen. Okay.
Einfügen eines Elementes X in einen sortierten binären Baum. Das wird jetzt anstrengend. Ich werde das mal einfach ganz kurz vorlesen. Ihr könnt entweder
jetzt auf Geschwindigkeit unendlich setzen, um einfach darüber hinwegzugehen, aber es ist schon mal wichtig, dass wir uns das mal anschauen,
wie man das machen kann. Wir haben hier ein Modul, ne, noch mal an also Modularisierung denken. Das Modul heißt Insert. Da wollen wir also praktischen
Element einfügen und hier haben wir halt den binären Baum. Okay, also wenn der Baum existiert, ja, dann mache ich folgendes. Ansonsten hier im Pseudocode,
erzeuge Knoten mit X als Schlüsselwert. Setze Unterbaum Verweise des neuen Knotens auf Nil. Lasse T auf den neuen Knoten verweisen. Okay, haben wir also
jetzt hier den binären Baum, der existiert. Also hier überprüfen wir das dann, wenn x, also das Element kleiner Daten von t,
dann fügen wir x im linken Unterbau von t ein. Ihr seht, es ist recht einfach. Und jetzt kommt noch mal das mit diesem rekursiven. Ja, also wir rufen ja, wir
haben ja das Modul Insert und das Modul Insert ruft sich selbst auf. Na, aber jetzt dann praktisch äh wieder mit X, aber mit dem linken Unterbaum von t also
größer, ja, oder dann halt gleich, weil hier haben wir ja nur die Überprüfung, wenn es kleiner ist. Also größer oder gleich, dann f(x) größer, dann Daten von
t, ne? Also größer als die Daten von t. Dann haben wir das Insert auf den rechten Unterbaum und ansonsten wenn es halt gleich ist, fügen wir es halt nicht
ein, ne? Also nichts tun, da X schon vorhanden ist. Uh, also ich glaube, so schwierig war es auch nicht, das jetzt in Java zu implementieren, ist eine gute
Übung für euch. Das würde ich euch auch empfehlen. Natürlich solltet ihr Java programmieren können, aber ihr wisst, da könnt ihr euch ja die ganzen
Vortragsreihen anschauen. Also wie gesagt, sollte jetzt so ein Beispiel sein, wie man jetzt so ein Element einfügen kann. Ja, dann interessiert uns
auch, wie wir dann so ein ähm ja, Knoten mit dem Schlüssel kleinen X löschen können. Ja, also da stellen wir uns erstmal die Frage, gibt es einen Knoten
mit Schlüssel X? Dann müssen wir nichts tun. Also, wenn es den nicht gibt, ne? Also, gibt es kein, dann müssen wir auch nicht löschen. Super. Zweitens, Knoten X
mit Schlüssel X hat kein oder genau einen Nachfolger. Ja, also wenn er kein hat oder genau ein Nachfolge, dann 2a ändere den Verweis auf den Knoten X in
einen Verweis auf den Nachfolger von X oder auf Nall, falls es keinen Nachfolger gibt. Und 2b lösche den Knoten X. Okay, hat jetzt der Knoten X
zwei Nachfolger, dann ersetze Knoten X durch das größte Element im linken Unterbaum von X. Ja, das war's. Also wir müssen uns immer Gedanken machen. Das
sind ja jetzt hier dann Algorithmen, die wir implementieren müssen für also wenn wir jetzt so ein wie nennen Suchbaum ADT implementieren wollen, dann müssen wir
wissen, wie das geht. Ja, also ist immer noch eine gute Übung. Hier sind jetzt Beispiel dazu, ne? Löschen eines Knotens X mit Schlüssel G in T. Ja, wenn man
sich das dann hier anschaut, was dann passiert. Also das 11 rutscht dann praktisch hier nach oben. Ja, klar. Also ich ich sage so oft in den
Vortragsreihen, nehmt euch ein Zettel und ein Stift. Ich weiß, ihr seid es wahrscheinlich nur noch gewohnt mit eurem Smartphone zu arbeiten, mit
Bildschirm zu arbeiten, irgendwie rumzuwischen, irgendwo zu tippern, so schnell wie es geht und so kurz und ihr seid immer in Hektik, aber hier echt
setzt euch hin, ja, malt euch das hier einfach ab oder zeichnet euch das ab. Also wirklich händisch, also glaubt mir, euer Gehirn funktioniert
vielleicht nicht so, wie euch das vorstellt. Okay, das war jetzt ein komisch formuliert Entschuldigung, aber was ich sagen möchte, also die ganzen
kognitiven Prozesse, die in eurem Gehirn ablaufen, werden enorm gepusht, wenn ihr ein Stift nehmt und selbst aktiv werdet. Ja, übergibt es nicht den Computer
alles, ne? Auch Rechtsschreibprüfung, ihr seht es ja, warum? Ja, die generieren die Fertigkeiten der der Menschheit bezüglich Rechtschreibung. Na
ja, ihr tippert irgendwo, der Computer wird das dann rot unterkringeln und ihr ändert das dann einfach so häufig, bis es passt oder die KI macht schon
Vorschläge, ersetzt das automatisch und dann verliert ihr die Fähigkeit, es selbst einzuschätzen, ne? Also okay, ja, da kann ich stundenlang drüber reden,
seht es mir nach. Okay, jetzt müssen wir uns noch anschauen, wie wir so ein Knoten X mit Schlüssel gn löschen. Äh, man könnte denken, äh, dass es
praktischer ist, X nicht zu löschen, sondern nur durch den Schlüssel des Knotens zu ersetzen. Dies ist jedoch keine gute Lösung, da zum einen das
Ersetzen von Daten kopieren bedeutet, was hohe Laufzeiten verursachen kann und außerdem wird jeder Verweis auf den Knoten, der als Schlüssel F, ne, also
der Schlüssel F enthält, ungültig wird. Also machen wir es lieber so. A, ich markiere das mal hier. A, setze die Verweise auf den Knoten F, also groß F
mit dem Schlüssel F auf null. B0. Setze die Nachfolger von F auf die Nachfolger von X. B1. Ändere vorher existierende Verweise auf X, so dass
diese auf F zeigen. C. Lösche den Knoten X. Ja, also haben wir es einfach noch mal zusammengefasst. Jo. Balancierter Baum. Ein Baum ist in
einem balancierten oder ausgeglichen Zustand, wenn sich für jeden Knoten die Höhen der linken und rechten Teilbäume um nicht mehr als eins unterscheiden.
Wenn die Anzahl der Knoten n bekannt ist, kann ein balancierter Baum aus n Eingabedaten konstruiert werden. A ein Knoten dient als Wurzel. B. Erzeuge den
linken Unterbau mit K links = NBE Knoten mit diesem Algorithmus und c erzeuge den rechten Unterbau mit k rechts = n - k links -1 Knoten mit diesem Algorithmus.
Jo, wie gesagt, einfach hinsetzen und äh überlegen. Ja, ein mit diesem Algorithmus erzeugter Baum ist nicht sortiert. Ganz wichtig. Also, wenn wir
das auch noch haben wollen, müssen wir dann auch noch Aufwand treiben, das Ganze zu sortieren. Hier ging es einfach nur darum, den Baum auszubalancieren.
Ein Algorithmus zum Einführen in einem sortierten binären Baum, so dass der Baum ausgeglichen bleibt, kann in diesem Paper nachgelesen werden. Ich markiere
euch das am besten. Ich weiß, die meisten, die es jetzt hier sich anschauen, denken sich: "Oh Gott, warum soll ich das machen?" Ja, ich weise ja
nur daraufhin, dass es sowas gibt. Ich weiß darauf hin, dass es balancierte binäre Suchbäume äh gibt und die nennen wir AVL Bäume, die nach den ja
sowjetischen Mathematikern, ich kann die Namen wahrscheinlich schlecht aussprechen, also Edison Welky und Lendes, ne, entwickelt worden und
das war schon 1962, ne? Also ihr seht, dass man sich ganz ganz viel Zeit ja genommen hat, um solche Sachen schon zu entwickeln, obwohl die Computer noch gar
nicht so weit waren, aber man hat sofort verstanden, dass das ganz wichtig ist von den Datenstrukturen her. Okay, ich weiß, es waren jetzt viele Informationen
und noch mal Grundlagen der Informatik. Dennoch weiß ich darauf hin, dass es sowas gibt. Ihr könnt erstmal euch überlegen, was ist ein Graf, ja, was ist
ein Bum, was sind Knoten, was sind Kanten und so weiter und dann tastet ihr euch da immer mehr daran. Ja, jetzt haben wir noch Teil 4, da reden wir über
das Hieb. Ja, wie kann man eine Prioritätswarteschlange implementieren? Das jetzt die Frage, die ich euch stelle. Denk noch mal dran, ganz ganz am
Anfang abstrakte Datentypen, da haben wir über Prioritätswarteschlangen gesprochen und jetzt wäre die Frage, wie könnte man sowas implementieren?
Ein Hieb oder auch Halde und Haufen genannt ist ein spezieller binärer Baum mit Knoten, den je ein Wert zugeordnet ist. Der Baum ist vollständig. Alle
Ebenen sind besetzt mit Ausnahme möglicherweise der untersten Ebene, wo alle Knoten links angeordnet sind. Der Schlüssel eines Knotens ist größer
gleich den Schlüsseln seiner beiden Nachfolger. Der größte Schlüssel ist damit an der Wurzel des Baums. Ein Hieb ist eine geeignete Datenstruktur zur
Implementierung einer Prioritätswarteschlange. Okay. Ja, ich weiß, es wird jetzt auch wieder komplex. Ich kann ja immer nur
sagen, stelle euch das vor. Grundlagen der Informatik, blablabla und ihr müsst natürlich aktiv sein. Das ist immer das, was ich auch bei meinen Studierenden so
vermisse, ne? Die lassen sich berieseln, die gehen zur Vorlesung, um ihr ja, was heißt Gewissen zu beruhigen, aber die sitzen dann da in der Vorlesung, sie
hören zu, denken aber vielleicht teilweise an andere Dinge und wenn sie dann selbst aktiv werden müssen, ist es immer schwierig sich aufzuraffen, ne?
Also Prokrastination, das kennt ihr wahrscheinlich auch. Aber wenn ihr hier bei den Videos seid, dann überlegt euch doch mal dann entweder holt ihr euch
noch mal andere Videos dazu, aber das dann auch mal selbst zu implementieren. Ja, implementiert doch dann mal ein Hieb, dann versteht ihr einfach besser,
worum es geht und das würde ich euch auch empfehlen, ne? Ihr müsst besser sein als die KI, das sage ich immer wieder, ne? Wenn ihr auch später noch
einen Job haben wollt. Okay, also ein Hieb kann mit Arrays oder verweisen implementiert werden. Ein Array A mit N Elementen ist ein Hieb, wenn folgendes
gilt. Das ist die sogenannte Hiebbedingung. Ja, also wir greifen halt den Index j -1/ halbe raus und der muss größer gleich sein als A j und das gilt
für alle Indizs 1 kleiner= jn kleiner n, ne? Also j ist kleiner n. Okay, damit ist A0 = A1 A2 und A1 größer = A3 A4 und so weiter. Also ist A0 das
Maximum, ne? Ich markiere das mal hier für euch noch mal. Das ist klar, das haben wir gesagt. Falls hohe Prioritäten durch kleine Zahlen repräsentiert
werden, geht es halt dann umgekehrt, ne? Den ist einfach nur hier haben wir größer Gleich und hier haben wir dann kleiner Gleich. Ja, ich wollte es nur
mal einfach erwähnen. Am besten zeige ich dann ein Beispiel. Also HEP Implementation mit einem Array als Baum jetzt dargestellt. Also die
Implementierung ist das Array. Also schauen wir uns hier oben an. Hier haben wir so ein Index dann von 0 bis 14. Also wir haben 15 Elemente und hier haben wir
die Werte, die dargestellt sind, ne? Könnt das auch Schlüssel nennen. Dann schauen wir uns d mal jetzt das so an. Also die 97, wenn wir das jetzt mal hier
so durchgeht, steht halt ganz oben. So soll es auch sein. Ich habe dann für euch den Index hier dahinter geschrieben, ne? Also, wenn wir jetzt
die neun rausgreifen, das ist dann der Index 13, ne? Also hier. Und na ja, die 14 ist halt frei, falls wir was einfügen wollen, ne? Ja, ihr müsst euch das
anschauen. Natürlich stellt man sich dann auch die Frage, ähm wie implementieren wir sowas? Und da kann es dann wirklich beliebig werden, also
beliebig komplex werden. Im folgenden Code werden die Grundlagen der Hiebdatenstruktur in Java gezeigt. Der Code genügt nicht in Anforderung
professioneller Software, dann werdet ihr immer euch die Frage stellen, ja, warum? Warum? Warum? Na ja, hier Einführung Einführung, wie ich es auch
in der Vortragsreihe äh zu Java sage, wenn wir doch gleich so anfangen, äh also praktisch äh bei der Krönung von allem, ähm dann wird es für euch doch
immer schwieriger dahinzukommen. Ja, und außerdem müssen wir es hier oder ich möchte es hier auf einer Folie oder mehreren Folien darstellen. Das muss
kompakt sein. Ja, also es gilt jetzt für Menschen, die jetzt da den Einstieg haben in Sachen Hieb. So, es wird angenommen, dass ein Hap mit einem Array
H realisiert wird und die Variable end mal hier kurz markiert bezeichnet die Position nach dem letzten Element. Und ja, was wir jetzt hier machen, das ist
wie gesagt anstrengend. Ihr könnt Pause machen, Geschwindigkeiten verändern. Ihr solltet dann von mir ist auch erstmal Zwe und Stift nehmen, versuchen das
nachzuempfinden oder ihr könnt einfach sagen, ja, ja, ich weiß jetzt, was ein Hieb ist, reicht mir. Und dann sage ich schon mal bye bye und dann zum nächsten
Kapitel. Aber für die, die es jetzt interessiert, gehen wir mal weiter. Ja, also wir haben da eine Klasse Inthieb, also ein Hieb, der Integerwerte
aufnimmt. Da haben wir das H, habe ich gerade gesagt, dann haben wir das End. Ganz wichtig, dass wir Kapseln, ne? Soll private sein. Dann haben wir den
Konstruktor, daübergeben wir dann ein Array und dann erzeuge ich halt mein H aus dem, was ich übergeben habe mit dem Clone, setze die Endposition auf null.
setze überhaupt an habe ich eine lokale Variable POS genannt, die setze ich auch auf null. Solange halt POS kleiner H längs ist, ne? Pus ich dann
dementsprechend die die Sachen in meinen Hieb da rein. Ja, also wir haben ja hier dann das H und da greif ich dann auf das POS, also H0
zu und das Push, ne? Das müssen wir uns glaube ich an anschauen, ne? Prüf für die Hiebbedingung. Das muss ich immer wieder aufrufen. Es muss ja immer ein
Hieb sein, ne? Okay, gut. Dann haben wir die Möglichkeit, ich habe dann hier überladen. Ich habe einen weiteren Konstruktor, da übergebe ich dann Inhb
und das ist dann halt mein Original. Dann wird das dann einfach dann kopiert. Okay, gut. Dann gehen wir weiter. Wir haben das Clone, ne, das wir auch
implementieren müssen. Ist auch ziemlich leicht, muss ich wenig zu sagen. Natürlich, wenn ihr jetzt von Java noch nicht so viel wisst, ist es nicht
leicht. Das ist klar, ne? Dann verweise ich halt darauf auf die andere Vortragsreihe. Dann haben wir so ein Size. Dann gehen wir einfach das End
zurück. Dann prüfen wir die Hiebedingung, ne? Ich gehe jetzt noch mal Folien zurück. Einfach die Hbbedingung, die ich ja hier angegeben
habe, das ist die Hiebedingung, die wir überprüfen müssen, ne? Okay. Also, prüfe die Hbedingung und dementsprechend äh setze ich das äh
um. Ja, hier ist natürlich ein bisschen, deshalb sage ich ja, professionell ist das jetzt nicht einfach Hiebingung verletzt und dann brechen wir einfach
hier ab. Das sollten wir natürlich nicht machen in der professionellen Softwareentwicklung, da müssen wir halt einfach drauf reagieren. Okay. Ja, dann
haben wir das Push. Das will ich jetzt auch nicht alles vorlesen. Ihr könnt ja einfach jetzt Pause machen. Wir pushen dann Elemente in das Hieb rein.
Gut, ne? Hier steht dann nun den Hieb reorganisieren, ind das Element hochsteigt oder anders formuliert, indem man alle Vorgänger, die schwerer sind,
ne, also die halt größer sind, auf den richtigen Platz sinken lässt. Ja, das ist üblich, dass man das so macht und wie gesagt, geht da durch, dann wichtig,
dass wir immer noch die Hibbedingung überprüfen, dass wir das einhalten müssen, dass wir hier auch keine Fehler gemacht haben. Natürlich können wir auch
drauf reagieren, aber es sollte hier auch soweit funktionieren, ne? Hab den Code auch mehrfach ausprobiert. Schaut euch das bitte dann an. Dann haben wir
das Pop, ne? Ähm, da wichtig das letzte Element, ne, nach H0 bringen, dann bis zur korrekten Position heruntersinken lassen, sukzessiv mit den Kindknoten
vergleichen und gegebenfalls tauschen. Leichte Nachfolger lässt man auf den richtigen Platz hochsteigen, ne? Nach H0 bringen und tauschen ist nicht
notwendig. Wert letzten Elements in Variables speichern für die Vergleiche entnehmen. Ihr werdet euch sicherlich die Frage stellen, warum mache ich jetzt
nicht ein deliziertes Video dazu? Kann das sein, dass ich das mache? Hier geht's einfach nur darum, dass ihr euch damit beschäftigt, weil es euch auch
trainiert, ne, gewisse Dinge besser zu verstehen, warum man das auch so dann implementieren äh ja könnte. Äh, ihr versteht das Hieb deutlich besser. Und
jetzt für die, die sich jetzt auf mögliche ja vielleicht Klausuren vorbereiten, wie gesagt, ich lasse schon lange, lange, lange keine Klausuren mehr
schreiben, aber es kann ja sein, dass halt Kolleginnen oder Kollegen Klausuren schreiben lassen. Ähm, ich gehe immer schwer davon aus, also ich habe ja
selbst auch mal Klausuren äh entworfen. Ist immer schwierig dann ähm ja, verschiedene Aufgaben zu finden mit einer gewissen Komplexität. Ähm, was ich
sagen möchte ist, dass viele dazu neigen, dann Aufgaben hier aus diesem Bereich zu nehmen. Ja, also so ein Pop, so ein Push. Äh, wenn ihr wisst, wie es
geht, dann seid ihr in der Klausur auch fit, ne? Geht aber auch manchmal davon aus, in so einer Klausur könnt ihr keine Hilfsmittel verwenden. Also z.B. bei uns
an der Fakultät ist das sehr häufig so und dann ist es gut, wenn ihr das trainiert habt, ne? Deshalb bringe ich euch hier solche Beispiele.
Ja, dann haben wir noch das Top, dann sowas wie ein Show Array, das gibt das dann ganze aus. Natürlich kann man das wie gesagt alles schöner implementieren,
dann als sortiertes Array. Also wie gesagt, ich habe den Code mehrfach getestet. Heißt jetzt nicht, dass da keine Fehler
drin sind, ne? Ihr wisst, in Software ist meistens Fehler, aber ich gehe mal von aus, dass ich da ganz gute Arbeit geleistet habe. Okay, dann haben wir so
ein Main als Beispiel. Ihr seht, das ist genau das Beispiel, was ich hier genommen habe. Ich gehe jetzt mal Folien zurück. Wir merken uns, wir sind bei
169. Ich glaube, die meisten von euch habe ich schon verloren. Macht nichts. Das ist das, ne? Also, wenn wenn ich jetzt so Folien mache oder auch Aufgaben
stelle, ich muss die alle erstmal selbst implementieren, diese Aufgaben, weil ich muss ja sichergehen, dass ich hier keinen Scheiß erzähle. heißt jetzt
nicht, dass ich mich manchmal vielleicht verspreche, ja, und das ist klar, aber geht ziemlich sicher, dass ich äh mich selbst kontrollieren muss, ob ich da das
auch alles richtig gemacht habe. Also, das ist dann hier das Beispiel dazu. Und dann könnt ihr das umsetzen. Ja, viele fragen sich dann auch, oh Mensch,
warum hat er das jetzt nicht einfach im Video diesen ganzen Quellcode da drunter gehängt? Ja, kommt immer so eine lapidare Antwort. Ich möchte ja, dass
ihr selbst das macht, ja, damit ihr auch die Tastatur besser bedienen könnt. Da haben wir jetzt so ein Hieb implementiert, genauso wie ich euch das
gerade jetzt gezeigt habe. Dann können wir über die Methode Pop ähm so ein Hieb dann sortieren. Ja, also ein Hiebsort ist ein Algorithmus, um die Elemente im
HB zu sortieren. Also wie gesagt, wir nutzen das aus, dass hier das erste Element an das Ende des HBs bewegt wird, wenn wir so ein Pop sagen. Okay, also
jetzt wissen wir auch, dass wir so ein Hieb auch fürs Sortieren nutzen können. Wow, das war Kapitel 5. Weiß nicht, wie lange das jetzt gedauert hat. Ich weiß,
Kapitel 5, das ist schon ziemlich hart. Also, man muss sich damit beschäftigen. Ihr müsst jetzt wirklich fleißig sein, wenn ihr weiterkommen wollt in der
Informatik. Ja, ich habe euch viele Sachen jetzt gezeigt. Abstrakte Datentypen sind ekant wichtig für die Informatik. Ich habe euch dann auch
einen Grafen gezeigt. Auch dort habe ich X mal gesagt, super wichtig, wird immer wieder eingesetzt. Ihr müsst jetzt wirklich Zeit investieren, wenn ihr
weiterkommen wollt und auch das mit dem Hieb müsst euch anschauen. Ja, dann sage ich vielen Dank, dass ihr hier durchgehalten habt und natürlich gibt's
auch bald das Kapitel 6. M.