Lukases2
Grünschnabel
Dabei seit: 01.07.2015
Beiträge: 1
 |
|
| Rotationen in Binarbäumen |
     |
Während des Einfügens in einen AVL-Baum kann es notwendig sein, eine Links-Rechts-Rotation durchzuführen. Gegebene Situation (nach einer Links-Rechts-Rotation) :
y
/ \
x z
/ \ / \
t1 t2 t3 t4
Aufgabe
Zeigen Sie:
 \text{Der Balancefaktor von } x \text{ ist } -1 \text{ nach der Rotation } \Longleftrightarrow \text{Der Balancefaktor von } x \text{ war } 1 \text{ vor der Rotation } <br />
(2) \text{Der Balancefaktor von } z \text{ ist } 1 \text{ nach der Rotation } \Longleftrightarrow \text{Der Balancefaktor von } y \text{ war } -1 \text{ vor der Rotation }<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?(1) \text{Der Balancefaktor von } x \text{ ist } -1 \text{ nach der Rotation } \Longleftrightarrow \text{Der Balancefaktor von } x \text{ war } 1 \text{ vor der Rotation } <br />
(2) \text{Der Balancefaktor von } z \text{ ist } 1 \text{ nach der Rotation } \Longleftrightarrow \text{Der Balancefaktor von } y \text{ war } -1 \text{ vor der Rotation }<br />
)
Idee
Ich habe leider quasi keine Idee. Mir fehlt hier so ein grundsätzlicher Ansatz. Auf welche Art kann ich das hier zeigen?
|
|
