Allgemeine Fragen Flashcards
Welche Eigenschaften sind für Binäre Suchbäume charakteristisch?
Für jeden Knoten sind die Schlüssel des linken Unterbaums kleiner und im rechten größer
Was ist der Grad in einem Baum?
Die maximale Anzahl von Unterbäume.
Was ist die Ebene in einem Baum?
Der Abstand zwischen einem Knoten bis zur Wurzel( => Wurzelknoten ist Ebene 0)
Was ist die Höhe eines Baumes?
Höchste Ebene eines Baumes (=> Baum mit nur Wurzel ist 0 hoch)
Wie wird die Baumwurzel in einem binären Baum realisiert?
Über eine Variable TreeNode <t> root.</t>
Wie wird auf den binären Suchbaum von “außen” zugegriffen (die bekannten Methoden sind private)?
Bspw.
public boolean contains(E key){
return lookup(root, key) != null;
}Was ist die Schwachstelle von Binären Suchbäumen?
- Struktur ist abhängig von der Einfügereihenfolge
- Maximum/ Minimum ineffizient
Was ist das Ziel gewesen, von normalen binären Suchbäumen “wegzukommen”?
Versuch, eine GARANTIERTE Laufzeit von O(log(N)) zu realisieren und nicht O(N)
Was sind die Vorteile von Binären Suchbäumen?
- Lookup nahezu so effizient wie auf Arrays
- Einfügen/ Löschen effizienter als Arrys (kein Verschieben notwendig)
Was ist ein 2-3-Baum?
Ein Baum, dessen Knoten entweder
- 1 Schlüssel und 2 Unterbäume hat
- 2 Schlüssel und 3 Unterbäume hat
Zu welcher Kategorie gehören 2-3-Bäume?
Balancierte Suchbäume
Was ist der Vorteil an Balancierten Suchbäumen?
Lookup, Minimum, Maximum, Einfügen, Löschen in garantiert in O(log(N)) realisieren
Wie sind Balancierte Suchbäume charakterisiert?
- Alle Blätter in “ähnlichem” Abstand zur Wurzel
- “Entartungen” werden vermieden
- Worst Case Szenario nahe an mittlerer Laufzeit
Was ist die Worst-Case-Performance bei Suchen und Einfügen bei 2-3-Bäumen?
Unterscheidet sich diese vom Garantierten Fall?
Nein, die Performance ist auch dabei O(log(N))
Begründe, wieso das Worst Case Szenario in 2-3-Bäumen ebenfalls O(log(N)) ist.
Worst Case Knotenversuche ergibt sich aus Baumhöhe. Diese ist bei 2-3-Bäumen dann log2(N), weil der Baum im Worst Case ausschließlich aus Binären Knoten besteht (Best Case: Alles Tertiäre Knoten)
Pro Knoten sind damit im Worst Case 2 Schlüsselvergleiche (Best Case: 3 Vergleiche) notwendig –> Beschränkung durch Konstante.
=> O(log(N))
Wieso sind 2-3-Bäume unattraktiv?
Vielzahl an Fallunterscheidungen benötigt (mehrere Schlüssel pro Knoten)
- Unterschiedliche Implementierung (Binäre und Tertiäre Knoten)
- Einfügen Fallunterscheidung. Ggf Umwandlung Binär in Tertiär
- > Auswahl des Mittleren Knotens fordert erweiterten Vergleich und Zuordnungen
Wodurch wird die Begrifflichkeit von Balancierten BINÄREN Suchbäumen festgemacht?
Höhe des Baums, bzw. Höhenunterschied der Teilbäume (möglichst geringer Unterschied)
Wie ist die Höhe eines leeren Binären Suchbaums definiert?
Gar nicht
Was ist ein leerer Suchbaum beim erweiterten binären Bäumen?
Spezielle Blattknoten (Externe Knoten)
Sind binäre Suchbäume ebenfalls perfekt (Baumstruktur) wie 2-3-Bäume? Falls Nein: Wieso und in welchen Fällen ist dies nicht der Fall?
Nein, da bei bestimmter Schlüsselzahl eine neue Ebene erstellt wird, die nicht vollständig ist.
Nur vollständig bei Schlüsselanzahl, die in 2^N - 1 dargestellt werden kann
Welche Anzahl Schlüssel können 2-3-Bäume mindestens und höchstens enthalten? (Abhängig von der Höhe H)
Zwischen 2^H - 1 bis 3^H - 1
Was bedeutet bei Binären Suchbäumen die Begrifflichkeit der Vollständigkeit?
Die höchste Ebene muss nicht vollständig besetzt sein. Alle anderen jedoch schon.
Welche 5 Eigenschaften haben Rot-Schwarz-Bäume?
B-WARE
Blätter - Blätter sind Schwarz
W - Wurzel Schwarz
A - Anzahl Schritte der Pfade(schwarze Knoten) bis alle Nachfolgeblätter immer gleich
R - Rote Knoten haben immer Schwarze Kindsknoten
E - Knoten Entweder Rot oder Schwarz
Was ist nach Sedgewick bezüglich der Roten Kanten (Kantenfarbe = Farbe des Kindsknoten) entscheidend?
Nur linke Kanten dürfen rot sein!
this. root = insert(this.root, key);
