Was ist der Grad eines Knotens?
Die Anzahl an Nachfolger.
Was ist der Grad eines Baumes?
Die maximale Anzahl an Nachfolger, die ein Knoten in diesen Baum haben kann.
Wie lässt sich die Tiefe eines Baumes herausfinden?
Durch Zählen der Kanten des längsten Pfads.
Wie lässt sich die Tiefe eines Knotens herausfinden?
Durch Zählen der Kanten des Pfads, der von der Wurzel zum Knoten führt.
Auf welcher Ebene ist die Wurzel?
Auf Ebene 0.
Wodurch sind Binäre Bäume charakterisiert?
Der Grad des Baumes ist 2.
Was ist ein binärer Suchbaum?
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.
Was ist eine Traversierung?
Alle Knoten von einem Baum werden systematisch abgearbeitet.
Beschreibe die Preorder-Traversierung!
- Es wird die Wurzel betrachtet, als
- wird der linke Teilbaum betrachtet und als
- wird der rechte Teilbaum betrachtet
Beschreibe die Inorder-Traversierung!
- Es wird der linke Teilbaum betrachtet, als
- wird die Wurzel betrachtet und als
- wird der rechte Teilbaum betrachtet
Beschreibe die Postorder-Traversierung!
- Es wird der linke Teilbaum betrachtet, als
- wird der rechte Teilbaum betrachtet und als
- wird die Wurzel betrachtet
Wie läuft die binäre Suche in einem binären Suchbaum ab?
- wird überprüft, ob der Baum und der gesuchte Wert einen Inhalt hat und gegebenenfalls null zurückgegeben, als
- wird in den linken Teilbaum gegangen, falls der gesuchte Inhalt kleiner als der Wurzelinhalt ist. Falls dies nicht der Fall ist, wird als
- in den rechten Teilbaum gegangen, falls der gesuchte Inhalt größer als der Wurzelinhalt ist. Falls dies nicht der Fall ist, wird als
- der Wurzelinhalt zurückgegeben.
Wie läuft das Einfügen eines Inhalts in einen binären Suchbaum ab?
- wird überprüft ob der einzufügende Inhalt einen Wert hat, als
- wird überprüft, ob der Baum leer ist und gegebenenfalls der Inhalt in die Wurzel gepackt. Falls dies nicht der Fall ist, wird als
- 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
- der Auftrag des Einfügens mit dem rechten Teilbaum gestartet, falls der einzufügende Inhalt größer, als der Wurzelinhalt ist.
Wie läuft das Entfernen eines Inhalts aus einem binären Suchbaum ab?
- 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. - Falls der zu entfernende Inhalt noch nicht gefunden wurde wird nach der binären Suche weitergesucht.
Was ist ein Partiell geordneter Baum?
Der Wert eines Knotens ist immer größer oder kleiner, als seine Nachfolger.
Was ist ein AVL-Baum?
Ein ausbalancierter Baum, der auf jeder Seite ca. gleich viele Nachfolger hat. Wird mithilfe eines Balancefaktors bestimmt.
Wie wird der Balancefaktor in einem AVL-Baum berechnet?
BF = Höhe rechter Teilbaum - Höhe linker Teilbaum
Wann tritt eine Rotation in einem AVL-Baum ein?
Wenn der BF kleiner als -1 oder größer als 1 eines Knotens ist.
Wie läuft die Rotation in einem AVL-Baum ab?
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
Wie läuft eine Rechtsrotation in einem AVL-Baum ab?
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.
Wie läuft eine Linksrotation in einem AVL-Baum ab?
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.
Wie läuft eine Linksrechtsrotation in einem AVL-Baum ab?
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.
Wie läuft eine Rechtslinksrotation in einem AVL-Baum ab?
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.
