AVL-Bäume Rotationen Klausurvorbereitung

Was ist ein AVL-Baum?

Ein AVL-Baum ist ein selbstbalancierender binärer Suchbaum, bei dem die Höhenbalance der Knoten maximal 1 beträgt.

Was sind die Hauptmerkmale von AVL-Bäumen?

1. Jeder Knoten hat einen Balancefaktor. 2. Balancefaktor ist -1, 0 oder 1. 3. Selbstbalancierung durch Rotationen.

Was ist der Balancefaktor?

Der Balancefaktor eines Knotens ist die Differenz zwischen der Höhe des linken und des rechten Teilbaums: $\displaystyle Balancefaktor = Höhe(links) - Höhe(rechts)$.

Sind AVL-Bäume immer binäre Suchbäume?

Ja, AVL-Bäume sind eine spezielle Form von binären Suchbäumen mit zusätzlichen Balancierungsbedingungen.

Fülle die Lücke: Der Balancefaktor muss zwischen ___ liegen.

-1 und 1.

Wie wird die Höhe eines AVL-Baums maximiert?

Durch Erhöhen der Anzahl der Knoten, wobei die Struktur balanciert bleibt, um die Höhe minimal zu halten.

Was passiert, wenn der Balancefaktor 2 oder -2 ist?

Der Baum muss rotiert werden, um die Balance wiederherzustellen.

Vergleich: AVL-Baum vs. Rot-Baum.

AVL-Bäume sind strenger balanciert, während Rot-Bäume eine flexiblere Balance haben. AVL-Bäume sind oft effizienter für Suchoperationen.

Wann ist ein AVL-Baum optimal?

Ein AVL-Baum ist optimal, wenn er die minimale Höhe für eine gegebene Anzahl von Knoten hat.

Wie viele Knoten kann ein AVL-Baum mit Höhe h maximal haben?

$\displaystyle N(h) = N(h-1) + N(h-2) + 1$, wobei $\displaystyle N(0) = 1$ und $\displaystyle N(1) = 2$.

Was ist die Höhe eines AVL-Baums mit n Knoten?

Die Höhe eines AVL-Baums ist $\displaystyle O( ext{log } n)$.

Sind AVL-Bäume immer balanciert?

Ja, AVL-Bäume bleiben durch Rotationen in einem balancierten Zustand.

Was bedeutet 'selbstbalancierend'?

Selbstbalancierend bedeutet, dass der Baum automatisch seine Struktur anpasst, um die Balance nach jeder Einfügung oder Löschung aufrechtzuerhalten.

Wie beeinflusst das Einfügen eines Knotens die Balance?

Das Einfügen kann den Balancefaktor beeinflussen, was zu einer Rotation führen kann, um die Balance wiederherzustellen.

Was sind Vor- und Nachteile von AVL-Bäumen?

Vorteile: Schnelle Suchen; Nachteile: Höhere Kosten für Einfügungen und Löschungen aufgrund von Rotationen.

Ist der AVL-Baum der effizienteste Baumtyp?

Nicht unbedingt. Es gibt andere Baumtypen wie B-Bäume, die für bestimmte Anwendungen effizienter sein können.

Was ist eine Linksrotation?

Eine Linksrotation wird durchgeführt, wenn der rechte Teilbaum eines Knotens höher ist. Der Knoten wird nach links gedreht.

Was ist eine Rechtsrotation?

Eine Rechtsrotation wird durchgeführt, wenn der linke Teilbaum eines Knotens höher ist. Der Knoten wird nach rechts gedreht.

Wann wird eine Doppelrotation benötigt?

Eine Doppelrotation wird benötigt, wenn ein Knoten im rechten Teilbaum eines linken Kindes eingefügt wird oder vice versa.

Was passiert bei einer Linksrotation?

Der Knoten wird nach links gedreht. Der rechte Nachfolger wird neuer Wurzelknoten.

Beispiel für Linksrotation?

Gegeben: Knoten A (Wurzel), B (rechter Nachfolger). Nach Linksrotation wird B Wurzel, A wird linker Nachfolger von B.

Beispiel für Rechtsrotation?

Gegeben: Knoten B (Wurzel), A (linker Nachfolger). Nach Rechtsrotation wird A Wurzel, B wird rechter Nachfolger von A.

Was ist eine Links-Rechtsrotation?

Eine Kombination aus einer Linksrotation gefolgt von einer Rechtsrotation. Wird bei bestimmten Insertionsmustern benötigt.

Was ist eine Rechts-Linksrotation?

Eine Kombination aus einer Rechtsrotation gefolgt von einer Linksrotation. Wird bei bestimmten Insertionsmustern benötigt.

Wann ist eine Linksrotation notwendig?

Wenn der rechte Teilbaum eines Knotens höher ist als der linke Teilbaum um mehr als 1.

Wann ist eine Rechtsrotation notwendig?

Wenn der linke Teilbaum eines Knotens höher ist als der rechte Teilbaum um mehr als 1.

Wahr oder falsch: Linksrotation balanciert einen AVL-Baum.

Wahr. Linksrotation balanciert den Baum, wenn der rechte Teilbaum zu hoch ist.

Wahr oder falsch: Rechtsrotation erhöht die Höhe des Baumes.

Falsch. Rechtsrotation verringert die Höhe des linken Teilbaums und balanciert den Baum.

Was ist der Effekt einer Doppelrotation?

Eine Doppelrotation balanciert den Baum, wenn sowohl der linke als auch der rechte Teilbaum des betroffenen Knotens unbalanciert sind.

Vergleich: Linksrotation vs. Rechtsrotation.

Linksrotation: Unbalanciert durch rechten Teilbaum. Rechtsrotation: Unbalanciert durch linken Teilbaum.

Was geschieht nach einer Links-Rechtsrotation?

Erst Linksrotation am linken Kind, dann Rechtsrotation am ursprünglichen Knoten.

Was geschieht nach einer Rechts-Linksrotation?

Erst Rechtsrotation am rechten Kind, dann Linksrotation am ursprünglichen Knoten.

Wofür wird die Drehung verwendet?

Um die AVL-Baum-Eigenschaft zu erhalten: Höhe der Teilbäume unterscheidet sich um maximal 1.

Wie beeinflusst die Rotation die Knotenzahlen?

Die Anzahl der Knoten ändert sich nicht, nur die Struktur des Baumes.

Was bleibt bei einer Rotation gleich?

Die Elemente im Baum bleiben gleich; nur ihre Position ändert sich zur Balance.

Beispiel: Knoten 30, 20, 40 - Rotation?

Wenn 40 eingefügt wird: Rechtsrotation bei 30 nötig, 40 wird neue Wurzel.

Beispiel für Linksrotation?

Führen Sie eine Linksrotation um Knoten A durch, wenn der rechte Teilbaum höher ist. Beispiel: A hat B links und C rechts. Nach der Rotation wird B der neue Wurzelknoten.

Beispiel für Rechtsrotation?

Bei einer Rechtsrotation um Knoten B, wenn der linke Teilbaum höher ist. Beispiel: B hat A links und C rechts. Nach der Rotation wird A der neue Wurzelknoten.

Wann wird eine Doppelte Rotation benötigt?

Eine doppelte Rotation (Links-Rechts oder Rechts-Links) wird benötigt, wenn ein Knoten im unbalancierten Teilbaum des übergeordneten Knotens eingefügt wird. Beispiel: Fügen Sie Knoten D im linken Teilbaum von C ein.

Links-Rechts-Rotation: Schritt 1?

Führen Sie zuerst eine Rechtsrotation um den linken Knoten durch, bevor Sie eine Linksrotation um den übergeordneten Knoten durchführen.

Wahr oder Falsch: Rotationen sind immer notwendig?

Falsch. Rotationen sind nur notwendig, wenn der AVL-Baum nach einer Einfügung oder Löschung unbalanciert wird.

Wie wird die Höhe eines AVL-Baums berechnet?

Die Höhe wird rekursiv berechnet: Höhe = 1 + max(Höhe linkes Kind, Höhe rechtes Kind).

Welche Knoten sind bei einer Linksrotation betroffen?

Der Knoten, um den die Rotation durchgeführt wird, und sein rechter Kindknoten sowie dessen linkes Kind.

Rechts-Links-Rotation: Schritt 2?

Führen Sie eine Linksrotation um den rechten Knoten durch, gefolgt von einer Rechtsrotation um den übergeordneten Knoten.

Fülle die Lücke: Nach einer Linksrotation wird der ____ Knoten der neue Wurzelknoten.

rechte Knoten

Wie viele Rotationen sind maximal pro Einfügen notwendig?

Maximal zwei Rotationen können erforderlich sein, um den Baum wieder ins Gleichgewicht zu bringen.

Beispiel für einen AVL-Baum vor und nach Rotation?

Vor: 10 (Wurzel), 20 (rechts), 30 (rechts von 20). Nach Rechtsrotation um 10: 20 (neu), 10 (links), 30 (rechts).

Was passiert bei übermäßiger Balance?

Übermäßige Balance führt zu ineffizienter Nutzung der Rotationen und kann die Einfüge- und Löschzeiten erhöhen.

Häufigster Fehler bei AVL-Bäumen?

Vergessen, die Höhen der Knoten nach Operationen anzupassen.

Wahr oder Falsch: AVL-Bäume sind immer perfekt balanciert.

Falsch. AVL-Bäume sind nur balanciert, aber nicht perfekt. Sie erlauben Höhenunterschiede von höchstens 1.

Ursache von Rotationen?

Ein Knoten hat nach einer Einfügung oder Löschung einen Höhenunterschied von mehr als 1.

Fülle die Lücke: Die Höhe eines AVL-Baums ist maximal __________.

logarithmisch zur Anzahl der Knoten.

Linkes und rechtes Kind: Unterschiede?

Linkes Kind hat höhere Höhe → linke Rotation. Rechtes Kind hat höhere Höhe → rechte Rotation.

Wie optimiert man entferntes Knoten?

Durchsuchen des Baums nach dem Nachfolger oder Vorgänger und Anpassen der Höhen und Rotationen.

Frühzeitige Rotationen?

Verhindern einer Vielzahl von Korrekturen und reduzieren die Zeitkomplexität auf $\displaystyle O( ext{log } n)$.

Häufige Fehler bei Löschoperationen?

Nicht alle notwendigen Rotationen durchführen, falsche Knotenhöhe anpassen.