Scribd
Hochladen
3 Ansichten2 Seiten

Blatt 07

Das Dokument enthält Aufgaben zu AVL-Bäumen und B-Bäumen im Rahmen einer Übung an der Universität Klagenfurt. Die Aufgaben umfassen das Einfügen von Schlüsseln, das Beweisen von Eigenschaften und das Löschen von Schlüsseln in den jeweiligen Baumstrukturen. Es werden spezifische Schlüsselsequenzen und theoretische Fragen zu den Eigenschaften der Bäume gestellt.

Hochgeladen von

Eva Marktl
Copyright
© All Rights Reserved
Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PDF, TXT herunterladen oder online auf Scribd lesen
3 Ansichten2 Seiten

Blatt 07

Das Dokument enthält Aufgaben zu AVL-Bäumen und B-Bäumen im Rahmen einer Übung an der Universität Klagenfurt. Die Aufgaben umfassen das Einfügen von Schlüsseln, das Beweisen von Eigenschaften und das Löschen von Schlüsseln in den jeweiligen Baumstrukturen. Es werden spezifische Schlüsselsequenzen und theoretische Fragen zu den Eigenschaften der Bäume gestellt.

Hochgeladen von

Eva Marktl
Copyright
© All Rights Reserved
Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PDF, TXT herunterladen oder online auf Scribd lesen

Universität Klagenfurt UE Algorithmen und Datenstrukturen

Artificial Intelligence und Cybersecurity SS 2026


P. Fleiss · M. Morak · J. Wachter · J. Winkler Übungstermine: Siehe Moodle-Kurs
Tutorium: E. Raunig

Übungsblatt 7

Aufgabe 7.1: AVL-Bäume – Aufbau


Fügen Sie die folgenden zwei Schlüsselsequenzen je in einen anfangs leeren AVL-Baum ein.
Geben Sie alle verwendeten Rotationen nachvollziehbar an.
a) 10, 15, 12, 4, 8, 7, 3, 1, 13
b) 5, 6, 3, 4, 10, 9, 8, 1, 2, 7

Aufgabe 7.2: AVL-Bäume – Eigenschaften


Ein fast vollständiger binärer Wurzelbaum ist ein binärer Wurzelbaum, bei dem die ersten h − 1
Ebenen vollständig mit Knoten belegt sind. Nur in der Blattebene dürfen Knoten fehlen.
a) Beweisen oder widerlegen Sie: Jeder fast vollständige sortierte binäre Wurzelbaum ist ein
AVL-Baum.
b) Beweisen oder widerlegen Sie: Jeder AVL-Baum ist ein fast vollständiger binärer Wurzel-
baum.
c) Beweisen oder widerlegen Sie: Für jede natürliche Zahl m gibt es einen AVL-Baum B, sodass
zwei Blätter aus B einen Höhenunterschied von m besitzen.

Aufgabe 7.3: Einfügen in B-Bäumen


Fügen Sie nacheinander die Schlüssel D, I, J, K, N , Q und R in folgenden B-Baum (t = 2) ein:

E L O

A C F G H M P S T

Aufgabe 7.4: Löschen in B-Bäumen


Löschen Sie nacheinander die Schlüssel S, O, L, E, F , B und G aus dem folgenden B-Baum
(t = 2):

E G O

A B C F H M P S T

Aufgabe 7.5: Eigenschaften von B-Bäumen


a) Sei ein B-Baum T mit Minimalgrad t = 2 gegeben.
Wie viele Schlüsselwerte kann T minimal bzw. maximal besitzen, wenn seine Höhe h beträgt?
b) Zeigen Sie: Für einen beliebigen B-Baum mit n Schlüsseln gilt: Höhe h ≤ logt ( n+1
2 ).
c) Zeigen oder widerlegen Sie: Werden zwei Schlüssel in einem B-Baum eingefügt, so resultieren
daraus unabhängig davon, welcher Schlüssel zuerst eingefügt worden ist, identische B-Bäume.

Das könnte Ihnen auch gefallen