Binärer Suchbaum
Lerne die Grundlagen und Eigenschaften eines binären Suchbaums für das Abitur in Informatik. Diese Karteikarten helfen dir, die wichtigsten Konzepte und Algorithmen zu verstehen.
Quiz(48 Fragen)
1. Was ist die Zeitkomplexität für das Suchen eines Wertes im Durchschnitt?
Begriffe in diesem Lernset(48)
Grundlagen des binären Suchbaums(16)
Was ist ein binärer Suchbaum?
Ein binärer Suchbaum ist eine Datenstruktur, die aus Knoten besteht. Jeder Knoten hat höchstens zwei Nachfolger: links ein kleinerer und rechts ein größerer Wert.
Eigenschaft: Knoten im linken Teilbaum
Alle Knoten im linken Teilbaum sind kleiner als der übergeordnete Knoten.
Eigenschaft: Knoten im rechten Teilbaum
Alle Knoten im rechten Teilbaum sind größer als der übergeordnete Knoten.
Tiefen- und Breitensuche
Tiefensuche geht in die Tiefe (links, dann rechts), Breitensuche untersucht Ebene für Ebene.
Wie viele Knoten hat ein vollständiger Baum mit Höhe 3?
Ein vollständiger binärer Baum mit Höhe 3 hat 15 Knoten: .
Wahr oder Falsch: Suche ist immer O(log n).
Falsch. Die Suche ist O(log n) im besten Fall, aber O(n) im schlechtesten Fall (z.B. bei einem unbalancierten Baum).
Was ist die Höhe eines binären Suchbaums?
Die Höhe ist die maximale Anzahl der Kanten von der Wurzel zu einem Blatt. Ein leerer Baum hat Höhe -1.
Definition: Blätter
Blätter sind Knoten ohne Nachfolger. Sie haben keine Kinder und sind am Ende eines Pfades.
Wann ist ein Baum balanciert?
Ein Baum ist balanciert, wenn die Höhen der Teilbäume für jeden Knoten sich um höchstens 1 unterscheiden.
Wie viele Blätter hat ein vollständiger Baum mit Höhe 3?
Ein vollständiger Baum mit Höhe 3 hat 8 Blätter, da für Höhe gilt.
Was passiert bei einer Einfügung?
Ein neuer Knoten wird entsprechend der Werte eingefügt, um die Sortierbedingungen des Baumes zu wahren.
Definition: Wurzel
Die Wurzel ist der oberste Knoten eines binären Suchbaums. Sie hat keinen Vorgänger.
Unterschied: Binärer Baum vs. Binärer Suchbaum
Ein binärer Baum hat keine speziellen Anforderungen an die Anordnung der Knoten; ein binärer Suchbaum hat spezifische Ordnungsregeln.
Vor- und Nachteil eines binären Suchbaums?
- Vorteil: Schnelle Suche.<br>- Nachteil: Unbalancierte Bäume können die Suche verlangsamen.
Was ist ein Knoten?
Ein Knoten ist eine grundlegende Einheit eines Baumes, die Daten und Verweise auf Nachfolger speichert.
Beispiel: Einfügen in einen binären Suchbaum
Um 7 in einen Baum mit Wurzel 10 einzufügen: Links von 10, da 7 < 10.
Operationen im binären Suchbaum(16)
Was ist die Zeitkomplexität für Einfügen?
Im Durchschnitt: O(log n), im schlechtesten Fall: O(n).
Operation: Suchen
Beginne beim Wurzelknoten. Gehe links oder rechts, je nach Vergleich.
Einfügen eines Wertes: Beispiel
Füge 15 in den Baum ein: 1. Start bei Wurzel. 2. Vergleiche: kleiner? Gehe links, sonst rechts.
Wahr oder falsch: Einfügen ist immer O(1).
Falsch. Es hängt von der Baumstruktur ab.
Was passiert bei Einfügen eines existierenden Wertes?
Der Wert wird nicht eingefügt. Es bleibt im Baum bestehen.
Wie löscht man einen Knoten?
Drei Fälle: 1. Kein Kind: Einfach entfernen. 2. Ein Kind: Kind ersetzen. 3. Zwei Kinder: Inorder-Nachfolger finden.
Was ist der Inorder-Nachfolger?
Der kleinste Knoten im rechten Teilbaum des zu löschenden Knotens.
Fülle die Lücke: Suchen benötigt im besten Fall ____ Vergleiche.
1 Vergleich.
Was ist die Zeitkomplexität für Löschen?
Im Durchschnitt: O(log n), im schlechtesten Fall: O(n).
Vergleich: Einfügen vs. Löschen
Einfügen: Einfache Umstellungen. Löschen: Komplexer, insbesondere bei zwei Kindern.
Wahr oder falsch: Einfügen kann den Baum unausgeglichen machen.
Wahr. Unbalancierte Einfügungen führen zu längeren Pfaden.
Was macht man, wenn der gesuchte Wert nicht gefunden wird?
Der Suchvorgang endet ohne Treffer, Rückgabe von null oder Fehlermeldung.
Einfügen: Zeitkomplexität bei balancierten Bäumen?
O(log n) für alle Operationen.
Was sind die Voraussetzungen für einen binären Suchbaum?
Jeder Knoten hat maximal zwei Kinder: links kleiner, rechts größer.
Was passiert bei einem Baum mit nur einem Knoten?
Einfügen oder Suchen ist trivial; der Knoten ist die Wurzel.
Was ist die Hauptanforderung beim Suchen?
Vergleiche den gesuchten Wert mit dem aktuellen Knoten und entscheide den nächsten Schritt.
Traversal-Methoden(16)
Inorder Traversierung
Besucht die Knoten in aufsteigender Reihenfolge. 1. Linker Teilbaum 2. Knoten 3. Rechter Teilbaum
Preorder Traversierung
Knoten werden in der Reihenfolge besucht: 1. Knoten 2. Linker Teilbaum 3. Rechter Teilbaum
Postorder Traversierung
Die Reihenfolge der Besuche ist: 1. Linker Teilbaum 2. Rechter Teilbaum 3. Knoten
Was ist Level-Order Traversierung?
Die Knoten werden schichtweise besucht, beginnend bei der Wurzel und von links nach rechts.
Unterschied zwischen Preorder und Inorder?
Preorder besucht zuerst den Knoten, Inorder besucht ihn zwischen den Teilbäumen.
Was passiert bei einer leeren Traversierung?
Es gibt keine Knoten zu besuchen. Die Rückgabe ist null oder leer.
Beispiel für Inorder Traversierung
Für den Baum: 2 (Wurzel), 1 links, 3 rechts Inorder: 1, 2, 3.
Wie wird Postorder genutzt?
Ideal für das Löschen von Knoten, da zuerst die Kinder besucht werden.
Level-Order Traversierung: Wahr oder Falsch?
Wahr. Knoten werden schichtweise besucht.
Welche Traversierung verwendet Rekursion?
Preorder, Inorder und Postorder Traversierungen nutzen Rekursion.
Fülle die Lücke: Inorder Traversierung liefert eine ________ Reihenfolge.
aufsteigende
Was ist eine nicht-rekursive Traversierung?
Eine Traversierung, die mit einer Warteschlange implementiert wird, wie Level-Order.
Preorder Traversierung: Nutzung?
Kann genutzt werden, um einen Baum zu kopieren oder zu serialisieren.
Postorder Traversierung: Beispiel
Für den Baum: 1 links, 3 Wurzel, 2 rechts Postorder: 1, 2, 3.
Worin besteht der Hauptunterschied?
Die Reihenfolge des Knotenzugriffs variiert je nach Traversierungsart.
Wie viele Traversierungsmethoden gibt es?
Es gibt vier Hauptmethoden: Inorder, Preorder, Postorder und Level-Order.
Fragen in diesem Lernset(48)
1. Was ist die Zeitkomplexität für das Suchen eines Wertes im Durchschnitt?
2. Was ist ein binärer Suchbaum?
3. Welche Traversierung besucht die Knoten in aufsteigender Reihenfolge?
4. Wenn man den Wert 20 in einen Baum einfügt, der Wurzel 15 hat, wohin geht man zuerst?
5. Welche Eigenschaft haben Knoten im linken Teilbaum?
6. Was geschieht bei der Preorder Traversierung?
7. Wahr oder falsch: Das Einfügen eines Wertes kann den Baum immer unausgeglichen machen.
8. Was passiert bei einer Einfügung in einen binären Suchbaum?
9. Wie lautet die Reihenfolge bei der Postorder Traversierung?
10. Was passiert, wenn ein Wert, der bereits im Baum existiert, nochmals eingefügt wird?
11. Wie viele Knoten hat ein vollständiger Baum mit Höhe 3?
12. Was beschreibt die Level-Order Traversierung?
13. Wie lautet die Zeitkomplexität für das Löschen eines Wertes im schlechtesten Fall?
14. Was ist die Höhe eines binären Suchbaums?
15. Welcher Unterschied besteht zwischen Preorder und Inorder Traversierung?
16. Was ist der Inorder-Nachfolger eines Knotens?
17. Wann ist ein binärer Suchbaum balanciert?
18. Was passiert bei einer leeren Traversierung?
19. Bei einer Suche beginnt man mit dem:
20. Was sind Blätter in einem binären Suchbaum?
21. Was ist ein Beispiel für eine Inorder Traversierung bei einem Baum mit Knoten 2 (Wurzel), 1 links, 3 rechts?
22. Was ist die Hauptanforderung bei der Operation Suchen?
23. Was ist der Unterschied zwischen einem binären Baum und einem binären Suchbaum?
24. Wie wird Postorder Traversierung normalerweise genutzt?
25. Welcher der folgenden Werte kann nicht in einen binären Suchbaum eingefügt werden?
26. Was ist das Ergebnis einer Tiefensuche in einem binären Suchbaum?
27. Ist die Aussage 'Level-Order Traversierung besucht die Knoten schichtweise' wahr oder falsch?
28. Welche Operation ist im Allgemeinen komplexer: Einfügen oder Löschen?
29. Wie viele Blätter hat ein vollständiger Baum mit Höhe 3?
30. Welche Traversierung verwendet Rekursion?
31. Was geschieht bei einem Baum mit nur einem Knoten?
32. Welche Aussage zu binären Suchbäumen ist falsch?
33. Fülle die Lücke: Inorder Traversierung liefert eine ________ Reihenfolge.
34. Wie viele Vergleiche benötigt das Suchen im besten Fall?
35. Wie wird ein Knoten in einen binären Suchbaum eingefügt?
36. Was ist eine nicht-rekursive Traversierung?
37. Wahr oder falsch: Bei einem balancierten Baum ist die Zeitkomplexität für alle Operationen O(log n).
38. Was ist die Wurzel eines binären Suchbaums?
39. Welche Traversierungsmethode kann verwendet werden, um einen Baum zu kopieren oder zu serialisieren?
40. Worin unterscheidet sich das Einfügen von Werten in einen Baum von der Suche?
41. Welcher Algorithmus kann zur Breitensuche verwendet werden?
42. Was ist ein Beispiel für eine Postorder Traversierung bei einem Baum mit Knoten 1 links, 3 Wurzel, 2 rechts?
43. Was geschieht, wenn der gesuchte Wert nicht im Baum gefunden wird?
44. Welche Aussage über Knoten in einem binären Suchbaum ist richtig?
45. Worin besteht der Hauptunterschied zwischen den Traversierungsarten?
46. Was ist die Zeitkomplexität für das Löschen eines Wertes im Durchschnittsfall in einem balancierten binären Suchbaum?
47. Was beschreibt die Zeitkomplexität O(log n) im Kontext der Suche in einem binären Suchbaum?
48. Wie viele Traversierungsmethoden gibt es im Allgemeinen?
Ähnliche Lernsets
Informatyka studia – Algorytmy i struktury danych
Sortieren einfach erklärt Karteikarten
Endliche Automaten Abiturvorbereitung
Dynamische Programmierung Prüfungsfragen
Halteproblem Entscheidbarkeit Klausurvorbereitung
Abitur: Komplexität grob
Greedy-Algorithmen Wechselgeldproblem Definitionen
Mergesort und Quicksort Laufzeit Definitionen
Eigenes Lernset erstellen
Lade ein PDF hoch, füge Notizen ein oder beschreibe ein Thema – KI erstellt Karteikarten, Quizze und mehr in Sekunden.
