L3 MIASHS, Algorithme et Programmation 3, année 2022

Ceci est un DM facultatif.

La date de rendu est le 16 décembre.

L’objectif est d’implémenter une structure de donnée MutableMapping via un arbre binaire équilibré.

Arbre simple

1. Créer une classe Noeud tel que:

• Chaque instance possède un fils droit et un fils gauche et une valeur
• Par défaut les fils droit et gauche sont soit None soit des instances de Noeud.

Si les deux fils d’un noeud sont None, on dit que le noeud est une feuille.

• Ajouter un propriété feuille qui retourne si un noeud est une feuille

2. Créer une classe Arbre qui surcharge MutableSet et qui:

• possède une racine qui est une soit une instance de Noeud soit None si l’arbre est vide
• possède deux propriétés ArbreGauche et ArbreDroit qui sont des arbres dont les racine sont les fils gauche et droit du noeud racine.

La profondeur d’un arbre est définit ainsi:

• Si la racine est None, sa profondeur est 0

• Sinon, la profondeur est le max de la profondeur de ArbreGauche et ArbreDroit.

• Ajoutez une propriété profondeur qui retourne la profondeur de l’arbre.

• Faites en sorte que la taille et la profondeur soit en complexité \(O(1)\) (par exemple en les stockant et en les mettant à jour).

Arbre monotone

3. Un Arbre est dit monotone si:

• le hash de la valeur maximale de l’arbre gauche est plus petite que le hash de la valeur de la racine
• le hash de la valeur minimale de l’arbre droit est plus petite que le hash de la valeur minimal de l’arbre de droite.

Surcharger la classe Arbre en une classe ArbreMonotone

Écrire des propriétés:

• min qui retourne le plus petit hash de toutes les valeurs de l’arbre
• max qui retourne le plus grand hash de toutes les valeurs de l’arbre
• monotone qui retourne si l’arbre est monotone

Faites en sorte que la méthode add préserve la propriété monotone.

4. Surcharger __contains__ pour réaliser une implémentation en O(d) où d est la profondeur de l’abre.

5. Trouver des exemples de taille arbitraire d’ArbreMonotone où la taille de l’arbre et sa profondeur sont égale.

Arbre monotone équilibrés

Lire la page wikipedia sur les rotations dans les arbres binaires de recherche

Un arbre est dit équilibré si l’arbre gauche et l’arbre droit ont le même nombre de noeud (plus ou moins un noeud).

6. Surcharger la classe ArbreMonotone en une classe ArbreEquilibre en ajoutant des opérations de RotationGauche et RotationDroite en place.

Ajouter une méthode RotationDroite et RotationGauche qui modifie en place l’arbre après ces opérations.

7. Surcharger l’opération add et l’opération discard pour garantir que votre arbre est toujours équilibré

8. Faites une analyse de complexité de votre structure de données

Compiled the: mer. 04 sept. 2024 12:49:53 CEST