Kapitel 8: Bäume Teil II

Question 1

Was ist ein balancierter Baum ?

Answer 1

Suchbäume mit einer logarithmischen Höhe

Question 2

Best Case Höhe eines Baumes mit n Elementen

Answer 2

h = log2n

Question 3

2-3-4 Suchbaum:

Wieviel Nachfolger hat ein Knoten mit 2 Schlüsseln ?

Answer 3

3 (kleiner, zwischen und größer)

Question 4

Wieviele Schlüssel pro Knoten erlaubt der 2-3-4 Suchbaum ?

Answer 4

zwischen 1 und 3

Question 5

Vorteil 2-3-4 Suchbaum

Answer 5

Strukturänderungen am Baum (Einfügen und löschen) sind auf einen Teilbereich des Baumes beschränkt, der Aufwand wird reduziert.

Question 6

2-3-4 : Was passiert wenn man eine “28” bei einem Baum aus einem Knoten “3,4,19” einfügen möchte ?

Answer 6

• das mittlere Element nach oben ziehen (3 einzelne Knoten)
• Elternknoten “4”
• Links davon “3”
• Rechts davon “19,28”

Question 7

2-3-4: Was passiert wenn man ein Schlüssel hinzufügen möchte, der Knoten aber schon 3 Schlüssel enthält ?

Answer 7

Der mittlere Schlüssel wird der Elternknoten, die anderen beiden dessen Kindknoten

Question 8

Einfügen im 2-3-4 Suchbaum:

Was ist die Bottom-Up Methode ?

Answer 8

Das mittlere Schlüsselelement vom Blattknoten wird zum Elternknoten verschoben. Ist dieser wieder ein 4-Knoten, muss dieser Knoten auch aufgeteilt werden … (rekursive Methode)

Question 9

Einfügen im 2-3-4 Suchbaum:

Was ist die Top-Down Methode ?

Answer 9

Auf dem Weg von der Wurzel bis zur Einfügeposition (Blattknoten) werden alle besuchten 4-Knoten vorsorglich in 2-Knoten umgewandelt (iterative Methode)

Question 10

Einfügen im 2-3-4 Suchbaum:
Welche Methode ist günstiger ?
- Bottom-Up
- Top-Down

Answer 10

Top-Down

Question 11

Rot-Schwarz: Welche Farben haben neu einzufügende Blattknoten ?

Answer 11

Rot

Question 12

Rot-Schwarz: darf es zwei aufeinanderfolgende rote Knoten geben ?

Answer 12

Nein