AVLBaum.java

package algorithmen;

import java.io.*;

public class AVLBaum {
  
  private AVLKnoten wurzel;
  
  public AVLBaum() {
    // Konstruktor erzeugt leeren Baum
    wurzel = null;
  }
  
  private AVLKnoten rotiereLinks(AVLKnoten b) {
    // vollführt einfaches Rotieren mit b, Fall links - links
    // gibt die geänderte Wurzel zurück
    // Vorbedingung: b ist ein nichtleerer Baum mit den richtigen Teilbäumen
    //    zum entsprechenden Rotieren
    
    AVLKnoten a = b.links;
    b.links = a.rechts;
    a.rechts = b;
    
    b.balance = 0;
    a.balance = 0;
    
    return a;
  }
  
  
  private AVLKnoten rotiereRechts(AVLKnoten b) {
    // vollführt einfaches Rotieren mit b, Fall rechts - rechts
    // gibt die geänderte Wurzel zurück
    // Vorbedingung: b ist ein nichtleerer Baum mit den richtigen Teilbäumen
    //    zum entsprechenden Rotieren
    
    AVLKnoten a = b.rechts;
    b.rechts = a.links;
    a.links = b;
    
    b.balance = 0;
    a.balance = 0;
    
    return a;
  }
  
  private AVLKnoten rotiereDoppeltLinksRechts(AVLKnoten c) {
    // vollführt doppeltes Rotieren mit c, Fall links - rechts
    // gibt die geänderte Wurzel zurück
    // Vorbedingung: c ist ein nichtleerer Baum mit den richtigen Teilbäumen
    //    zum entsprechenden Rotieren
    
    AVLKnoten a = c.links;
    AVLKnoten b = a.rechts;
    a.rechts = b.links;
    b.links = a;
    c.links = b.rechts;
    b.rechts = c;
    
    c.balance = (b.balance == -1)? 1 : 0;
    a.balance = (b.balance ==  1)? -1 : 0;
    b.balance = 0;
    
    return b;
  }
  
  private AVLKnoten rotiereDoppeltRechtsLinks(AVLKnoten c) {
    // vollführt doppeltes Rotieren mit c, Fall rechts - links
    // gibt die geänderte Wurzel zurück
    // Vorbedingung: c ist ein nichtleerer Baum mit den richtigen Teilbäumen
    //    zum entsprechenden Rotieren
    
    AVLKnoten a = c.rechts;
    AVLKnoten b = a.links;
    a.links = b.rechts;
    b.rechts = a;
    c.rechts = b.links;
    b.links = c;
    
    c.balance = (b.balance == 1)? -1 : 0;
    a.balance = (b.balance ==  -1)? 1 : 0;
    b.balance = 0;
    
    return b;
  }
  
  public void einfuegen(AVLKnoten neu) {
    // fügt Knoten neu an die richtige Stelle ein
    
    // 1. Fall: Baum ist noch leer
    if (wurzel == null) {
      wurzel = neu;
    } else {
      // sonst rekursiv durch
      wurzel = einfuegen(wurzel, neu);
    }
  }
  
  boolean rebalance;   // muss der Baum umsortiert werden?
  
  private AVLKnoten einfuegen(AVLKnoten spitze, AVLKnoten neu) {
    // fügt Knoten neu an die richtige Stelle unter Teilbaum spitze ein
    // gibt Zeiger auf neuen Wert für spitze zurück
    
    AVLKnoten temp;
    
    if (neu.daten > spitze.daten) {
      // rechten Teilbaum betrachten
      if (spitze.rechts == null) {
        // neuen Knoten einfach rechts anhängen
        spitze.rechts = neu;
        spitze.balance++;
        rebalance = (spitze.balance >= 1);
        return spitze;
      } else {
        // im rechten Teilbaum einfügen
        spitze.rechts = einfuegen(spitze.rechts, neu);  // ggf. spitze ändern
        if (rebalance) {
          // Ausgleichen
          switch (spitze.balance) {
            case -1:
              // war links-lastig, jetzt ausgewogen
              spitze.balance = 0;
              rebalance = false;
              return spitze;
            case 0:
              // war ausgeglichen, jetzt hier rechtslastig. Weiter oben?
              spitze.balance = 1;
              return spitze;
            case 1:
              // ok, ich bin rechts schief
              rebalance = false;  // wird hier gleich bereinigt
              if (spitze.rechts.balance == 1) {
                // Fall rechts - rechts
                return rotiereRechts(spitze);
              } else {
                // Fall rechts - links
                return rotiereDoppeltRechtsLinks(spitze);
              }
          }
        } else {
          return spitze;   // alles ok, einfach hochreichen
        }
      }
    } else {
      // linken Teilbaum betrachten, genau wie rechts
      if (spitze.links == null) {
        // neuen Knoten einfach links anhängen
        spitze.links = neu;
        spitze.balance--;
        rebalance = (spitze.balance <= -1);
        return spitze;
      } else {
        // im linken Teilbaum einfügen
        spitze.links = einfuegen(spitze.links, neu);  // ggf. spitze ändern
        if (rebalance) {
          // Ausgleichen
          switch (spitze.balance) {
            case 1:
              // war rechts-lastig, jetzt ausgewogen
              spitze.balance = 0;
              rebalance = false;
              return spitze;
            case 0:
              // war ausgeglichen, jetzt hier linkslastig. Weiter oben?
              spitze.balance = -1;
              return spitze;
            case -1:
              // ok, ich bin links schief
              rebalance = false;  // wird hier gleich bereinigt
              if (spitze.links.balance == -1) {
                // Fall links - links
                return rotiereLinks(spitze);
              } else {
                // Fall links - rechts
                return rotiereDoppeltLinksRechts(spitze);
              }
          }
        } else {
          return spitze;   // alles ok, einfach hochreichen
        }
      }
    }
    
    return null;  // der Form halber - sollte hier nie ankommen!
  }
}