Vorlesung Informatik 2 - Teil B: Theorie

4.9 AVL Bäume - Vertiefung

Wir beginnen mit einem etwas komplexeren Beispiel: Dir Buchstaben BERLIN:

Bis zu BERL mussten wir nur eine einfache Rotation durchführen:

        E
      /   \
     B    E
         /
       L

und auch die Rotation nach dem Einfügen von I ist keine Herausforderung:

        E
      /   \
     B    L
         /   \
       I      N

Aber nach dem Einfügen von N ist eine einfache Rotation am Knoten E notwendig, wobei der Knoten I  plötzlich übrig ist, d.h.  wir müssen den Knoten I jetzt in den Teilbaum E als rechten Knoten einfügen.

         L
      /     \
    E        R
   /  \      /   
  B    I   N      

Der Knoten I war vorher der kleinste Knoten im rechten Teilbaum der Wurzel und wurde durch die Rotation zum größte Knoten im linken Teilbaum der neuen Wurzel.

Zur Implementierung von AVL Bäumen:

Vorausgesetzt, wir haben bereits eine Klasse Suchbaum mit einer inneren KLasse SuchBaumKnoten:

public class SuchBaum<K extends Comparable, V> implements MeineMap<K,V>{	
protected class SuchBaumKnoten extends Baum<V>{
protected K key;
                                ...

Dann leiten wir AVL Baum von SuchBaum wie folgt ab:

public class AVLBaum<K extends Comparable, T> extends SuchBaum<K,T>{
protected class AVLKnoten extends SuchBaumKnoten{
protected int hoehe = 1;  // Hoehe des Baumes: maximale Tiefe seiner Knoten
                public void updateHoehe(){
                                       ...

Ein Objekt der inneren Klasse AVLKnoten hat also wie SuchBaumKnoten einen Inhalt vom Typ T, einen Schlüssel vom Typ K und zusätzlich seine Höhe. 

Die Klasse AVLBaum bekommt nur eine Eigenschaft: die Wurzel:

    private AVLKnoten wurzel;

Die put Methode macht jetzt folgendes:

    public void put(K key, T value){
            wurzel = put(key, value, wurzel);
    }

Wobei die überladene Methode rekursiv den Eintrag in den Baum einfügt. Da aber durch Rotationen die Wurzel eventuell ausgetauscht wird, muss die rekursive Methode den aktuellen Knoten sowohl als Parameter erhalten als auch zurückgeben.

Die rekursive Methode sieht schließlich so aus:

   private AVLKnoten put(K key, T value, AVLKnoten k){
	if(k==null) return new AVLKnoten(key, value);		
	if(key.compareTo(k.key)==0) k.inhalt=value;
	else if(key.compareTo(k.key)<0) k.setLinks(this.put(key, value, k.links()));    // Rekursion
	else                            k.setRechts(this.put(key, value, k.rechts()));  // rekursion	
	return balanciere(k);	
   }   

Die Hauptarbeit der Rotationen mach die Methode balanciere, sie:

  • vergleicht die Höhe des linken und rechten Teilbaums von K
  • Prüft ob und welche Rotation notwendig ist und führt sie durch,
  • berechnet die Höhe des Knotens k neu.

Für die Rotationen schreiben wir dann vier Methoden: rotiereEinfachRechts bzw Links sowie rotiereDoppeltRechts(AVLKnoten k)

Das Schema einer einfachen Rechtsrotation:

      k2             k1
     /  \           /  \
    k1   Z   -->   X    k2
   /  \                /  \
  X    Y              Y    Z

Die wesentlichen Element in Java:

   AVLKnoten rotiereEinfachRechts(AVLKnoten k2)
            AVLKnoten k1 = k2.links();   
  k2.setLinks(k1.rechts());         
k1.setRechts(k2); 

Danach muss noch die Höhe von k1 und k2 neu berechnet werden.

Lehrvideo (Youtube)