Was ist ein Baum in der Informatik?
Datenstruktur, die Objekte in einer hierarchischen Struktur speichert.
Wie genau ist der Aufbau eines Baums in der Informatik?
Wurzel: Der oberste Knoten in einem Baum.
Knoten: Jedes Element in einem Baum. Es kann einen Elternknoten und null oder mehr Kindknoten haben.
Eltern: Ein Knoten, der Subknoten (Kinder) hat.
Kind: Ein Knoten, der direkt unter einem anderen Knoten (Elternteil) steht.
Blatt: Ein Knoten, der keine Kinder hat.
Geschwister: Knoten mit demselben Elternteil.
Ebene: Die "Höhe" oder "Tiefe" eines Knotens, definiert als die Anzahl der Kanten auf dem Weg von der Wurzel zu diesem Knoten.
Unterbaum: Ein Teilbaum, der von einem Knoten und seinen Nachkommen gebildet wird.
Wie lauten die drei Traversierungsalgorithmen?
Inorder-Traversierung (Symmetrische Ordnung)
Preorder-Traversierung (Vororder)
Postorder-Traversierung (Nachorder)
Wie funktioniert die Inorder-Traversierung?
Die Knoten werden in der Reihenfolge linker Knoten, Wurzelknoten, rechter Knoten besucht
Schritt für Schritt:
Starte beim Wurzelknoten: Beginne mit dem Wurzelknoten des Baumes.
Durchlaufe den linken Unterbaum: Bevor du den aktuellen Knoten verarbeitest (oder "besuchst"), durchlaufe zuerst den linken Unterbaum des Knotens. Dies geschieht rekursiv, das bedeutet, du führst die Inorder-Traversierung auch für den linken Unterbaum durch.
Besuche den Knoten: Sobald du den linken Unterbaum vollständig durchlaufen hast, verarbeite den aktuellen Knoten. Bei einer Ausgabeoperation würdest du den Wert des Knotens ausgeben.
Durchlaufe den rechten Unterbaum: Danach durchlaufe den rechten Unterbaum des Knotens, ebenfalls rekursiv.
Wiederhole den Vorgang: Führe diese Prozedur für alle Knoten durch, bis alle Knoten des Baumes besucht wurden.
Wie funktioniert die Preorder-Traversierung?
Die Knoten werden in der Reihenfolge Wurzelknoten, linker Knoten, rechter Knoten besucht.
Besuche den Knoten: Als erstes verarbeite den aktuellen Knoten. Bei einer Ausgabeoperation würdest du zum Beispiel den Wert des Knotens ausgeben.
Durchlaufe den linken Unterbaum: Nachdem du den aktuellen Knoten verarbeitet hast, durchlaufe den linken Unterbaum des Knotens. Dies geschieht rekursiv, das heißt, du führst die Preorder-Traversierung auch für den linken Unterbaum durch.
Durchlaufe den rechten Unterbaum: Sobald du den linken Unterbaum vollständig durchlaufen hast, durchlaufe den rechten Unterbaum des Knotens, ebenfalls rekursiv.
Wie funktioniert die Postorder-Traversierung?
Die Knoten werden in der Reihenfolge linker Knoten, rechter Knoten, Wurzelknoten besucht.
Durchlaufe den linken Unterbaum: Zuerst durchlaufe den linken Unterbaum des Knotens. Dies geschieht rekursiv, das heißt, du führst die Postorder-Traversierung auch für den linken Unterbaum durch.
Durchlaufe den rechten Unterbaum: Nachdem du den linken Unterbaum vollständig durchlaufen hast, durchlaufe den rechten Unterbaum des Knotens, ebenfalls rekursiv.
Besuche den Knoten: Nachdem du den linken und rechten Unterbaum durchlaufen hast, verarbeite den aktuellen Knoten. Bei einer Ausgabeoperation würdest du zum Beispiel den Wert des Knotens ausgeben.
Was bedeutet Beschränktheit bei einem Baum?
Ein beschränkter Baum ist ein Baum, in dem der Grad (die Anzahl der direkten Kinder) jedes Knotens auf ein Maximum beschränkt ist. Beispielsweise in einem Binärbaum ist der Grad jedes Knotens auf höchstens 2 beschränkt.
Was bedeutet Höhe eines Baums?
In der Informatik bezieht sich die Höhe oder Tiefe eines Baums auf die Länge des längsten Pfades von der Wurzel des Baums zu einem Blattknoten.
Was bedeutet Ausgeglichenheit eines Baums?
Ein ausgeglichener Baum ist ein Baum, in dem die Höhen der beiden Unterbäume jedes Knotens um nicht mehr als eins differieren.
Was bedeutet Voll ausgeglichen eines Baums?
Ein vollständig ausgeglichener Baum ist ein spezieller Typ eines ausgeglichenen Baumes, bei dem alle Blätter des Baums auf dem gleichen Level sind.
Was bedeutet Gleichverzweigt eines Baums?
Ein Baum ist gleichverzweigt, wenn alle Knoten die gleiche Anzahl an Kindknoten haben. Ein Binärbaum wäre zum Beispiel gleichverzweigt, wenn alle nicht-Blattknoten genau zwei Kinder haben.
Was bedeutet Blattknoten eines Baums?
Ein Knoten in einem Baum ohne Kinder wird als Blatt oder Blattknoten bezeichnet.
Was bedeutet Wurzel des Baums?
Die Wurzel ist der oberste Knoten in einem Baum.
Was bedeutet Grad eines Knotens?
Der Grad eines Knotens ist die Anzahl der Kinder dieses Knotens.
Was ist ein Binärbaum?
Ein Binärbaum ist ein Baum, bei dem jeder Knoten höchstens zwei Kinder hat, die üblicherweise als linkes Kind und rechtes Kind bezeichnet werden.
Was ist ein Vollständiger Binärbaum?
Ein Binärbaum ist ein vollständiger Binärbaum, wenn alle Levels des Baums außer möglicherweise dem letzten komplett gefüllt sind und alle Knoten im letzten Level so weit links wie möglich sind.
Was bedeuet Verzweigungsgrad eines Knotens?
Die maximale Anzahl von Kindern, die ein Knoten haben kann.
Was genau ist ein Pfad eines Baums?
Ein Pfad ist eine Sequenz von Kanten, die zwei Knoten in einem Baum verbindet.
Wie genau findet der Suchvorgang bei einem Binärbaum statt?
Beginnen Sie bei der Wurzel des Baums.
Wenn der Wert des gesuchten Elements gleich dem Wert der Wurzel ist, haben Sie das Element gefunden.
Wenn der Wert des gesuchten Elements kleiner ist als der Wert der Wurzel, suchen Sie im linken Unterbaum.
Wenn der Wert des gesuchten Elements größer ist als der Wert der Wurzel, suchen Sie im rechten Unterbaum.
Wiederholen Sie die Schritte 2-4 für den jeweiligen Unterbaum, bis Sie das Element gefunden haben oder bis Sie einen leeren Unterbaum erreichen, was bedeutet, dass das Element nicht im Baum vorhanden ist.
→ Für AVL immer nach jedem Schritt (Änderung des Baums) die Balancefaktoren überprüfen und ggf. balancieren
Wie genau findet der Löschvorgang bei einem Binärbaum statt?
Wenn der Knoten keine Kinder hat, entfernen Sie einfach den Knoten.
Wenn der Knoten ein Kind hat, ersetzen Sie den Knoten durch dieses Kind.
Wenn der Knoten zwei Kinder hat, ersetzen Sie den Knoten durch den kleinsten Wert im rechten Unterbaum (oder den größten Wert im linken Unterbaum), und löschen Sie diesen Knoten im Unterbaum.
Was ist ein AVL-Baum?
In einem AVL-Baum ist für jeden Knoten das absolute Höhendifferenz seiner beiden Unterbäume (linker Unterbaum und rechter Unterbaum) höchstens 1. Das bedeutet, kein Unterbaum kann mehr als eine Ebene tiefer sein als der andere Unterbaum.
Wenn eine Einfügung oder Löschung dazu führt, dass die Höhendifferenz der beiden Unterbäume eines Knotens größer als 1 wird (was bedeutet, dass der Baum unausgeglichen ist), wird eine sogenannte Rotationsoperation durchgeführt, um den Baum wieder auszugleichen.
Wie stellt man die Balancefaktoren bei einem AVL-Baum dar?
Zahl an der Wurzel. Rechts-Links=Balancefaktor
Wie viele Rotationsarten für einen AVL-Baum gibt es?
4 Arten von Rotationen
1. Einfache Linksrotation (LL)
2. Einfache Rechtsrotation (RR)
3. Doppelte Linksrotation (LR)
4. Doppelte Rechtsrotation (RL)
Wie genau funktioniert eine Einfache Linksrotation (LL)?
Wann zu benutzen?
wenn ein Knoten in den rechten Unterbaum des rechten Unterbaums eingefügt wird und der Baum deswegen aus dem Gleichgewicht gerät. In einer Linksrotation wird der unbalancierte Knoten zum linken Kind seines rechten Kindes.
Angenommen, wir haben drei Knoten A, B und C, wobei A der Elternknoten von B und B der Elternknoten von C ist und die Balance ins Negative gerät (d.h., der rechte Unterbaum ist schwerer).
Die Schritte zur Durchführung einer einfachen linken Rotation wären:
Setzen Sie B als neuen Elternknoten.
Setzen Sie A als linken Kindknoten von B.
Setzen Sie den rechten Kindknoten von A als linken Kindknoten von B.
Wie genau funktioniert eine Einfache Rechtsrotation (RR)?
wenn ein Knoten in den linken Unterbaum des linken Unterbaums eingefügt wird und der Baum deswegen aus dem Gleichgewicht gerät. In einer Rechtsrotation wird der unbalancierte Knoten zum rechten Kind seines linken Kindes.
Angenommen, wir haben drei Knoten A, B und C, wobei A der Elternknoten von B und B der Elternknoten von C ist und die Balance ins Positive gerät (d.h., der linke Unterbaum ist schwerer).
Die Schritte zur Durchführung einer einfachen rechten Rotation wären:
Setzen Sie A als rechten Kindknoten von B.
Setzen Sie den linken Kindknoten von A als rechten Kindknoten von B.
Wie genau funktioniert eine Doppelte Linksrotation (LR)?
wenn ein Knoten in den linken Unterbaum des rechten Unterbaums eingefügt wird und der Baum deswegen aus dem Gleichgewicht gerät. In einer doppelten Linksrotation wird zuerst eine Rechtsrotation auf dem rechten Kind des unbalancierten Knotens durchgeführt und dann eine Linksrotation auf dem unbalancierten Knoten.
Angenommen, wir haben drei Knoten A, B und C, wobei A der Elternknoten von B und B der Elternknoten von C ist und die Balance bei A ins Positive gerät und bei B ins Negative.
Die Schritte zur Durchführung einer linken-rechten Rotation wären:
Führen Sie eine einfache linke Rotation auf B und C durch.
Führen Sie eine einfache rechte Rotation auf A durch.
Wie genau funktioniert eine Doppelte Rechtsrotation (RL)?
wenn ein Knoten in den rechten Unterbaum des linken Unterbaums eingefügt wird und der Baum deswegen aus dem Gleichgewicht gerät. In einer doppelten Rechtsrotation wird zuerst eine Linksrotation auf dem linken Kind des unbalancierten Knotens durchgeführt und dann eine Rechtsrotation auf dem unbalancierten Knoten.
Angenommen, wir haben drei Knoten A, B und C, wobei A der Elternknoten von B und B der Elternknoten von C ist und die Balance bei A ins Negative gerät und bei B ins Positive.
Die Schritte zur Durchführung einer rechten-linken Rotation wären:
Führen Sie eine einfache rechte Rotation auf B und C durch.
Führen Sie eine einfache linke Rotation auf A durch.
Last changed2 years ago