AVL-Baum

1. 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, dass 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 muss 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 muss der Baum neu sortiert werden.

Bei der Veränderung der Balancevariable können drei Fälle entstehen:

Urspungswert	Neuer Wert	Aktion
- 1	0	Der Baum ist wieder ausbalanciert (Suchpfadverfolgung kann abgebrochen werden)
0	+ 1 / - 1	Der Baum hat links oder rechts eine Ebene mehr ist aber immer noch ausbalanciert.
+ 1 / - 1	+ 2 / - 2	der Baum muss neu sortiert werden

Zum neu sortieren gibt es vier Möglichkeiten:

1. LL-Rotation

2. LR-Rotation

3. RR-Rotation

4. RL-Rotation

6. Beispiel für LL-Rotation:

Benutzte Zahlen: 1,2,3,4,5,6

1.

Balancevariable

2.

Schlüssel

402 Worte in "deutsch"  als "hilfreich"  bewertet