Remerciez-le!

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

Sda td5 arbres equilibres corrige

Licence Informatique TD Arbres Binaires Equilibrés - Corrigé Arbres AVL Exercice Il y en a Exercice Les noeuds ?? ? et ?? ? ne respectent pas la propri ?et ?e Dans ce cas on peut faire une rotation gauche soit en soit en pour r ?etablir l ? ?equilibre Par exemple rotation en Exercice Comme on n ? insere qu ? une feuille la hauteur ne peut changer que pour les anc etre de cette feuille Par cons ?equent les n ?uds d ?es ?equilibr ?es se trouvent tous sur le chemin allant de la nouvelle feuille a la racine C a en fait O log n On remarque que le d ?es ?equilibre di ? ?erence de hauteur ne peut etre que de d ?es ?equilibr ?e ou ?equilibr ?es Exercice L ? algorithme page suivante consiste a tester pour chaque noeud si la di ? ?erence entre les hauteurs de chacun des deux ?ls est au plus C ? est une fonction r ?ecursive qui renvoie une valeur ?? - si le sous-arbre est d ?es ?equilibr ?e pas ABR ?? la hauteur ? du sous-abre si c ? est un ABR Pour analyser la complexit ?e on remarque que l ? algorithme s ? appelle r ?ecursivement exactement une fois sur chaque n ?ud c ? est un parcours d ? arbre classique en O n CTestABR N N ?ud entier d ?ebut si est-vide N alors retourner ?n g TestABR G N d TestABR D N si g ?? ou d ?? ou g ?? d alors retourner - ?n retourner max g d ?n Exercice On ne représente pas ici toutes les étapes L ? insertion se fait comme dans un ABR Ensuite il y'a éventuellement quelque chose à faire si l ? arbre n ? est plus un AVL D ?es ?equilibre ??adroite ? - en Comme au noeud le d ?es ?equilibre esta gauche il faut faire une double rotation a droite en puisa gauche en C d ?es ?equilibre ??gauche-gauche ? en On fait une rotation a droite D ?es ?equilibre en Double rotation gauche en puis droite en D ?es ?equilibre en Rotation gauche D ?es ?equilibre en en aussi mais on commence par remonter depuis le noeud que l ? on a ajout ?e Double rotation C D ?es ?equilibre en Double rotation d ?es ?equilibre en Rotation gauche Le predecesseur de n ? a qu ? un ?ls On remplace par et cela ne desequilibre pas l ? arbre La suppression de est sans probleme Celle de feuille maintenant d ?es ?equilibre son pere Roration - C Exercice Une fac on simple et rapide est de refaire l ? arbre de z ?ero En e ?et on peut facilement construire un ABR ?equilibr ?e depuis un tableau tri ?e Une premiere ?etape consiste donca faire un parcours in ?xe de l ? ABR de d ?epart pour obtenir le tableau T de ses ?el ?ements tri ?e par ordre