Ausgeglichene Bäume

• Verfahren zum Ausgleichen von Bäumen:
  • Ziel: Höhe wächst mit O(log(n))
  • zwei Grundverfahren
    • Umbauen der Zweige beim Einsortieren (z.B. AVL-Bäume)
    • zusätzliche Information im Knoten, Knoten mit mehr Zeigern (z.B. B-Bäume)
  • vielfältige Anwendungen, z.B. Indizierung von Datenbanken
• AVL-Bäume:
  • binärer Suchbaum
  • Höhe von linkem und rechtem Zweig jedes Knotens höchstens um 1 verschieden
  • benannt nach G. M. Adelson-Velskii und E. M. Landis
  • einfache Operationen (wie beim normalen Binärbaum)
    • Ausgeben des Baums
    • Suchen nach einem Element
  • komplizierte Operationen
    • Einfügen eines Elements (s.u.)
    • Löschen eines Elements (ähnlich zum Einfügen)
  • Beispiel für AVL-Baum
    
  • kein AVL-Baum
    
• Einfügen eines neuen Elements:
  • zunächst wie beim Sortierbaum einhängen
  • vom neuen Element aus nach oben unbalanzierten Knoten (Differenz > 1) suchen
  • zwei Möglichkeiten
    • zu tiefer Teil ist über links-links oder rechts-rechts zu erreichen ("außen schwer")
      
    • zu tiefer Teil ist über links-rechts oder rechts-links zu erreichen ("innen schwer")
      
  • Ausgleich bei außen schwerem Teilbaum ("einfaches Rotieren" R)
    
  • Ausgleich bei innen schwerem Teilbaum ("doppeltes Rotieren" DR)
    
  • Beispielfolge 4 5 7 2 1 3
    
• Implementierung eines AVL-Baums:
  • AVLKnoten
    • enthält zusätzlich Balance = h(rechts) - h(links)
  • AVLBaum
    • toString, suchen etc. wie beim Sortierbaum
  • Methoden rotiere und rotiereDoppelt
    • jeweils in zwei Versionen (linksrum, rechtsrum)
    • verbiegen nur Zeiger
    • bestimmen neue balance-Werte der veränderten Knoten
    • geben Zeiger auf das neue Wurzel-Element zurück
  • Methode einfuegen
    • sucht rekursiv geeignete Stelle und fügt unten neues Blatt an
    • rekursive Aufrufe setzen rebalance, wenn Ungleichgewicht auftreten könnte
    • rebalance gesetzt → Ausgleichen
    • Ausgleich durch Rotation oder einfach durch Korrektur von balance-Werten
• Aufgaben:
  • Aufgabe 6