algorithmique (école d'ingénieur) · Chapitre 9 · Application directe du cours

Taille et hauteur

Arbres binaires de recherche de coût minimum · niveau 1 (application)

Énoncé

Avec la classe AB du cours et ses primitives vide, vr, sag, sad :

écrire int taille(AB a), qui retourne le nombre de valeurs de l'arbre binaire $a$ . Exemple : l'arbre $(1 (2 () ()) (1 () ()))$ contient $3$ valeurs ;
écrire int h(AB a), qui retourne la hauteur de $a$ : celle de l'arbre vide vaut $- 1$ , celle d'un arbre non vide est la plus grande des hauteurs de ses deux sous-arbres, plus un ;
justifier que ces deux fonctions sont en $Θ (n)$ pour un arbre de $n$ valeurs.

Corrigé

Les deux fonctions suivent la définition d'un arbre binaire : vide (base), ou racine et deux sous-arbres (hérédité).


static int taille(AB a) {
    if (vide(a)) return 0;                            // aucune valeur
    return 1 + taille(sag(a)) + taille(sad(a));       // la racine et les deux sous-arbres
}
static int h(AB a) {
    if (vide(a)) return -1;                           // par convention, h(()) = -1
    return 1 + Math.max(h(sag(a)), h(sad(a)));
}

Avec $h (()) = - 1$ , une feuille a bien la hauteur $1 + max (- 1, - 1) = 0$ . Chaque fonction fait exactement un appel par sous-arbre, vide ou non : $n$ appels sur des arbres non vides et $n + 1$ sur des arbres vides, chacun en temps constant, soit $Θ (n)$ .


taille((1 (2 () ()) (1 () ()))) = 3, h = 1

100 % gratuit

La suite du chapitre est sur Adloun

Exercice suivant et tuteur

Sans compte : le cours et le premier QCM. Exercices et tuteur : inscription gratuite en 30 secondes, sans carte bancaire.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant et tuteur →