AVL Bäume

Titel:

Note: 2 Klasse: 11

Hier kannst Du Deine Meinung zum Referat schreiben!

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

Wenn Euch das Referat geholfen hat könnt ihr das mit einem Klick +1 auf bestätigen. So wissen andere Schüler schneller ob diese Seite ihnen helfen kann. Um diesen Dienst zu nutzen, müsst ihr bei Google angemeldet sein.

Täglich erreichen uns E-Mails von Euch, in denen Ihr Euch bedankt. Bedenkt bitte, dass die Referate, die Euch hier mal schnell aus der Not helfen, von anderen Schülern hochgeladen wurden.

Darum die Bitte: Wenn Ihr eigene Referate auf dem PC habt ladet diese hier hoch, um auch anderen zu helfen. Nur so kann aus diesem Forum eine große Bereicherung für Euch werden.

So wie Dir geholfen wurde kannst Du auch anderen helfen.

Das tolle daran, Du kannst auch noch etwas gewinnen. Unter allen Einsendern verlosen wir in regelmäßigen Abständen CD's, Taschenrechner und Spielekonsolen, die uns von Sponsoren zur Verfügung gestellt werden.

Hauptanliegen sollte aber die Hilfe untereinander sein. Also seid fair und ladet Eure eigenen Arbeiten HIER hoch. Du findes den Link auch auf der Webseite im Kopf (Referat senden)

Im Namen Aller herzlichen Dank!

Tipp:

MEDIADATEN --- Besucher seit dem 01.09.2006
gesamt: 3876371 - heute: 58 - gestern: 1568 - online: 4 - Rekord online: 125 - Rekord Tag: 8794

ID: 5694 Aufrufe seit dem 02.08.2011: 82