Heute ist wieder mal eine traurige Veranstaltung, das Wochenende steht vor der Tür und wir haben

die letzte Vorlesung im Bereich der Bäume. Wir legen mal los und ich hatte gestern Abend

überlegt wie es denn aussieht mit optimalen Bäumen, Gesundheit, ob die denn schwierig zu

finden seien und mir ist spontan keine Reduktion zu einem NP-vollständigen Problem eingefallen und

eine ihrer Kommilitonen hat dann gesagt, ja ist auch eigentlich relativ klar warum, weil es eine

relativ einfache Lösung gibt und die ist wirklich ziemlich cool. Also vielen Dank für die Idee,

ich glaube das waren Sie da oben. Also was war das Problem? Das Problem war folgendes,

die grundlegende Frage war, wir haben jetzt einen Baum, da ist ein bisschen blöd die Knoten,

aber vielleicht können sie ja noch kleiner werden, gleiches Problem auch für B-Bäume und die

grundlegende Frage war, warum muss ich eigentlich diese komplizierten Operationen machen? Wir hatten

das Problem, dass wir teilweise Knoten verschmelzen mussten oder von den Geschwistern klauen mussten,

warum kann ich die Balance nicht innerhalb der vorderen Knoten suchen? Und dann dachte ich,

das ist eigentlich eine coole Idee, weil warum suchen wir nicht immer nach dem optimalen Baum?

Und dann hatte ich überlegt, ob das denn teuer sei und in der Tat gibt es eine relativ einfache

Lösung und die funktioniert im Wesentlichen wie folgt, also wenn wir uns zum Beispiel den

Benärenbaum angucken, wir wollen quasi eine Operation haben, eine Ausgleichsoperation,

die die Höhe hält, damit der Baum nicht entartet. Was wir im Wesentlichen machen könnten ist,

wir könnten zum Beispiel die Knoten einfach in order durchgehen, wir sortieren die einfach

der Größe nach und nachdem wir das gemacht haben, klar können wir das Element löschen,

vielleicht auch auf dem Weg, während wir das tun und danach fügen wir die Elemente einfach wieder

an den Baum ein. Also offensichtlich können wir das relativ einfach in P durchlaufen,

wahrscheinlich sogar einmal das Durchlaufen des Baumes in N, wenn wir den geschickt durchlaufen,

dann sind die bereits sortiert, das heißt wir müssen alle wieder einsortieren, also haben wir

irgendeine Konstante mal N, das heißt das geht relativ einfach. Also finden eines optimalen

Baums ist offensichtlich nicht so schwierig, warum machen wir das generell nicht? Naja,

weil wir dann jede Operation, also weil wir dann alle Operationen linear in der Anzahl

der Elemente hätten, was wir nicht wollen, sondern wir wollen natürlich logarithmische

Operationen. Also vielen Dank, coole Lösung, das hat mich gestern voll gefreut. Also schauen

wir nochmal wo wir waren, das war quasi das Recap, was ich versprochen hatte. Wir sind bei den AVL

Bäumen und wir haben uns im Grunde genommen mit balancierten Bäumen schon beschäftigt,

insbesondere mit den B-Bäumen und wir haben natürlich die Frage gestellt, warum schauen wir

uns noch andere Baumoperationen an und hier haben wir insbesondere dann gemerkt und diskutiert,

dass die asymptotischen Betrachtungen, die wir machen im Allgemeinen, wie der Name schon sagt,

Operationen sind, die quasi gegen unendlich laufen, also sprich, wenn ich eine riesige Anzahl an

Elementen durcharbeiten würde, was würde passieren? In diesem Fall sind die B-Bäume natürlich auch

optimal, weil sie logarithmisch sind, aber für konkrete Effizienz, das heißt, wenn wir viele

Einfügen und Löschoperationen haben, dann sind die B-Bäume einfach nicht gut und deswegen sind wir

interessiert an den sogenannten AVL Bäumen. Das heißt, hier haben wir Binärbäume, was wir

verhindern wollen, ist immer generell eine Entartung, die so aussieht und wir wollen im

Wesentlichen balancierte Bäume haben, die so aussehen. Dann kam auch generell die Frage auf,

naja, wir haben im Prinzip mehrere Varianten, die wir uns an Baumstrukturen immer anschauen.

Die eine ist, dass die Elemente in den Knoten sind, drei, jetzt mache ich wieder so einen komischen Baum,

wenigstens ein bisschen mehr und in dem Fall hätten wir hier auch ein Blatt und dann hatten wir bei den

B-Bäumen die Notation, wo wir die Blätter im Wesentlichen leer gelassen haben. Also da hatten

wir dann hier unsere Strukturen und die Blätter waren dann im Wesentlichen immer leer. Im Grunde

genommen ist das eine Geschmacksfrage, also sprich, was sie lieber wollen. Sie können auch diese

Bäume zum Beispiel immer durch leere Blätter ergänzen. Dann haben sie auch das optische

Hervorheben eines Blattes. Sie können natürlich auch hier das einfach um eine Ebene erweitern und

Elemente rein speichern, dann müssen sie im Wesentlichen, damit sie wissen, dass sie am Ende

angekommen sind, Ullpointer einfügen. Das heißt, diese unterschiedlichen Darstellungen sind im