Ein AVL-Baum definiert als ein Selbstausgleich Der Unterschied zwischen den Höhen des linken Teilbaums und des rechten Teilbaums für jeden Knoten wird als bezeichnet Ausgleichsfaktor des Knotens.

Der AVL-Baum ist nach seinen Erfindern Georgy Adelson-Velsky und Evgenii Landis benannt, die ihn 1962 in ihrer Arbeit An algorithm for the organization of information veröffentlichten.

Beispiel für AVL-Bäume:

AVL-Baum

Der obige Baum ist AVL, da die Unterschiede zwischen den Höhen der linken und rechten Teilbäume für jeden Knoten kleiner oder gleich 1 sind.

Operationen an einem AVL-Baum:

• Einfügen
• Streichung
• Suchen [Es ähnelt der Durchführung einer Suche in BST]

Rotieren der Teilbäume in einem AVL-Baum:

Ein AVL-Baum kann auf eine der folgenden vier Arten rotieren, um sich im Gleichgewicht zu halten:

Linksdrehung :

Wenn ein Knoten zum rechten Teilbaum des rechten Teilbaums hinzugefügt wird und der Baum aus dem Gleichgewicht gerät, führen wir eine einzelne Drehung nach links durch.

Linksrotation im AVL-Baum

Liste in Java

Rechtsdrehung :

Wenn dem linken Teilbaum des linken Teilbaums ein Knoten hinzugefügt wird, gerät der AVL-Baum möglicherweise aus dem Gleichgewicht. Wir führen eine einzelne Rechtsdrehung durch.

Rechtsdrehung im AVL-Baum

10 von 40

Links-Rechts-Rotation :

Eine Links-Rechts-Rotation ist eine Kombination, bei der die erste Linksrotation stattfindet, nachdem diese Rechtsrotation ausgeführt wird.

Links-Rechts-Rotation im AVL-Baum

Rechts-Links-Rotation :

Eine Rechts-Links-Rotation ist eine Kombination, bei der die erste Rechtsrotation nach der Ausführung der Linksrotation erfolgt.

Rechts-Links-Rotation im AVL-Baum

Anwendungen von AVL Tree:

1. Es wird verwendet, um große Datensätze in einer Datenbank zu indizieren und darin effizient zu suchen.
2. Für alle Arten von In-Memory-Sammlungen, einschließlich Sets und Wörterbüchern, werden AVL-Bäume verwendet.
3. Datenbankanwendungen, bei denen Einfügungen und Löschungen weniger häufig vorkommen, aber häufige Datensuchen erforderlich sind
4. Software, die eine optimierte Suche benötigt.
5. Es wird in Unternehmensbereichen und Storyline-Spielen eingesetzt.

Vorteile von AVL Tree:

1. AVL-Bäume können sich selbst ausgleichen.
2. Es ist sicherlich nicht verzerrt.
3. Es bietet schnellere Suchvorgänge als Red-Black Trees
4. Höhere Suchzeitkomplexität im Vergleich zu anderen Bäumen wie Binärbäumen.
5. Die Höhe darf log(N) nicht überschreiten, wobei N die Gesamtzahl der Knoten im Baum ist.

Nachteile von AVL Tree:

1. Es ist schwierig umzusetzen.
2. Für einige Operationen weist es hohe konstante Faktoren auf.
3. Weniger genutzt im Vergleich zu rot-schwarzen Bäumen.
4. Aufgrund ihres recht strengen Gleichgewichts stellen AVL-Bäume komplizierte Einfüge- und Entfernungsvorgänge bereit, wenn mehr Rotationen ausgeführt werden.
5. Benötigt mehr Verarbeitung zum Ausbalancieren.

In Verbindung stehende Artikel:

• Einführung in binäre Suchbäume – Tutorials zu Datenstruktur und Algorithmen
• Einfügen in einen AVL-Baum
• Löschen in einem AVL-Baum