Remerciez-le!

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

Ex03 1 corrige Corrigé de l ? examen de Structures de données du février Exercice Question A Un arbre AVL est un arbre binaire de recherche qui est H- équilibré Un arbre binaire de recherche est tel que la clé de tout n ?ud est plus grande que toutes les

Corrigé de l ? examen de Structures de données du février Exercice Question A Un arbre AVL est un arbre binaire de recherche qui est H- équilibré Un arbre binaire de recherche est tel que la clé de tout n ?ud est plus grande que toutes les clés des n ?uds de son sous arbre gauche et plus petite que toutes les clés des n ?uds de son sous arbre droit Un arbre binaire est H-équilibré si en tout n ?ud la di ?érence de hauteur entre les sous arbres gauche et droit est au plus de On peut constater sur l ? arbre donné qu ? il s ? agit bien d ? un arbre binaire de recherche et que de plus il est Héquilibré On peut le décorer avec les déséquilibres - Question B L ? adjonction dans un arbre AVL consiste d ? abord à faire une adjonction d ? une feuille dans un arbre binaire de recherche en recherchant l ? endroit o? doit être le n ?ud en tant que feuille Pour cela partant de la racine on descend dans l ? arbre à gauche ou à droite selon que la clé de l ? élément ajouté est inférieure ou supérieure à la clé du n ?ud jusqu ? à rencontrer un arbre vide qui est remplacé par un nouveau n ?ud contenant l ? élément ajouté Ensuite on remonte le chemin vers la racine en corrigeant les déséquilibres si on remonte depuis la gauche et ?? si on remonte depuis la droite en véri ?ant que le résultat reste dans les limites - ou et en pratiquant la rotation adaptée si ce n ? est pas le cas Dans tous les cas on arrête la remontée et les corrections lorsque le déséquilibre résultant est nul Question C On part de l ? arbre ci-dessus pour ajouter d ? abord étant plus grand que on descend à droite étant plus petit que on descend à gauche est plus grand que on descend à droite est plus petit que on descend à gauche On est sur un arbre vide qui est donc remplacé par le n ?ud ?ls gauche de Ceci porte le Cdéséquilibre de à celui de à ?? et celui de à Il faut alors pratiquer une rotation gauche-droite puisque le déséquilibre de est ?? Ceci met à la place de avec un déséquilibre nul la remontée est donc terminée et on obtient l ? arbre ci-dessous Pour ajouter dans ce nouvel arbre étant plus petit que on descend à gauche étant plus grand que on descend à droite étant plus grand que on descend à droite étant plus petit que on descend à gauche On est sur un arbre vide qui est donc remplacé par le n ?ud ?ls gauche de Ceci porte le déséquilibre de à celui de à ?? et celui de à ?? Il faut alors pratiquer une rotation à gauche puisque le déséquilibre de est ?? Ceci met à