Hallo und herzlich willkommen zu Vorlesung Tick-Nackits.

Also ich heute von Nürnberg in Google Maps die Adresse eingegeben habe, ich habe einfach

mal 7 mal eingegeben und dann habe ich per Zufall auf die Bilder geklickt.

Das war wirklich ein lustiger Raschen heute.

So, so kleiner Spaser-Mannfangen, ja, fanden wir sehr lustig.

Wir haben immer das wahr, es war echt lustig.

Also, wo sind wir?

Leider zieht das Semester so seine Runden, das heißt wir haben größte Teile bereits beendet,

das heißt wir fangen heute mit einem neuen größten Blog an, also einfach bei Google Maps

H7 eingeben und dann bin ich mal das Bild.

Wir fangen heute mit einem neuen Blog an und insbesondere soll es um die soll es in diesen

Blog um Grafen gehr, ich habe schon Grafen und Bäume gehen, Bäume sind natürlich eine bestimmte

Grafen und wir werden insbesondere besprechen, was sind Bäume.

Dabei wollen wir insbesondere verstehen warum es praktisch jeder Anwendung Bäume in den

großen Bäume nicht wegzudenken sind und wir werden uns auch überlegen, wie bauen wir

in diese Bäume geschickt auf, was für Möglichkeiten haben wir denn.

Wir fangen heute relativ einfach an mit sogenannten Binerbäumen, die die Informatik

in der Schule gehört haben am Binerbäumen, höchst wahrscheinlich schon mal gesehen.

Binerbäumen bilden die Grundlage für praktisch alles, wir werden dann im folgenden

sehen, dass man die Nährbäume auch anders aufhassen kann indem man nicht nur

höchstens zwei Elemente zusammenfasst sondern in den Knoten, was im Binerbäumen

wir sehen, die sehen typischerweise so aus und wir werden danach in der nächsten

Vorlesung uns B-Bäume anschauen und B-Bäume haben die Idee, dass man einfach

wesentlich mehr Elemente in einem Knoten speichert.

Warum macht man das? Weil die Hoffnung ist, dass man quasi möglichst wenig

Plattenzugriffe braucht und danach werden wir im letzten Teil

AVL-Bäume uns anschauen und AVL-Bäume sind im Wesentlichen Bäume die

versuchen immer einen ausbelangteten Baum zu haben.

Wir werden das gleiche am Anfang sehen, dass wenn man Binerbäume

ungünstig aufbaut, dann degeneriert das im Wesentlichen zu

Listen und dann sind die wunderschöne Eigenschaften kaputt.

Also wir überlegen uns quasi, was für mögliche Braumstrukturen gibt es,

was für Möglichkeiten haben wir und wann ist welche Struktur eigentlich besser

als eine andere? So, dann legen wir mal los. Warum machen wir Bäume

überhaupt? Klar, ist die Grundlage für ganz, ganz viele Anwendungen.

Insbesondere wenn es darum geht, dass wir große Datenmengen

effizient durch suchen wollen, dann brauchen wir Bäume, wenn wir so genannte

authentifizierte Datenstrukturen wollen, ja, so beim normalen Binerbäume.

Also wenn wir quasi hier noch mehrere Elemente haben, dann stellen wir

in der Regel die Frage, ist ein Element in diesem Baum enthalten, aber wir

wollen nicht unbedingt eine Art Beweis haben, dass dem auch wirklich so ist.

Es gibt keine Authentifikation dafür und das ist insbesondere was,

was wir uns dann in den nächsten Blöcken nach den Bäumen anschauen.

Das ist quasi hier. In diesem Teil schauen wir uns dann authentifizierte

Baumstrukturen an. Aber um die zu verstehen muss man natürlich erst mal

die Grundlage haben. Was ist formal ein Baum? Naja, formal ist das ein

ungerichteter Graf. Grafen haben wir mittlerweile lieben und zu

ein bisschen Hassengelernt.

Das ist ein ungerichteter Graf. Worauf es besteht, ja, das können wir

nun zu genügelm aus einer Menge aus Knoten und aus einer Menge von Kanten