AVL-Baum bei Unbalance < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:42 So 09.10.2005 | | Autor: | Draugr |
Hallo, kurze Frage:
Ich füge in einem AVL-Baum ein zusätzliches Element ein, der dadurch unbalanciert wird. Angenommen es treten mehrfach Balancewerte von [mm] \pm2 [/mm] auf, wie gehe ich vor? Nehme ich immer den Knoten mit [mm] \pm2 [/mm] auf der höchsten Stufe und schaue dann nach der Rotation ob immer noch unbalancierte Knoten vorliegen?
Bzw ich glaube beim Einfügen kann gar keine Doppelrotation entstehen, wohl aber beim Löschen. Die Frage ist aber trotzdem: arbeite ich mich dann "von unten nach oben" vor?
Danke im Voraus!
Gruß
Chris
|
|
| |
|
Hallo Chris,
> Ich füge in einem AVL-Baum ein zusätzliches Element ein,
> der dadurch unbalanciert wird. Angenommen es treten
> mehrfach Balancewerte von [mm]\pm2[/mm] auf
Meiner Ansicht nach ist das unmöglich. Ich denke, es kann nur einmal ein solches Ungleichgewicht entstehen, und dann wird das Gleichgewicht nach dem Einfügen wiederhergestellt, wodurch ein mehrfaches [mm] $\pm [/mm] 2$ von Anfang an ausgeschlossen ist.
> Bzw ich glaube beim Einfügen kann gar keine Doppelrotation
> entstehen, wohl aber beim Löschen.
Doch auch beim Einfügen kann es zu einer Doppelrotationen kommen. Ein wirklich gutes Applet dazu findest Du ![[]](/images/popup.gif) hier. Füge mal 3,1,2 in dieser Reihenfolge ein, und siehe selbst. 
Soweit ich weiß, ist übrigens die Fibonacci-Reihe ein Worst-Case-Fall für einen AVL-Baum, da hier fast ständig Rotationen ausgeführt werden müssen. Versuch' das mal mit dem Applet. Aber selbst damit treten keine mehrfachen 2er-Ungleichgewichte auf, die man dann ausgleichen müßte. Und wenn man sich den Code einer Einfüge-Operation für einen AVL-Baum anschaut, so stehen dort zunächst die rekursiven Einfüge-Anweisungen. Danach aber kommen sofort gewisse if-Abfragen, die einen sofortigen Ausgleich eines möglichen Ungleichgewichts (bis [mm] $\pm [/mm] 2$) zur Folge haben.
> arbeite ich mich dann "von unten nach oben" vor?
Ja, genau.
Viele Grüße
Karl
|
|
|
|
