Bitte unbedingt beachten:

Übungsblatt 6

Abgabe: 11.1.96 um 12:00 Uhr

Aufgabe 1 [40 Punkte]

1. Gegeben sei ein AVL-Baum mit 10 ⁵ Knoten, die vollständig im Hauptspeicher Platz finden, und mit einer Verarbeitungszeit von 10 ^-6 Sekunden pro aufgesuchtem Knoten.
   • Wie lang dauert die erfolgreiche Suche nach einem Schlüssel im schlechtesten Fall?
   • Berechnen Sie zum Vergleich den schlechtesten sowie mittleren Fall für einen entsprechenden unbalanzierten Suchbaum.

2. Bauen Sie sukzessive aus folgenden Schlüssel einen AVL-Baum auf: 4, 5, 7, 2, 1 ,3, 6

   Außerdem sei folgender AVL-Baum gegeben:
   
   Löschen Sie aus dem Baum sukzessive die folgenden Schlüssel: 4, 8, 6, 5, 2

3. Implementieren Sie AVL-Bäume in C. Verwenden Sie dazu folgende Struktur:

   typedef int item;
   typedef AVL_Node* AVL_tree;
   struct AVL_Node {
         item key;
         AVL_tree left, right;
         int bal;
   };
   

   Implementieren Sie damit die 4 Rotationen für AVL-Bäume:
   • int L_rot(AVL_tree t)
   • int R_rot(AVL_tree t)
   • int LR_rot(AVL_tree t)
   • int RL_rot(AVL_tree t)

4. Programmieren Sie die Operationen Suchen und Einfügen in AVL-Bäumen:
   • AVL_tree AVL_search(AVL_tree t, item x)
   • int AVL_insert(AVL_tree t, item x)

5. Schreiben Sie eine Routine, die die Schlüssel aus einer Datei der Form
   /Schlüssel 1/
   ...
   /Schlüssel n/
   einliest und in einen AVL-Baum einfügt. Schreiben Sie auch eine Routine, die den Baum in PREORDER in eine Datei der Form

   5
    3
     2
      1
     4
    8
     7
      6
   usw.

   ausgibt.

6. Beginnend mit dem leeren AVL-Baum sollen für folgende Fälle 10000 verschiedene Schlüssel eingefügt werden:
   • sortierte Reihenfolge (Zahlen 1 bis 10000) und
   • zufällige Reihenfolge
   Messen Sie die Anzahl der dabei jeweils auftretenden Rotationen (L, R, LR, RL). Schreiben Sie Ihr Programm so, dass man den Dateinamen der Schlüsseldatei auf der Kommandozeile angeben kann. Sie Schlüsseldatei kann beliebig viele Schlüssel enthalten. Die Tutoren werden zum Test zwei Dateien bereitstellen.