AZreferate - Referate und hausaufgaben fur schule.
Referatesuche, Hausarbeiten und Seminararbeiten Kostenlose Online-Dokumente mit Bildern, Formeln und Grafiken. Referate, Facharbeiten, Hausarbeiten und Seminararbeiten findest für Ihre einfache Hausarbeiten.



BetriebstechnikBiographienBiologieChemieDeutschDigitaltechnik
ElectronicaEpochenFertigungstechnikGemeinschaftskundeGeographieGeschichte
InformatikKulturKunstLiteraturManagementMathematik
MedizinNachrichtentechnikPhilosophiePhysikPolitikProjekt
PsychologieRechtSonstigeSportTechnikWirtschaftskunde

Referat AVL-BAUME - Das Balancefeld eines AVL

informatik referate

informatik referate

AVL-BAUME

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:

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

Die Tiefen von links und rechts werden gleich.

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).

Beispiel zum Einfügen von Elementen in AVL-Bäume:


Es werden folgende Elemente eingefügt:

4 5 7 2 1 3 6

Einfügen der Zahl 4:

Einfügen der Zahl 5:

Einfügen der Zahl 7:

Einfügen der Zahl 2:

Einfügen der Zahl 1:

Einfügen der Zahl 3:

Einfügen der Zahl 6:



Referate über:


Datenschutz




Copyright © 2024 - Alle Rechte vorbehalten
AZreferate.com
Verwenden sie diese referate ihre eigene arbeit zu schaffen. Kopieren oder herunterladen nicht einfach diese
# Hauptseite # Kontact / Impressum