Binäre Suchbäume Flashcards
1
Q
Welche Höhe hat ein BST im Besten und im schlechtesten Fall?
A
- Vollstädniger BST mit n Knoten hat eine Höhe von Θ(lg n)
- Schlechtester Fall ist eine lineare Liste mit N Knoten hat dieser eine Höhe von Θ(n)
- Mit Rot-Schwarz und B Bäumen kann man den Best-case garantieren
- Auch randomized BST zeigen gutes Laufzeitverhalten
2
Q
Welche Attribute hat ein Knoten in einem Baum?
A
- key (und evtl. Satellitendaten)
- left: linker Nachfloger (Kind bzw. linker Teilbaum)
- right: rechter Nachfolger (Kind bzw. rechter Teilbaum)
- p: zeigt zum Elternknoten. p[root[T]] = NIL
3
Q
Was gibt die Inorder Traversierung aus?
A
Beim BST gibt die Inorder Traversierung eine Sortierte Liste aus und hat eine Laufzeit von Θ(n)
4
Q
Wie sucht man in einem Binären Suchbaum und wie ist die Laufzeit?
A
- Man vergleicht mit dem aktuellen Knoten
- Ist es größer macht man mit dem rechten Teilbaum weiter
- Ist es kleiner macht man mit dem linken Teilbaum weiter
- Ist es gleich ist die Suche beendet
- Laufzeit O(h), h = Baumhöhe
5
Q
Wie erhält man das Minimum oder das Maximum eines Baumes?
A
- Minimum Blatt des linkesten Teilbaums
- Maximum Blatt des rechtesten Teilbaums
- Beides ist in O(h), h = Baumhöhe
6
Q
Wie erhält man den Nachfolger eines Elements?
A
- Hat der Knoten einen rechten Teilbaum dann das kleinste Element in diesem
- Ansonsten gehe von unten nach Oben durch und der Nachfolger ist der parent-Knoten des ersten Knotens der ein linker Teilbaum ist (sich selbst eingeschlossen)
- Das Maximum hat keinen Nachfolger
7
Q
Wie erhält man den Vorgänger eines Elements?
A
- Hat der knoten einen linken Teilbaum dann das größte Element in diesem
- Ansonsten gehe von unten nach Oben durch und der Vorgänger ist der parent-Knoten des ersten Knotens der ein rechter Teilbaum ist (sich selbst eingeschlossen)
8
Q
Wie fügt man ein Element in den Baum ein?
A
- Zuerst setzt man vom einzufügenden Element beide Kinder auf NIL
- Dann macht man wie bei BTS Search vergleiche bis man am Ende des Baumes ist
- Dort fügt man das Blatt ein
9
Q
Wie löscht man ein Element aus einem Baum?
A
- Es gibt 3 Fälle
1. Z hat kein Kind - Lösche Z, indem der Elternknoten von z auf NIL zeigt, anstatt auf z
2. Z hat ein Kind - Lösche z, indem der Elternknoten von z auf das Kind von z zeigt, anstatt auf z
3. Z hat zwei Kinder - Der Nachfolger von z wird zum neuen Knoten und hat entweder ein oder kein Kind
- Hat der Nachfolger von z ein Kind muss der rechteste Teilbaum von diesem mit dem rechten Kind von z verbunden werden
