Binäre Suchbäume (VL 10)

Question 1

Definition eines binären Suchbaums

Answer 1

• Binärbaum
• Enthält Elemente mit Schlüsseln
• Schlüssel eines jeden Knotens im rechten Teilbaum ist mind. so groß wie jeder Schlüssel im linken Teilbaum
• Schlüssel eines jeden Knotens im linken Teilbaum ist höchstens so groß, wie jeder Schlüssel im rechten Teilbaum
• Knoten besteht aus vier Feldern:
• • Schlüssel
• • Zeiger auf linken und rechten Teilbaum (können leer sein)
• • Zeiger auf Elternknoten (leer bei Wurzel)

Question 2

Vier Felder eines BST Knotens

Answer 2

• Schlüssel
• Zeiger auf linken und rechten Teilbaum (können leer sein)
• Zeiger auf Elternknoten (leer bei Wurzel)

Question 3

Zeitkomplexität bei Inorder Traversierung eines BSTs mit n Knoten

Answer 3

Θ(n)

Question 4

Strategie beim löschen in einem BST

Answer 4

Drei Fälle:

1) Der Knoten hat keine Kinder => Einfach löschen
2) Der Knoten hat ein Kind = > Vaterknoten mit Kindknoten direkt verbinden
3) Den zahlenmäßigen Nachfolger des Knotens suchen, löschen und für den Knoten einsetzen

Question 5

–( 1 )——-
-/—--——
[A]–(2)—-
—–/—-—
—[B]–[C]-

Rotiert nach links

Answer 5

—( 2 )—-
—/—--–
–( 1 )–[C]-
–/—-—-
[A]–[B]—

Question 6

Definition eines AVL-Baumes

Answer 6

• balanzierter BST
• für jeden Knoten unterscheiden sich die Höhen seiner Teilbäume um höchstens 1
• Teilbaumhöhen werden balanziert
• in jedem Knoten wird über die Höhe des Unterbaums Buch geführt
• Nach jeder ausgeführten Operation wird die Höhe wiederhergestellt
• Dadurch bleibt stets h ∈ Θ(log n) und Θ(log n) kann für alle Operationen garantiert werden