PPT-Folie
Balancierte Bäume
Balancierte Binärbäume
AVL - Bäume
Suchoperationen wie für allgemeine binäre Suchbäume
Implementierung des AVL-Baumes:
Einfügen in AVL - Bäumen
Dann bedeutet:
Rotationsbeispiele:
Beispiel 2:
Löschen in AVL - Bäumen
Bis auf Symmetrie treten nur 3 Fälle auf:
Der Rebalancierungsalgorithmus beim Löschen hat folgende wesentlichen Schritte: 1.) Suche im Löschpfad nächsten Vater mit BF = ? 2. 2.) Führe Rotation im gegenüberliegenden Unterbaum dieses Vaters aus.
Gewichtsbalancierte Suchbäume (oder BB-Bäume - bounded balance)
Parameter ? als Freiheitsgrad im Baum
Positionssuche mit balancierten Bäumen
E-Mail: der@informatik.uni-leipzig.de
Homepage: http://www.informatik.uni-leipzig.de/~der