Réseau d'arbres binaires de recherche avec héritage et polymorphisme

Python Hard classes

Tâche «Réseau d'arbres binaires de recherche avec héritage et polymorphisme»

Implémentez la classe Node pour un nœud d'arbre binaire de recherche (BST) avec les méthodes insert, search, delete. Créez la classe BST qui stocke la racine et contient les méthodes insert (ajout d'une valeur), search (recherche d'une valeur, retourne True/False), delete (suppression d'une valeur) et get_height (hauteur de l'arbre). Créez ensuite la classe AVLTree, héritant de BST, redéfinissant insert et delete pour prendre en charge l'équilibrage (avec rotations). Données d'entrée : une séquence de commandes. Commandes : "insert x" ajouter x, "delete x" supprimer x (si présent), "search x" afficher "found" ou "not found", "height" afficher la hauteur de l'arbre. Pour AVLTree, après chaque insertion/suppression, l'équilibre est vérifié (différence de hauteur des sous-arbres <= 1) et la rotation correspondante est effectuée. Contraintes : -10^9 <= x <= 10^9, nombre de commandes jusqu'à 10^5.

Format d\ entrée

Première ligne : un entier n (1 <= n <= 10^5) — le nombre de commandes. Ensuite n lignes, chacune contient une commande : insert x, delete x, search x ou height.

Format de sortie

Pour chaque commande search, affichez "found" ou "not found" sur une ligne séparée. Pour la commande height, affichez un entier — la hauteur de l'arbre (hauteur d'un arbre vide = 0).

Exemples

Exemple 1

ENTRÉE

SORTIE

Exemple 2

ENTRÉE

2
0 0 0
2 -2 2 -2

SORTIE

main.py