So, willkommen zur letzten IWGS-Vorlesung dieses Jahr. Wir haben damit schon zwei Drittel geschafft

von diesem Semester. Sieht auch mehr so aus, als ob ich sie unterschätzt habe in ihrer

Geschwindigkeit. Sie waren im Wesentlichen fertig schon 90 Sekunden bevor das Ding aufhörte.

Bevor ich das vergesse, möchte ich mich bedanken, es gibt hier Personen, ich glaube sogar anonym,

die Fehler melden im Text und das ist sehr hilfreich, denn dann kann ich sie korrigieren.

Also, bitte weiter so machen, wer auch immer das ist. Sie sollten sich auch nicht scheuen,

Fragen zu stellen, auch auf dem Matrix Channel und so weiter, das ist genau das, wofür das da

ist und genau wie Fragen, während sie hier sind, ist das etwas, was das Lernen sehr stark unterstützt.

Ja, das war, glaube ich, alles, was ich sagen wollte. Wir haben uns das letzte Mal Dokumente

angeguckt. Dokumente kann man entweder sehen als ganz lange Zeichenkette oder aber, wenn es

formatierte Dokumente sind, eben als eine Mischung aus Kontrollsequenzen und Nutzlasttest.

Kontrollsequenzen sagen, wie der Text aussehen soll, während der Nutzlasttest ist halt einfach

Text und ich hatte versucht, sie davon zu überzeugen, dass Dokumente Bäume sind. Okay,

kommt man vielleicht nicht als erstes drauf, aber wenn man sich so Dokumentenstrukturen

sozusagen von innen anguckt, dann merkt man, dass es fast immer irgendwie ineinander geschachtelte

Regionen sind und ineinander geschachtelte Regionen, wie wir sie überall sehen, lassen sich am besten

durch diese Baummetapher beschreiben, Baummetapher, weil jeder weiß, wo eben Baum funktioniert und

weil wir dadurch ein relativ reiches Vokabular kriegen und das ist auch nicht zu unterschätzen,

wenn wir, was sagen, viele Dinge als Bäume sehen können, dann können wir Algorithmen bauen,

allgemeine Algorithmen, Programme schreiben, die sich auf allen Arten von Bäumen gut austoben können

und die kann man dann häufig verwenden. Bäume sind eine der wichtigsten Datensstrukturen in der

Informatik. Bäume sind dadurch kennzeichnet, dass sie eine Wurzel haben und dann auseinandergehen

in verschiedene Äste, bis sie irgendwann da mal in Blättern enden und zwei Sachen sind für Bäume

wichtig, das muss man sich vor Augen halten. Egal, an welche Gabelung sie kommen, wenn sie da

einfach abschneiden, ist das, was übrig bleibt, ein Baum, immer noch ein Baum und auf der anderen

Seite, das, was sie abgeschnitten haben, ist wieder ein Baum. Die Schnittstelle wird die Wurzel des

Baums auf der einen Seite und die Schnittstelle wird ein Blatt auf der anderen Seite des Baums.

Das ist die eine Sache, die man sich vor Augen führen müssen. Ein Baum ist aus ganz vielen

Unterbäumen aufgebaut und das andere, was sie sich vor Augen führen sollten, ist, dass zu jedem

Teilbaum, also insbesondere auch zu den Blättern, gibt es genau einen Weg. Wenn Sie sich also

vorstellen, Sie laufen von der Wurzel aus los als Ameise und dann wird durch, wenn Sie überall sagen,

hier gehe ich links, da gehe ich rechts, links, links, links, rechts, links, jedes Blatt hat einen

Pfad dahin und nichts zwei. Also ich kann jeden Teilbaum und jedes Blatt kann ich durch den Pfad,

durch den Baum beschreiben. Okay, also wir haben letztlich eine Menge von Teilbäumen, die alle durch

ihre Pfade beschrieben sind und das macht es relativ einfach mit den Biestern umzugehen.

Ja, wir hatten über, gibt tatsächlich baumige, Bäume die umgekehrt wachsen in freier Wildbahn,

fast freier Wildbahn und wir können Bäume sehr einfach mit den Datenstrukturen, die wir haben,

beschreiben. Das waren so die letzten Dinge, die wir gemacht haben. Man kann einfach einen Baum als

eine Liste von Listen machen. Man zum Beispiel dieser Baum hier, das ist der da, das ist eine

Liste, wo das erste Element der Label hier an der Wurzel ist und dann eine Liste von Kindbäumen.

Ja, wir haben hier zum Beispiel einen, den ersten Kindbaum, der fängt mit einer 2 an und der zweite

Kindbaum, der da fängt mit einer 3 an und der hat wiederum eine Liste und so weiter und so fort.

Okay, wenn ich Listen ineinander schachtle, beliebig tief, dann ist das, wenn wir es richtig machen,

eine Baumstruktur und man kann mit diesen Biestern programmieren. Man kann zum Beispiel die Höhe

eines Baums sozusagen wie häufig sind die ineinander geschachtelt. Kann man definieren,

indem man sagt, okay, ich benutze so eine Art Teile- und Herrscheansatz. Wenn man den Baum hier

sieht, dann weiß man, wenn ich weiß, wie hoch dieser Baum ist, dieser Teilbaum und wenn ich weiß,

wie hoch dieser Teilbaum ist, dann weiß ich auch, wie groß die Höhe des Gesamtbaums ist, nämlich

einfach das Maximum der beiden Höhen. Wir nehmen einfach den höheren von den beiden und zählen eins dazu.

Okay, und das ist genau, was dieses Ding hier macht. Die Höhe des Baums ist, man nimmt die maximale