AVL Bäume - schulnote.de 
Akzeptieren

Unsere Webseite nutzt Cookies. Wenn Sie auf dieser Webseite bleiben, nehmen wir an, dass Sie damit einverstanden sind. Sie können unsere Cookies löschen. Wie das geht, erfahren Sie in unserer Datenschutzerklärung. Mehr erfahren



Impressum | Datenschutzerklärung Startseite








Titel:

AVL Bäume


  Note: 2   Klasse: 11









Arbeit: AVL-BÄUME

Ein binärer Baum heißt ausgeglichener Baum oder AVL-Baum (benannt nach seinen "Erfindern" Adelson-Velskij und Landis), falls sich die Höhen der beiden Teilbäume um höchstens 1 unterscheiden.



Jeder Knoten eines Baumes setzt sich aus vier Informationen zusammen:

Pointer auf den linken Sohn

Pointer auf den rechten Sohn

Balancefeld

Datenfeld


Das Balancefeld eines AVL-Knotens kann die Tiefendifferenz mit zwei Bits anzeigen:


+1 der rechte Sohn ist tiefer (unbalancierter Knoten)

0 gleiche Tiefe (balancierter Knoten)

-1 der linke Sohn ist tiefer (unbalancierter Knoten)


Wird ein neuer Knoten eingefügt, sind drei Fälle zu unterscheiden:

1. Die Tiefen von links und rechts werden verschieden, aber das Kriterium der Ausgeglichenheit wird nicht verletzt.

2. Die Tiefen von links und rechts werden gleich.

3. Die Ausgeglichenheit wird zerstört, und der Baum muß umstrukturiert werden


Der Prozeß des Einfügens und des Löschens ist grundsätzlich gleich dem Einfügen und Löschen bei "normalen" binären Bäumen. Es muß jedoch nach jedem Einfügen bzw. Löschen eines Knotens darauf geachtet werden ob die Balance in dem erlaubten Rahmen ist (-1,0,+1).


Um den AVL-Baum gegebenenfalls wieder in Balance bringen zu können, muß eine "Rotation" durchgeführt werden (Links-/Rechtsrotation).








Quelle:




ähnliche Referate 



Hier könnt Ihr die DRUCKANSICHT für das Referat öffnen




Tipp:







(c) schulnote.de 2004-2018

MEDIADATEN --- Besucher seit dem 01.09.2006
gesamt: 6674696 - heute: 95 - gestern: 984 - online: 4 - Rekord online: 340 - Rekord Tag: 2801


ID: 5694      Aufrufe seit dem 02.08.2011: 2150