Kursinhalt
Überblick Über Algorithmen und Datenstrukturen
Überblick Über Algorithmen und Datenstrukturen
Herausforderung: Ausgewogene Bäume
Ein ausgeglichener Baum, speziell ein ausgeglichener Binärer Suchbaum (BST), ist eine Baumdatenstruktur, bei der sich die Höhen der linken und rechten Teilbäume eines Knotens um höchstens eins unterscheiden. Diese Balance gewährleistet effiziente Such-, Einfüge- und Löschoperationen und hält die Zeitkomplexität dieser Operationen logarithmisch. In einem ausgeglichenen BST ist die Höhe des Baumes minimiert, was zu optimaler Leistung führt.
Schauen wir uns das Beispiel eines unausgeglichenen Baumes an:
Im bereitgestellten BST hat der linke Teilbaum des Wurzelknotens eine Höhe von 4, während der rechte Teilbaum nur eine Höhe von 2 hat. Dieser signifikante Unterschied in den Höhen zeigt an, dass der Baum unausgeglichen ist, was zu ineffizienten Such-, Einfüge- und Löschoperationen im Vergleich zu einem ausgeglichenen BST führt.
Swipe to start coding
Sie haben einen in Python implementierten Binärsuchbaum (BST) zur Verfügung. Ihre Aufgabe ist es, eine Funktion zu schreiben, die bestimmt, ob der BST ausgeglichen ist oder nicht.
Sie müssen die folgenden Schritte ausführen:
- Berechnen Sie die Höhe eines Teilbaums, der an einem gegebenen Knoten verwurzelt ist, rekursiv. Es gibt die maximale Höhe zwischen den linken und rechten Teilbäumen plus eins zurück (um den aktuellen Knoten zu berücksichtigen). Diese Logik wird in der Funktion
calculate_height()implementiert. - Überprüfen Sie rekursiv, ob der Teilbaum, der an einem gegebenen Knoten verwurzelt ist, ausgeglichen ist. Dies wird mit der Funktion
is_balanced_recursive()implementiert. Sie vergleicht die Höhen der linken und rechten Teilbäume und gibtFalsezurück, wenn der Unterschied in den Höhen größer als 1 ist, was auf ein Ungleichgewicht hinweist. - Um zu überprüfen, ob der Baum ausgeglichen ist, müssen Sie
is_balanced_recursive()mit der Baumwurzel als Argument aufrufen.
Lösung
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwendenDanke für Ihr Feedback!
Herausforderung: Ausgewogene Bäume
Ein ausgeglichener Baum, speziell ein ausgeglichener Binärer Suchbaum (BST), ist eine Baumdatenstruktur, bei der sich die Höhen der linken und rechten Teilbäume eines Knotens um höchstens eins unterscheiden. Diese Balance gewährleistet effiziente Such-, Einfüge- und Löschoperationen und hält die Zeitkomplexität dieser Operationen logarithmisch. In einem ausgeglichenen BST ist die Höhe des Baumes minimiert, was zu optimaler Leistung führt.
Schauen wir uns das Beispiel eines unausgeglichenen Baumes an:
Im bereitgestellten BST hat der linke Teilbaum des Wurzelknotens eine Höhe von 4, während der rechte Teilbaum nur eine Höhe von 2 hat. Dieser signifikante Unterschied in den Höhen zeigt an, dass der Baum unausgeglichen ist, was zu ineffizienten Such-, Einfüge- und Löschoperationen im Vergleich zu einem ausgeglichenen BST führt.
Swipe to start coding
Sie haben einen in Python implementierten Binärsuchbaum (BST) zur Verfügung. Ihre Aufgabe ist es, eine Funktion zu schreiben, die bestimmt, ob der BST ausgeglichen ist oder nicht.
Sie müssen die folgenden Schritte ausführen:
- Berechnen Sie die Höhe eines Teilbaums, der an einem gegebenen Knoten verwurzelt ist, rekursiv. Es gibt die maximale Höhe zwischen den linken und rechten Teilbäumen plus eins zurück (um den aktuellen Knoten zu berücksichtigen). Diese Logik wird in der Funktion
calculate_height()implementiert. - Überprüfen Sie rekursiv, ob der Teilbaum, der an einem gegebenen Knoten verwurzelt ist, ausgeglichen ist. Dies wird mit der Funktion
is_balanced_recursive()implementiert. Sie vergleicht die Höhen der linken und rechten Teilbäume und gibtFalsezurück, wenn der Unterschied in den Höhen größer als 1 ist, was auf ein Ungleichgewicht hinweist. - Um zu überprüfen, ob der Baum ausgeglichen ist, müssen Sie
is_balanced_recursive()mit der Baumwurzel als Argument aufrufen.
Lösung
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwendenDanke für Ihr Feedback!
Wechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwenden