AVL-Bäume

Schlagwörter:
Referat, Hausaufgabe, AVL-Bäume
Themengleiche Dokumente anzeigen

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

Autor:
Anzahl Wörter:
317
Art:
Fachbereichsarbeit
Sprache:
Deutsch
Zurück