Welche der Bäume sind korrekte, streng aufsteigend sortierte Binärbäume? Was sind die Fehler in den nicht korrekten Bäumen?

Geben Sie eine kurze Begründung.

Binärbaum 1	Binärbaum 2

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Welche der beiden Bäume sind korrekte AVL-Bäume? Was sind die Fehler in den nicht korrekten Bäumen?

AVL-Baum 1	AVL-Baum 2

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Antwort zu Frage 1: Binärbäume

Geben Sie eine kurze Begründung.

Welche der beiden Bäume sind korrekte Bruderbäume? Was sind die Fehler in den nicht korrekten Bäumen? Bitte geben Sie eine kurze Erklärung.

Bruder-Baum 1	Bruder-Baum 2

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Antwort zu Frage 2: AVL-Bäume

Der unten gezeigte Baum ist ein streng aufsteigend, sortierter Binärbaum und gleichzeitig ein AVL-Baum. Die Schlüssel in den Knoten sind ganze, positive Zahlen.
Fügen Sie 6 Knoten in das Diagramm ein.

• Wählen Sie die Knotenpositionen so, dass der Baum ein AVL-Baum bleibt.
• Tragen Sie dann die Schlüsselwerte so ein, dass der Baum streng sortiert bleibt.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 3: Bruderbäume

Was sind Brüder im Kontext von Brüderbäumen?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 4: Erweitern eines AVL-Baums

Eine mögliche Lösung

Wann ist ein Binärbaum ein Bruderbaum? Nennen Sie die Kriterien.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 5: Definition Bruder (bei Bruderbäumen)

Knoten die den gleichen Vater besitzen.

Welche Aufwände O(n) haben die folgenden Operationen bei nicht optimierten Implementierungen?

• Einfügen eines Elements am Kopf einer Liste
• Suchen eines Elements in einer Liste
• Finden eines Elements in einem balancierten Baum
• Finden eines Elements in einem Feld(Array) bei bekanntem Index
• Finden eines Elements in einem Feld(Array) wenn der Zugriffsindex nicht bekannt ist

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 6: Binär- und Bruderbäume

• Jeder innere Knoten hat einen oder zwei Söhne
• Jeder unäre Knoten hat einen binären Bruderknoten
• Alle Söhne haben die gleiche Tiefe

Welche drei Bedingungen gelten für einen Bruderbaum?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 7: Aufwände von Operationen in Listen, Warteschlangen und Bäumen

• Einfügen eines Elements am Kopf einer Liste: O(1)
• Suchen eines Elements in einer Liste: O(n)
• Finden eines Elements in einem balancierten Baum: O(logN)
• Finden eines Elements in einem Feld(Array) bei bekanntem Index: O(1)
• Finden eines Elements in einem Feld(Array) wenn der Zugriffsindex nicht bekannt ist: O(n)

Was gilt für alle Teilbäume eines AVL-Baums?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 8: Definition Bruderbaum

1. Jeder innere Knoten hat einen oder zwei Söhne
2. Jeder unäre Knoten hat einen binären Bruderknoten
3. Alle Söhne eines Vaters haben die gleiche Tiefe

Der Baum links, ist mit seinen äusseren Blattknoten (Werte 1 bis 6) streng aufsteigend sortiert. Warum ist dieser Baum kein Bruderbaum? Geben Sie eine kurze Erklärung. Zeichnen Sie rechts einen Baum, der ein streng aufsteigend sortierter Bruderbaum ist. Er soll die gleichen 6 äusseren Blattknoten (Wert 1 bis 6) besitzen.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 9: Anforderungen an einen AVL-Baum

Die Höhe des linken Unterbaums unterscheidet sich um maximal 1 von der Höhe des rechten Unterbaums.

Der links gezeigte Binärbaum ist streng aufsteigend sortiert. Er ist nicht höhenbalanciert. Transformieren Sie die Knoten dieses Baums so, dass ein höhenbalancierter, streng sortierter Binärbaum der entsteht.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 10: Bruderbaum korrigieren

Aufgabe	Lösung

Der links gezeigte streng sortierte Binärbaum ist kein AVL Baum. Warum ist er kein AVL Baum? Geben Sie eine kurze Begründung: Zeichnen Sie rechts die gleichen Knoten als einen streng aufsteigend, sortierten AVL-Baum ein:

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 11: Höhenbalancierter Binärtbaum

Aufgabe	Lösung

Die „einfache“ Warteschlange wird in echten Implementierungen eher selten eingesetzt. Nennen Sie den wichtigsten Nachteil einer „einfachen“ Warteschlange. Welcher Warteschlangentyp wird in realen Implementierungen eher eingesetzt. Nennen Sie den Fachbegriff. Was ist der Vorteil dieses Warteschlangentyps?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 12: AVL Baum: Fehler erkennen und korrigieren

Knoten „80“ hat keinen Unterbaum (Höhe 1). Der Unterbaum von „40“ rechts hat die Höhe 3. Die Unterbäume dürfen sich in der Höhe nur um 1 unterscheiden.

Aufgabe	Lösung

Nennen Sie drei Eigenschaften die für jeden inneren Knoten eines streng
aufsteigend sortierten Binärbaums gelten.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Antwort zu Frage 13: Warteschlangen

Einfache Warteschlangen können beliebig groß werden falls ein Prozessor, der die Warteschlange bedient ausfällt. Dieser Ausfalls des Prozessors der die Warteschlange abarbeitet und Elemente löscht wird dann zu einem Hauptspeicheproblem führen. Das Hauptspeicherproblem kann dann die gesamte Anwendung stoppen.

Die Lösung:

Ringsspeicher auch Ringpuffer genannt.

Sie haben einen konstanten Speicherverbrauch.

Der streng sortierte Binärbaum (rechts) gewährleistet einen Zugriff auf alle Knoten mit einem minimalen Aufwand. Zeichnen Sie rechts daneben einen streng sortierten Binärbaum mit den gleichen Werten der den höchstmöglichen (schlechtesten) Aufwand für den Zugriff auf alle Knoten besitzt

Die Antwort finden Sie unten auf dieser Seite.

Antwort zu Frage 14: Streng sortierte Binärbäume

1. Jeder Knoten hat einen oder zwei Söhne
2. Jeder linke Sohn ist kleiner als der Vater
3. Jeder rechte Sohn ist größer als der Vater

Antwort zu Frage 15: Maximaler Aufwand für Binärbaum