Was ist ein AVL-Baum?
Die Struktur des AVL-Baumes wurde im Jahre 1962 von den Herren Adelson-Velskii und Landis entwickelt bzw. Erfunden.
Definition des AVL-Baumes:
Ein AVL-Baum ist ein binärer Suchbaum, für all dessen Knoten gilt, daß die Anzahl der linken und rechten Ebene sich um maximal eins differenziert.
Zur Bestimmung dessen wird eine variable verwendet die im Grunde genommen drei Werte annehmen kann:
- 1 (linker Teilbaum eine Ebene tiefer)
0 (balanciert)
+ 1 (rechter Teilbaum eine Ebene tiefer)
Die AVL-Bäume sind die älteste und bekannteste Dateistruktur für balancierte Bäume und eine Sonderart der B-Bäume.
2. Wozu ein AVL-Baum?
Ein AVL-Baum ist ein balancierter Baum. Im Gegensatz zu einem nicht-balancierten Baum (einem Natürlichem) sind die AVL-Bäume für den Einsatz zum Suchen besser geartet. Bei einem natürlichen Baum besteht immer die Gefahr das der Baum zu einer Art Liste verkommt.
Diese Art der Bäume eignet sich besser, wenn ein Anwender in einem Baum eher Knoten Löschen und Einfügen will, da diese keine komplizierten Algorithmen benötigen.
Unbalancierter Baum balancierter Baum
3. Wie ist ein Knoten aufgebaut?
Ein Konten besteht im Allgemeinen aus folgenden Teilen:
Schlüssel
(optional) Datenfeld
Zeiger rechts
Zeiger links
Balancevariable
4. Wie Lösche bzw. Entferne ich?
1. Man suche den Knoten mit dem Schlüssel.
2. Dann löscht man den Knoten
Problem:
Ist der Knoten ein Endknoten oder hat nur einen Nachfolger, gibt es kein Problem.
Ein Problem gib es nur dann, wenn der Knoten mehr als einen Nachfolgeknoten hat. Dann nimmt man entweder den am weitesten links oder rechts gelegenen Knoten
3. Eventuell muß der Baum neu geordnet werden.
5. Wie Ordne ich den Baum neu?
Wenn ein Knoten eingefügt wurde geht man entlang eines Suchpfades und verändert die Balancevariable. Sie wird um 1 verringert wenn links eingefügt wurde, oder um 1 erhöht wenn sie rechts eingefügt wurde.
Sobald eine Balancevariable auf plus oder minus zwei steht muß der Baum neu sortiert werden.
