Zur Themenübersicht     

Eigenschaften von AVL-Bäumen

 Hier noch einmal zur Erinnerung einige Definitionen zu binären Bäumen:

• Ein Binärbaum heißt vollständig, wenn jeder Pfad (Folge von Kanten) zu einem beliebigen Blatt die gleiche Länge hat. (Dann gibt es keine Leerstellen im Baum)

• ein binärer Baum heißt vollständig ausgeglichen, wenn für jeden Knoten die Anzahl der Knoten in seinem rechten und linken Teilbaum sich um höchstens 1 unterscheidet.

• ein binärer Baum heißt ausgeglichen (oder AVL-ausgeglichen),  wenn die Tiefe seiner beiden Teilbäume sich um höchstens 1 unterscheidet und beide Teilbäume ausgeglichen sind.

Hier ein vollständiger Baum:

Hier nun zwei vollständig ausgeglichene Bäume, die nicht vollständig sind: 

Hier nun zwei avl-ausgeglichene Bäume, die nicht vollständig ausgeglichen sind: 

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite