Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

corrige Chapitre option informatique Corrigé des exercices ? Arbres binaires ? Exercice ? La première solution qui vient à l ? esprit est sans doute celle-ci let rec profondeur p function Nil ?? a when p ?? a Noeud fg fd ?? profondeur p ?? fg profondeur p

Chapitre option informatique Corrigé des exercices ? Arbres binaires ? Exercice ? La première solution qui vient à l ? esprit est sans doute celle-ci let rec profondeur p function Nil ?? a when p ?? a Noeud fg fd ?? profondeur p ?? fg profondeur p ?? fd mais elle n ? est pas optimale car il faut se souvenir que la concaténation de deux listes e ?ectue un nombre d ? insertions en tête de liste égal à la longueur de la liste de gauche Dans le cas d ? un arbre complet de hauteur p le nombre tp d ? insertions e ?ectuées véri ?e la relation tp tp ?? p ?? Celle-ci se résout en sommant l ? égalité télescopique tp p ?? tp ?? p ?? soit tp p p ?? Ainsi dans le cas d ? un arbre binaire complet le coût de cette fonction est un n log n avec n A p ?? On peut faire mieux en utilisant un accumulateur let profondeur let rec aux acc p function Nil ?? raise Not found a when p ?? a acc Noeud fg fd ?? aux aux acc p ?? fd p ?? fg in aux Avec cette fonction chaque arbre n ? est inséré qu ? une fois en tête de liste ce qui est optimal dans le cas de l ? arbre binaire complet le nombre d ? insertion est égal à p le coût est un n ? Exercice ? Le calcul de la hauteur d ? un arbre est linéaire vis-à-vis de la taille de l ? arbre donc lorsque A est un arbre binaire complet de taille n le coût tn de cette fonction véri ?e la relation tn t n n D ? après le théorème ma? tre tn n log n Le cas d ? un arbre incomplet est plus délicat à étudier à cause de l ? évaluation paresseuse mais on peut au moins donner une majoration du coût tn tp tq n avec p q n ?? ce qui permet d ? obtenir tn O n dans le cas général De toute façon on peut faire mieux en utilisant une fonction auxiliaire qui calcule la hauteur en même temps qu ? elle détermine si l ? arbre est complet ou non let est complet a let rec aux function Nil ?? true ?? Noeud fg fd ?? let b h aux fg and b h aux fd in b b h h max h h in fst aux a Le coût de cette fonction véri ?e cette fois la relation tn tp tq avec p q n ?? ce qui conduit à tn n le coût est linéaire dans tous les cas Jean-Pierre Becirspahic C option informatique ? Exercice ? On génère un arbre complet de taille n s ? il en existe à l ? aide de la fonction let rec complet function ?? Nil n when n mod ?? failwith complet n