Informatik Datenstrukturen – Suchbäume und AVL-Bäume
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was ist ein binärer Suchbaum? · Welche Invariante muss ein binärer Suchbaum erfüllen?
Karten
14 KartenWas ist ein binärer Suchbaum?
Rückseite
Ein binärer Suchbaum ist ein binärer Baum, in dem jeder Knoten links kleinere und rechts größere Schlüsselwerte speichert.
Welche Invariante muss ein binärer Suchbaum erfüllen?
Rückseite
Für jeden Knoten gilt: Alle Schlüssel im linken Teilbaum sind kleiner, alle im rechten Teilbaum größer als der Knotenschlüssel.
Wie lautet die Zeitkomplexität für Suche im BST?
Rückseite
Im Durchschnitt O(log n), im Worst-Case O(n) bei entartetem Baum in Form einer verketteten Liste.
Was unterscheidet einen AVL-Baum vom normalen BST?
Rückseite
Ein AVL-Baum ist ein selbstbalancierender binärer Suchbaum mit Höhenbalance: Die Höhen der Teilbäume jedes Knotens unterscheiden sich um höchstens 1.
Wie wird der Balancefaktor eines Knotens berechnet?
Rückseite
Balancefaktor = Höhe(rechter Teilbaum) – Höhe(linker Teilbaum); erlaubt sind nur die Werte -1, 0, +1.
Welche vier Rotationsfälle gibt es bei AVL-Bäumen?
Rückseite
LL (einfache Rechtsrotation), RR (einfache Linksrotation), LR (doppelte Links-Rechts-Rotation), RL (doppelte Rechts-Links-Rotation).
Wann führt man eine einfache Rechtsrotation (LL-Fall) durch?
Rückseite
Bei Einfügen in den linken Teilbaum des linken Kindes: Balancefaktor +2 am Elternknoten, +1 am linken Kind.
Wann führt man eine einfache Linksrotation (RR-Fall) durch?
Rückseite
Bei Einfügen in den rechten Teilbaum des rechten Kindes: Balancefaktor -2 am Elternknoten, -1 am rechten Kind.
Wie funktioniert die doppelte Links-Rechts-Rotation (LR-Fall)?
Rückseite
Zuerst Linksrotation am linken Kind, dann Rechtsrotation am Elternknoten; korrigiert Einfügen in rechten Teilbaum des linken Kindes.
Wie funktioniert die doppelte Rechts-Links-Rotation (RL-Fall)?
Rückseite
Zuerst Rechtsrotation am rechten Kind, dann Linksrotation am Elternknoten; korrigiert Einfügen in linken Teilbaum des rechten Kindes.
Wie hoch ist ein AVL-Baum mit n Knoten maximal?
Rückseite
Maximale Höhe ≈ 1,44 · log₂(n+1); garantiert logarithmische Laufzeit für alle Operationen.
Warum ist der Worst-Case bei BST O(n), bei AVL O(log n)?
Rückseite
BST kann entarten zur Liste; AVL erzwingt durch Rotationen Höhenbalance und verhindert Entartung.
Welche Operationen haben im AVL-Baum O(log n) Garantie?
Rückseite
Suche, Einfügen und Löschen – alle garantiert logarithmisch durch Höhenbalance und Rotationen nach Änderungen.
Was passiert mit Balancefaktoren nach einer Rotation?
Rückseite
Betroffene Knoten erhalten neue Balancefaktoren (meist 0); Pfad zur Wurzel wird geprüft und ggf. weiter rotiert.