Informatik Datenstrukturen – Binärbäume und Traversierung
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was definiert einen Binärbaum? · Was unterscheidet einen binären Suchbaum (BST) von e…
Karten
15 KartenWas definiert einen Binärbaum?
Rückseite
Ein Binärbaum ist eine Baumstruktur, in der jeder Knoten maximal zwei Kindknoten hat – bezeichnet als linker und rechter Sohn.
Was unterscheidet einen binären Suchbaum (BST) von einem allgemeinen Binärbaum?
Rückseite
Im BST gilt: Alle Schlüssel im linken Teilbaum sind kleiner, alle im rechten Teilbaum größer als der Knotenschlüssel – diese Ordnungsproperty ermöglicht effizientes Suchen.
In welcher Reihenfolge besucht die Pre-Order-Traversierung die Knoten?
Rückseite
Wurzel – linker Teilbaum – rechter Teilbaum. Die Wurzel wird vor ihren Nachfahren verarbeitet (Top-Down).
In welcher Reihenfolge besucht die In-Order-Traversierung die Knoten?
Rückseite
Linker Teilbaum – Wurzel – rechter Teilbaum. Bei BSTs liefert dies die Schlüssel in aufsteigend sortierter Reihenfolge.
In welcher Reihenfolge besucht die Post-Order-Traversierung die Knoten?
Rückseite
Linker Teilbaum – rechter Teilbaum – Wurzel. Die Wurzel wird nach ihren Nachfahren verarbeitet (Bottom-Up), nützlich zum Löschen ganzer Bäume.
Wie funktioniert die Level-Order-Traversierung (Breadth-First)?
Rückseite
Knoten werden ebenenweise von oben nach unten, innerhalb jeder Ebene von links nach rechts besucht. Implementierung erfolgt typischerweise mit einer Queue.
Wie sucht man einen Schlüssel in einem BST?
Rückseite
Vergleiche Schlüssel mit Wurzel: bei Gleichheit gefunden, bei kleinerem Wert links weitersuchen, bei größerem Wert rechts weitersuchen – rekursiv oder iterativ.
Welche drei Fälle gibt es beim Löschen eines Knotens im BST?
Rückseite
1) Blattknoten: einfach entfernen. 2) Ein Kind: Kind rückt nach. 3) Zwei Kinder: Nachfolger (Minimum im rechten Teilbaum) oder Vorgänger kopieren und diesen statt dessen löschen.
Wie lautet die Laufzeitkomplexität für Suche, Einfügen und Löschen im BST?
Rückseite
Im Durchschnitt O(log n) bei balanciertem Baum, im Worst Case O(n) bei entartetem Baum (lineare Kette).
Was ist ein AVL-Baum?
Rückseite
Ein selbstbalancierender binärer Suchbaum, bei dem die Höhen der beiden Teilbäume jedes Knotens sich um maximal 1 unterscheiden (Balance-Faktor ∈ {-1,0,1}).
Welche Rotationsarten nutzt der AVL-Baum zur Rebalancierung?
Rückseite
Einfachrotation (rechts/links) bei Außeneinfang und Doppelrotation (links-rechts/rechts-links) bei Inneneinfang – insgesamt vier Fälle.
Was ist der Unterschied zwischen Höhe eines Baums und Tiefe eines Knotens?
Rückseite
Höhe: längster Pfad vom Knoten zu einem Blatt (Blatthöhe = 0). Tiefe: Pfadlänge von der Wurzel zum Knoten (Wurzeltiefe = 0).
Was unterscheidet einen vollständigen von einem vollkommenen Binärbaum?
Rückseite
Vollkommen: alle Ebenen komplett gefüllt (2^h - 1 Knoten). Vollständig: alle Ebenen bis auf die letzte komplett, letzte Ebene von links nach rechts gefüllt ohne Lücken.
Was definiert die Heap-Eigenschaft bei Min-Heaps und Max-Heaps?
Rückseite
Min-Heap: Schlüssel jedes Knotens ≤ Schlüssel seiner Kinder (Minimum an Wurzel). Max-Heap: Schlüssel jedes Knotens ≥ Schlüssel seiner Kinder (Maximum an Wurzel).
Wie wird ein Binärbaum im Array (implizite Darstellung) gespeichert?
Rückseite
Wurzel bei Index 1 (oder 0). Für Knoten i: linker Sohn bei 2i, rechter bei 2i+1, Elternteil bei ⌊i/2⌋. Platzsparend für vollständige Bäume (Heaps).