A. Sigayret : Algorithmique

Exercices d'algorithmique : série 7


Un arbre binaire A est une structure de données récursive composée d'un élément (appelé noeud père ou parent) qui peut avoir un ou deux successeurs (appelés respectivement fils ou enfant gauche et droit), qui sont aussi des arbres. Nous choisirons les actions élémentaires suivantes :
estvide(A) : teste si l'arbre A ne contient aucun noeud.
creernoeud(x) : créer un arbre à un noeud étiqueté par x.
estfeuille(A) : teste si un arbre non vide n'a aucun fils.
etiquette(A) : retourne la valeur du noeud de A. SAG(A) : retourne le sous-arbre gauche de l'arbre A. Par convention, le sous-arbre gauche d'un arbre feuille est vide. SAD(A) : retourne le sous-arbre droit de l'arbre A. Par convention, le sous-arbre droit d'un arbre feuille est vide. ajoutgauche(A) : ajoute un fils gauche à un arbre sans fils gauche.
ajoutdroit(A) : ajoute un fils gauche à un arbre sans fils gauche.
supprimegauche(A) : supprime le fils gauche d'un arbre. par convention ne fait rien si l'arbre est vide.
supprimedroit(A) : supprime le fils droit d'un arbre. par convention ne fait rien si l'arbre est vide.

Exercice 7.1.
On veut transférer les étiquettes d'un arbre dans une file. Ecrire un algorithme pour chacune des variantes du parcours de l'arbre selon l'ordre dans lequel les noeuds sont placés dans la file. En faire la preuve et montrer que la complexité du problème est linéaire dans la taille de l'arbre.
a) Parcours préfixe : étiquette du noeud courant, puis étiquettes du fils gauche, puis étiquettes du fils droit.
b) Parcours infixe : étiquettes du fils gauche, puis étiquette du noeud courant, puis étiquettes du fils droit.
c) Parcours postfixe : étiquettes du fils gauche, puis étiquettes du fils droit, puis étiquette du noeud courant.

Exercice 7.2.
Ecrire un algorithme pour chacun des problèmes suivants et donner sa complexité.
a) Calculer la taille n d'un arbre binaire (nombre de noeuds).
b) Calculer la hauteur d'un arbre binaire, càd. le nombre maximum de noeuds dans un chemin reliant la racine à une feuille.
c) Tester si une valeur appartient à un arbre.
d) Déterminer la valeur maximale contenue dans un arbre.

Exercice 7.3.
Ecrire un algorithme pour chacun des problèmes suivants et donner sa complexité.
a) Calculer la profondeur d'un noeud donné, qui est la distance entre la racine et ce noeud (on supposera l'étiquette x unique).
b) Calculer la distance entre deux noeuds x et y quelconques.
c) Déterminer le plus proche ancêtre commun de deux sommets, càd le noeud le plus loin de la racine de l'arbre qui est la racine d'un sous-arbre contenant les deux sommets considérés.
d) Tester si un arbre binaire est équilibré, càd. si la différence de distance entre la racine et les différentes feuilles est inférieure ou égale à 1. Quelle est la profondeur maximale d'un arbre binaire équilibré de taille n ?

Exercice 7.4.
On peut représenter une expression algébrique par un arbre binaire où chaque feuille contient un nombre et les autres noeuds (internes) contiennent un opérateur. Par exemple l'arbre syntaxique de 12+54 a une racine avec "+", un fils gauche avec "12" et un fils droit avec "54".
a) En tenant compte des propriétés des opérateurs numériques, dessiner l'arbre syntaxique des expressions suivantes. E1=12*4-9. E2=12*(4-9). E3=5*7*22. E4=6+7+3+7. E5=(61+3*12)*((94+43)*74).
b) Pourquoi y a-t-il plusieurs arbres binaires associables à certaines expressions ?
c) Ecrire un algorithme qui parcourt un arbre syntaxique pour donner la valeur de l'expression numérique associée. Est-il gênant qu'il puisse y avoir plusieurs arbres pour une même expression ?
d) Ecrire un algorithme qui parcourt un arbre syntaxique pour retrouver l'expression numérique bien parenthésée associée représentée par une liste.
e) Ecrire un algorithme qui utilise une pile pour évaluer une expression numérique bien parenthésée. Le problème est-il plus compliqué si l'expression est parenthésée a minima ?

Exercice 7.5.
On veut réaliser des partitions successives d'un ensemble d'entiers à n éléments E={0,1,...n}. Pour cela, on étiquette la racine d'un arbre avec E. Le fils gauche contiendra la partie de E contenant les nombre divisibles par 2 et la partie droite les autres. Pour chacun de ces fils, on séparera dans le fils gauche les diviseurs de 3 et dans le fils droit les autres. Et ainsi de suite jusqu'à arriver à une feuille quand un des fils devrait contenir un ensemble vide.
a) Déterminer, en fonction de la représentation de l'ensemble E et de sa taille, la complexité du problème de partition élémentaire par un diviseur. b) Ecrire l'algorithme de partitions successives. Quelle est la hauteur de l'arbre obtenu ? Quelle est la complexité de votre algorithme ?

Exercice 7.6.
a) On veut construire la liste de toutes les permutations d'un ensemble à n éléments E={x1,...,xn}.
Ecrire l'algorithme correspondantet donner sa complexité.
b) On veut construire la liste de tous les sous-ensembles propres (sans E ni {}) d'un ensemble à n éléments E={x1,...,xn}.
Ecrire l'algorithme correspondantet donner sa complexité.

Exercice 7.7.
Un arbre binaire de recherche (ABR) est un arbre binaire à étiquettes numériques défini récursivement par :
– l'étiquette de la racine est inférieure ou égale à toutes les étiquettes du sous-arbre droit et strictement supérieure à toutes les étiquettes du sous-arbre gauche, et
– cette propriété est valable pour tous les sous-arbres de cet arbre.
a) Ecrire un algorithme qui détermine si un arbre binaire est un ABR.
b) Donner un exemple d'ABR qui n'est pas équilibré, un exemple d'arbre binaire équilibré qui n'est pas un ABR.
c) Ecrire un algorithme qui détermine l'étiquette maximale d'un ABR. La complexité du problème est-elle meilleure que dans un arbre quelconque ?
d) Ecrire un algorithme qui détermine l'étiquette minimale d'un ABR. La complexité du problème est-elle meilleure que dans un arbre quelconque ?
e) Ecrire un algorithme qui transfert les étiquettes d'un ABR vers un tableau par ordre croissant de valeurs.
f) Ecrire un algorithme qui transfert les étiquettes d'un ABR vers une file par ordre croissant de valeurs.
g) Donner une schéma algorithmique puis un algorithme précisé pour ajouter une valeur à un ABR.
h) Si on veut supprimer d'un ABR, quels sont les différents cas à considérer ? Donner un schéma algorithmique correspondant.

Exercice 7.8.
Un tas est un arbre binaire défini récursivement par :
– la racine de l'arbre contient la valeur maximale, et
– cette propriété est valable pour tous les sous-arbres.
N.B. S'il y a plusieurs instances de la valeur maximale, l'une d'elle est à la racine. Par convention, un tas est un "tas-max" (un "tas-min" utiliserait la valeur minimale ce qui revient au même).
a) Montrer que pour l'ensemble de valeurs {-4,-2,-2,5,8,10,10} il existe plusieurs manières de construire un tas.
b) On veut transférer les éléments d'un tas dans un tableau T tel que :
– Le premier élément du tableau correspond à la racine du tas, et
– si un élément du tas est placé en T[i], la racine de son fils gauche est dans T[2*i] et la racine de son fils droit dans T[2*i+1]. Par conséquent, le père d'un sommet en T[j] est en T[j div 2]. Un tel tableau sera appelé ici tableau-tas.
Ecrire l'algorithme correspondant.
Remarque. Ce type de numérotation est utilisée en généalogie où, à rebours, le père d'un numéro i a le numéro 2*i et sa mère le numéro 2*i+1.
c) Ecrire un algorithme qui donne le maximum d'un tableau-tas T. Même question pour le minimum.
d) Ecrire un schéma algorithmique qui permet d'ajouter un élément dans un tableau-tas. Quelle est s complexité ? Peut-on faire mieux ? Mêmes questions pour le retrait d'un élément.
e) On souhaiterait concevoir des tas basés sur des arbres ternaires. Est-ce possible ? Si oui quelle sera l'impact sur les complexité des algorithmes correspondants, si non, pourquoi ?

Exercice 7.*.
On souhaiterait utiliser un ABR qui soit équilibré et qui le reste si on ajoute ou retire une valeur de l'arbre.
a) En quoi cet équilibre optimise-t-il la complexité de recherche d'une valeur dans un arbre binaire ?
b) Pourquoi l'algorithme d'ajout d'une valeur est-il plus compliqué à écrire ? Ecrire cet algorithme avec une complexité aussi bonne que l'algorithme de recherche (difficile).