Der AVL-Baum wurde 1962 von GM Adelson-Velsky und EM Landis erfunden. Der Baum wird zu Ehren seiner Erfinder AVL genannt.
Der AVL-Baum kann als höhenausgeglichener binärer Suchbaum definiert werden, in dem jedem Knoten ein Ausgleichsfaktor zugeordnet ist, der durch Subtrahieren der Höhe seines rechten Unterbaums von der Höhe seines linken Unterbaums berechnet wird.
Der Baum gilt als ausgeglichen, wenn der Gleichgewichtsfaktor jedes Knotens zwischen -1 und 1 liegt. Andernfalls ist der Baum unausgeglichen und muss ausgeglichen werden.
Ausgleichsfaktor (k) = Höhe (links(k)) – Höhe (rechts(k))
Wenn der Gleichgewichtsfaktor eines Knotens 1 ist, bedeutet dies, dass der linke Teilbaum eine Ebene höher ist als der rechte Teilbaum.
Wenn der Gleichgewichtsfaktor eines Knotens 0 ist, bedeutet dies, dass der linke Teilbaum und der rechte Teilbaum die gleiche Höhe haben.
Numpy-Linspace
Wenn der Gleichgewichtsfaktor eines Knotens -1 ist, bedeutet dies, dass der linke Unterbaum eine Ebene niedriger ist als der rechte Unterbaum.
Ein AVL-Baum ist in der folgenden Abbildung dargestellt. Wir können sehen, dass der jedem Knoten zugeordnete Ausgleichsfaktor zwischen -1 und +1 liegt. Daher handelt es sich um ein Beispiel für einen AVL-Baum.
Komplexität
| Algorithmus | Durchschnittlicher Fall | Schlimmsten Fall |
|---|---|---|
| Raum | An) | An) |
| Suchen | o(log n) | o(log n) |
| Einfügen | o(log n) | o(log n) |
| Löschen | o(log n) | o(log n) |
Operationen am AVL-Baum
Aufgrund der Tatsache, dass der AVL-Baum auch ein binärer Suchbaum ist, werden alle Operationen auf die gleiche Weise ausgeführt wie in einem binären Suchbaum. Das Suchen und Durchlaufen führt nicht zu einer Verletzung des Eigentums des AVL-Baums. Allerdings sind Einfügung und Löschung Vorgänge, die diese Eigenschaft verletzen können und daher erneut überprüft werden müssen.
| SN | Betrieb | Beschreibung |
|---|---|---|
| 1 | Einfügen | Das Einfügen in den AVL-Baum erfolgt auf die gleiche Weise wie in einen binären Suchbaum. Dies kann jedoch zu einer Verletzung der AVL-Baumeigenschaft führen und daher muss der Baum möglicherweise ausgeglichen werden. Der Baum kann durch Rotationen ausgeglichen werden. |
| 2 | Streichung | Das Löschen kann auch auf die gleiche Weise durchgeführt werden wie in einem binären Suchbaum. Das Löschen kann auch das Gleichgewicht des Baums stören. Daher werden verschiedene Arten von Rotationen verwendet, um den Baum wieder ins Gleichgewicht zu bringen. |
Warum AVL Tree?
Der AVL-Baum steuert die Höhe des binären Suchbaums, indem er eine Schiefe verhindert. Die für alle Operationen in einem binären Suchbaum der Höhe h benötigte Zeit beträgt Oh) . Es kann jedoch erweitert werden An) wenn der BST verzerrt wird (d. h. im schlimmsten Fall). Durch die Begrenzung dieser Höhe auf log n legt der AVL-Baum jeder durchzuführenden Operation eine Obergrenze fest O(log n) wobei n die Anzahl der Knoten ist.
AVL-Rotationen
Wir führen eine Rotation im AVL-Baum nur dann durch, wenn der Balance-Faktor anders ist als -1, 0 und 1 . Grundsätzlich gibt es vier Arten von Rotationen:
- L L-Rotation: Eingefügter Knoten befindet sich im linken Teilbaum des linken Teilbaums von A
- R R-Rotation: Eingefügter Knoten befindet sich im rechten Teilbaum des rechten Teilbaums von A
- L R-Rotation: Eingefügter Knoten befindet sich im rechten Teilbaum des linken Teilbaums von A
- R L Rotation: Eingefügter Knoten befindet sich im linken Teilbaum des rechten Teilbaums von A
Wobei Knoten A der Knoten ist, dessen Balance-Faktor nicht -1, 0, 1 ist.
Die ersten beiden Umdrehungen LL und RR sind Einzelumdrehungen und die nächsten beiden Umdrehungen LR und RL sind Doppelumdrehungen. Damit ein Baum unausgeglichen ist, muss die Mindesthöhe mindestens 2 betragen. Lassen Sie uns jede Drehung verstehen
1. RR-Rotation
Wenn BST aus dem Gleichgewicht gerät, weil ein Knoten in den rechten Teilbaum des rechten Teilbaums von A eingefügt wird, führen wir eine RR-Rotation durch. Die RR-Rotation ist eine Drehung gegen den Uhrzeigersinn, die auf die Kante unterhalb eines Knotens mit dem Balancefaktor -2 angewendet wird
Im obigen Beispiel hat Knoten A den Ausgleichsfaktor -2, da ein Knoten C in den rechten Teilbaum des rechten Teilbaums A eingefügt wird. Wir führen die RR-Rotation an der Kante unterhalb von A durch.
2. LL-Rotation
Wenn BST unausgeglichen wird, weil ein Knoten in den linken Teilbaum des linken Teilbaums von C eingefügt wird, führen wir eine LL-Rotation durch. Die LL-Rotation ist eine Drehung im Uhrzeigersinn, die auf die Kante unterhalb eines Knotens mit dem Balancefaktor 2 angewendet wird.
Mergesort-Algorithmus
Im obigen Beispiel hat Knoten C den Ausgleichsfaktor 2, da ein Knoten A in den linken Teilbaum des linken Teilbaums C eingefügt wird. Wir führen die LL-Rotation an der Kante unterhalb von A durch.
3. LR-Rotation
Doppelrotationen sind etwas schwieriger als Einzelrotationen, was oben bereits erläutert wurde. LR-Rotation = RR-Rotation + LL-Rotation, d. h. zuerst wird die RR-Rotation am Teilbaum und dann die LL-Rotation am vollständigen Baum durchgeführt. Mit vollständigem Baum meinen wir den ersten Knoten aus dem Pfad des eingefügten Knotens, dessen Ausgleichsfaktor anders als -1 ist , 0 oder 1.
Lassen Sie uns jeden einzelnen Schritt ganz klar verstehen:
| Zustand | Aktion |
|---|---|
 | Ein Knoten B wurde in den rechten Teilbaum von A und den linken Teilbaum von C eingefügt, wodurch C zu einem unausgeglichenen Knoten mit dem Ausgleichsfaktor 2 geworden ist. In diesem Fall handelt es sich um eine LR-Rotation, wobei: Der eingefügte Knoten befindet sich im rechten Teilbaum des linken Teilbaums von C |
 | Da LR-Rotation = RR + LL-Rotation, wird daher zuerst RR (gegen den Uhrzeigersinn) für den Teilbaum mit Wurzel A durchgeführt. Durch die RR-Rotation, Knoten A , ist zum linken Teilbaum von geworden B . |
 | Nach der RR-Rotation ist Knoten C immer noch unausgeglichen, d. h. er hat den Ausgleichsfaktor 2, da sich der eingefügte Knoten A links von links befindet C |
 | Jetzt führen wir eine LL-Drehung im Uhrzeigersinn am gesamten Baum durch, d. h. am Knoten C. Knoten C ist nun der rechte Teilbaum von Knoten B geworden, A ist linker Teilbaum von B |
 | Der Balancefaktor jedes Knotens beträgt jetzt entweder -1, 0 oder 1, d. h. BST ist jetzt ausgeglichen. |
4. RL-Rotation
Wie bereits erwähnt, sind Doppelrotationen etwas schwieriger als Einzelrotationen, was oben bereits erläutert wurde. R L-Rotation = LL-Rotation + RR-Rotation, d. h. zuerst wird die LL-Rotation am Teilbaum und dann die RR-Rotation am vollständigen Baum durchgeführt. Mit vollständigem Baum meinen wir den ersten Knoten aus dem Pfad des eingefügten Knotens, dessen Ausgleichsfaktor anders als -1 ist , 0 oder 1.
| Zustand | Aktion |
|---|---|
 | Ein Knoten B wurde in den linken Teilbaum von eingefügt C der rechte Teilbaum von A , wodurch A zu einem unausgeglichenen Knoten mit einem Ausgleichsfaktor von - 2 geworden ist. In diesem Fall handelt es sich um eine RL-Rotation, wobei: Der eingefügte Knoten sich im linken Teilbaum des rechten Teilbaums von A befindet |
 | Da RL-Rotation = LL-Rotation + RR-Rotation, also LL (im Uhrzeigersinn) auf dem Teilbaum mit der Wurzel bei C wird zunächst durchgeführt. Durch die RR-Rotation, Knoten C ist zum rechten Teilbaum von geworden B . |
 | Nachdem Sie die LL-Rotation durchgeführt haben, Knoten A ist immer noch unausgeglichen, d. h. mit dem Ausgleichsfaktor -2, was auf den rechten Teilbaum des rechten Teilbaumknotens A zurückzuführen ist. |
 | Jetzt führen wir eine RR-Rotation (Rotation gegen den Uhrzeigersinn) am gesamten Baum durch, d. h. am Knoten A. Knoten C ist nun zum rechten Teilbaum von Knoten B geworden, und Knoten A ist zum linken Teilbaum von B geworden. |
 | Der Ausgleichsfaktor jedes Knotens beträgt jetzt entweder -1, 0 oder 1, d. h. BST ist jetzt ausgeglichen. |
F: Erstellen Sie einen AVL-Baum mit den folgenden Elementen
H, I, J, B, A, E, C, F, D, G, K, L
1. Fügen Sie H, I, J ein
Beim Einfügen der oben genannten Elemente, insbesondere im Fall von H, wird der BST unausgeglichen, da der Balance-Faktor von H -2 beträgt. Da der BST rechtsschief ist, führen wir eine RR-Rotation am Knoten H durch.
Der resultierende Bilanzbaum ist:
2. Fügen Sie B, A ein
Beim Einfügen der oben genannten Elemente, insbesondere im Fall von A, wird der BST unausgeglichen, da der Gleichgewichtsfaktor von H und I 2 beträgt. Wir betrachten den ersten Knoten vom zuletzt eingefügten Knoten, d. h. H. Da der BST von H linksschief ist, Wir werden eine LL-Rotation auf Knoten H durchführen.
Der resultierende Bilanzbaum ist:
3. Fügen Sie E ein
Beim Einfügen von E wird BST unausgeglichen, da der Balance-Faktor von I 2 beträgt, denn wenn wir von E nach I reisen und feststellen, dass es in den linken Teilbaum des rechten Teilbaums von I eingefügt ist, führen wir eine LR-Rotation am Knoten I durch. LR = RR + LL-Rotation
3 a) Wir führen zunächst eine RR-Rotation auf Knoten B durch
Der resultierende Baum nach der RR-Rotation ist:
Python oder
3b) Wir führen zunächst eine LL-Rotation am Knoten I durch
Der resultierende ausgeglichene Baum nach der LL-Rotation ist:
4. Fügen Sie C, F, D ein
Beim Einfügen von C, F, D wird BST unausgeglichen, da der Balance-Faktor von B und H -2 beträgt, denn wenn wir von D nach B reisen, stellen wir fest, dass es in den rechten Teilbaum des linken Teilbaums von B eingefügt wird, und führen dann aus RL-Rotation auf Knoten I. RL = LL + RR-Rotation.
4a) Wir führen zunächst eine LL-Rotation am Knoten E durch
Der resultierende Baum nach der LL-Rotation ist:
4b) Anschließend führen wir eine RR-Rotation auf Knoten B durch
Der resultierende ausgeglichene Baum nach der RR-Rotation ist:
5. G einfügen
Beim Einfügen von G wird BST unausgeglichen, da der Gleichgewichtsfaktor von H 2 beträgt. Wenn wir von G nach H reisen und feststellen, dass es in den linken Teilbaum des rechten Teilbaums von H eingefügt wird, führen wir eine LR-Rotation auf Knoten I durch. LR = RR + LL Drehung.
Liste der Schriftarten in Gimp
5 a) Wir führen zunächst eine RR-Rotation auf Knoten C durch
Der resultierende Baum nach der RR-Rotation ist:
5 b) Anschließend führen wir eine LL-Rotation am Knoten H durch
Der resultierende ausgeglichene Baum nach der LL-Rotation ist:
6. Fügen Sie K ein
Beim Einfügen von K wird BST unausgeglichen, da der Gleichgewichtsfaktor von I -2 beträgt. Da der BST von I nach K rechtsschief ist, führen wir eine RR-Rotation am Knoten I durch.
Der resultierende ausgeglichene Baum nach der RR-Rotation ist:
7. L einfügen
Beim Einfügen ist der L-Baum immer noch ausgeglichen, da der Ausgleichsfaktor jedes Knotens jetzt entweder -1, 0, +1 ist. Daher ist der Baum ein ausgeglichener AVL-Baum
