Netzwerk binärer Suchbäume mit Vererbung und Polymorphismus

Python Hard classes

Aufgabe «Netzwerk binärer Suchbäume mit Vererbung und Polymorphismus»

Implementieren Sie die Klasse Node für einen Knoten eines binären Suchbaums (BST) mit den Methoden insert, search, delete. Erstellen Sie die Klasse BST, die die Wurzel speichert und die Methoden insert (Wert hinzufügen), search (Wert suchen, gibt True/False zurück), delete (Wert löschen) und get_height (Baumhöhe) enthält. Erstellen Sie dann die Klasse AVLTree, die von BST erbt und insert sowie delete zur Unterstützung der Balancierung (mit Rotationen) überschreibt. Eingabedaten: eine Folge von Befehlen. Befehle: "insert x" fügt x hinzu, "delete x" löscht x (falls vorhanden), "search x" gibt "found" oder "not found" aus, "height" gibt die Baumhöhe aus. Für AVLTree wird nach jeder Einfügung/Löschung die Balance überprüft (Höhenunterschied der Teilbäume <= 1) und die entsprechende Rotation durchgeführt. Einschränkungen: -10^9 <= x <= 10^9, Anzahl der Befehle bis zu 10^5.

Eingabeformat

Erste Zeile: eine ganze Zahl n (1 <= n <= 10^5) — die Anzahl der Befehle. Dann n Zeilen, jede enthält einen Befehl: insert x, delete x, search x oder height.

Ausgabeformat

Geben Sie für jeden Befehl search "found" oder "not found" in einer separaten Zeile aus. Geben Sie für den Befehl height eine ganze Zahl aus — die Höhe des Baums (Höhe eines leeren Baums = 0).

Beispiele

Beispiel 1

EINGABE

AUSGABE

Beispiel 2

EINGABE

2
0 0 0
2 -2 2 -2

AUSGABE

main.py