Bäume

Question 1

Was ist der Grad eines Knotens?

Answer 1

Die Anzahl an Nachfolger.

Question 2

Was ist der Grad eines Baumes?

Answer 2

Die maximale Anzahl an Nachfolger, die ein Knoten in diesen Baum haben kann.

Question 3

Wie lässt sich die Tiefe eines Baumes herausfinden?

Answer 3

Durch Zählen der Kanten des längsten Pfads.

Question 4

Wie lässt sich die Tiefe eines Knotens herausfinden?

Answer 4

Durch Zählen der Kanten des Pfads, der von der Wurzel zum Knoten führt.

Question 5

Auf welcher Ebene ist die Wurzel?

Answer 5

Auf Ebene 0.

Question 6

Wodurch sind Binäre Bäume charakterisiert?

Answer 6

Der Grad des Baumes ist 2.

Question 7

Was ist ein binärer Suchbaum?

Answer 7

Wenn von der Wurzel und jedem Knoten aus links immer die kleineren Werte und rechts die größeren Werte vorzufinden sind, ist es ein binärer Suchbaum.

Question 8

Was ist eine Traversierung?

Answer 8

Alle Knoten von einem Baum werden systematisch abgearbeitet.

Question 9

Beschreibe die Preorder-Traversierung!

Answer 9

1. Es wird die Wurzel betrachtet, als
2. wird der linke Teilbaum betrachtet und als
3. wird der rechte Teilbaum betrachtet

Question 10

Beschreibe die Inorder-Traversierung!

Answer 10

1. Es wird der linke Teilbaum betrachtet, als
2. wird die Wurzel betrachtet und als
3. wird der rechte Teilbaum betrachtet

Question 11

Beschreibe die Postorder-Traversierung!

Answer 11

1. Es wird der linke Teilbaum betrachtet, als
2. wird der rechte Teilbaum betrachtet und als
3. wird die Wurzel betrachtet

Question 12

Wie läuft die binäre Suche in einem binären Suchbaum ab?

Answer 12

1. wird überprüft, ob der Baum und der gesuchte Wert einen Inhalt hat und gegebenenfalls null zurückgegeben, als
2. wird in den linken Teilbaum gegangen, falls der gesuchte Inhalt kleiner als der Wurzelinhalt ist. Falls dies nicht der Fall ist, wird als
3. in den rechten Teilbaum gegangen, falls der gesuchte Inhalt größer als der Wurzelinhalt ist. Falls dies nicht der Fall ist, wird als
4. der Wurzelinhalt zurückgegeben.

Question 13

Wie läuft das Einfügen eines Inhalts in einen binären Suchbaum ab?

Answer 13

1. wird überprüft ob der einzufügende Inhalt einen Wert hat, als
2. wird überprüft, ob der Baum leer ist und gegebenenfalls der Inhalt in die Wurzel gepackt. Falls dies nicht der Fall ist, wird als
3. der Auftrag des Einfügens mit dem linken Teilbaum gestartet, falls der einzufügende Inhalt kleiner, als der Wurzelinhalt ist. Falls dies nicht der Fall ist, wird als
4. der Auftrag des Einfügens mit dem rechten Teilbaum gestartet, falls der einzufügende Inhalt größer, als der Wurzelinhalt ist.

Question 14

Wie läuft das Entfernen eines Inhalts aus einem binären Suchbaum ab?

Answer 14

1. Falls der zu entfernende Inhalt gefunden wurde:
   - Falls der Baum keine Teilbäume hat, also ein Blatt ist, wird der Inhalt einfach null gesetzt.
   - Falls er nur einen Teilbaum besitzt kann dieser einfach aufrücken.
   - Falls der Baum zwei nichtleere Teilbäume hat, wird das Maximum des linken Teilbaums an die Stelle des gelöschten Knoten gesetzt und das Maximum wird nach den oberen Prinzipien gelöscht.
2. Falls der zu entfernende Inhalt noch nicht gefunden wurde wird nach der binären Suche weitergesucht.

Question 15

Was ist ein Partiell geordneter Baum?

Answer 15

Der Wert eines Knotens ist immer größer oder kleiner, als seine Nachfolger.

Question 16

Was ist ein AVL-Baum?

Answer 16

Ein ausbalancierter Baum, der auf jeder Seite ca. gleich viele Nachfolger hat. Wird mithilfe eines Balancefaktors bestimmt.

Question 17

Wie wird der Balancefaktor in einem AVL-Baum berechnet?

Answer 17

BF = Höhe rechter Teilbaum - Höhe linker Teilbaum

Question 18

Wann tritt eine Rotation in einem AVL-Baum ein?

Answer 18

Wenn der BF kleiner als -1 oder größer als 1 eines Knotens ist.

Question 19

Wie läuft die Rotation in einem AVL-Baum ab?

Answer 19

Wenn der BF kleiner als -1 ist und dessen Nachfolgers BF -1 ist, wird rechtsrotiert.
Wenn der BF größer als 1 ist und dessen Nachfolgers BF 1 ist, wird linksrotiert

Wenn der BF kleiner als -1 ist und dessen Nachfolgers BF 1 ist, wird linksrechtsrotiert.
Wenn der BF größer als 1 ist und dessen Nachfolgers BF -1 ist, wird rechtslinksrotiert

Question 20

Wie läuft eine Rechtsrotation in einem AVL-Baum ab?

Answer 20

Der linke Nachfolger des Knotens mit einem zu niedrigen BFs wird die neue Wurzel des Teilbaums und der Knoten mit dem zu niedrigen BF wird dessen rechter Nachfolger.

Question 21

Wie läuft eine Linksrotation in einem AVL-Baum ab?

Answer 21

Der rechte Nachfolger des Knotens mit einem zu hohen BFs wird die neue Wurzel des Teilbaums und der Knoten mit dem zu hohen BF wird dessen linker Nachfolger.

Question 22

Wie läuft eine Linksrechtsrotation in einem AVL-Baum ab?

Answer 22

Der rechte Nachfolgerteilbaum wird linksrotiert und dann wird der eigentliche Baum rechstrotiert. Danach hat die Wurzel des Baumes einen Nachfolger zu viel, also muss dieser in den rechten Teilbaum eingefügt werden.

Question 23

Wie läuft eine Rechtslinksrotation in einem AVL-Baum ab?

Answer 23

Der linke Nachfolgerteilbaum wird rechtsrotiert und dann wird der eigentliche Baum linksrotiert. Danach hat die Wurzel des Baumes einen Nachfolger zu viel, also muss dieser in den linken Teilbaum eingefügt werden.