Remerciez-le!

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

Exercice 1 Il y en a 6 3 2 4 1 5 3 1 4 2 5 3 2 5 1 4 3 1 5 2 4 2 1 4 3 5 4 2 5

Exercice 1 Il y en a 6 3 2 4 1 5 3 1 4 2 5 3 2 5 1 4 3 1 5 2 4 2 1 4 3 5 4 2 5 1 3 Exercice 2 Les noeuds “25” et “42” ne respectent pas la propri´ et´ e. Dans ce cas on peut faire une rota- tion gauche soit en 25 soit en 42 pour r´ etablir l’´ equilibre. Par exemple rotation en 42 : 42 25 54 12 63 Exercice 3 Comme on n’ins` ere 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 2 (d´ es´ equilibr´ e),1 ou 0 (´ equilibr´ es). Exercice 4 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 1. C’est une fonction r´ ecursive qui renvoie une valeur : – -1 si le sous-arbre est d´ es´ equilibr´ e (pas ABR) – la hauteur (≥0) 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). Licence 2 Informatique 12 / 2014 TD5: Arbres Binaires Equilibrés - Corrigé Arbres AVL TestABR (N : Nœud) : entier d´ ebut si est-vide(N) alors retourner 1 ﬁn g = TestABR(G(N)) d = TestABR (D(N)) si g = −1 ou d = −1 ou [g −d| > 1 alors retourner -1 ﬁn retourner 1+max(g,d) ﬁn Exercice 5 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. 25 60 35 D´ es´ equilibre “` a droite” (-2) en 25. Comme au noeud 60 le d´ es´ equilibre est ` a gauche (+1), il faut faire une double rotation : ` a droite en 60 puis ` a gauche en 25. 35 25 60 35 25 60 10 5 d´ es´ equilibre “gauche-gauche” en 25. On fait une rotation ` a droite. 35 10 60 5 25 35 10 60 5 25 20 D´ es´ equilibre en 35. Double rotation : gauche en 10 puis droite en 35 25 10 35 5 20 60 25 10 35 5 20 60 65 D´ es´ equilibre en 35. Rotation gauche 25 10 60 5 20 35 65 25 10 60 5 20 35 65 70 45 40 D´ es´ equilibre en 35 (en 25 aussi, mais on commence par remonter depuis le noeud que l’on a ajout´ e). Double rotation 25 10 60 5 20 40 65 70 35 45 25 10 60 5 20 40 65 70 35 45 50 D´ es´ equilibre en 25. Double rotation. 40 25 60 10 35 5 20 45 65 70 50 40 25 60 10 35 5 20 45 65 70 50 55 d´ es´ equilibre en 45. Rotation gauche 40 25 60 10 35 5 20 50 65 70 45 55 40 25 60 10 35 5 20 15 30 50 65 70 45 55 Le predecesseur de 25, 20, n’a qu’un ﬁls. On remplace 25 par 20 et cela ne desequilibre pas l’arbre! 40 20 60 10 35 5 15 30 50 65 70 45 55 La suppression de 30 est sans probl` eme. Celle de 35 (feuille maintenant) d´ es´ equilibre son p` ere 20. Roration 10-20. 45 20 60 10 5 15 50 65 70 55 45 10 60 5 20 15 50 65 70 55 Exercice 7 Une fa¸ con 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 premi` ere ´ etape consiste donc ` a faire un parcours inﬁxe de l’ABR de d´ epart pour obtenir le tableau T de ses ´ el´ ements, tri´ e par ordre croissant. Cela se fait en O(n). Ensuite nous allons faire du diviser pour r´ egner pour construire l’AVL : on ins` ere le m´ edian ` a la racine et on repart ` a gauche et ` a droite. Il n’y aura alors jamais de r´ e´ equilibrages ` a faire. Cela donne l’algorithme suivant, r´ ecursif (initialement sur un arbre r´ eduit ` a une feuille). ` A chaque appel, soit on place une valeur dans un nœud (ce qui arrive n fois) soit on ne fait rien (ce qui arrive au pire deux fois plus que le nombre d’appels r´ ecursifs) donc une complexit´ e totale de O(n). Notez que tous les nœuds ont un ´ equilibre de 0, sauf ceux sur le chemin allant du dernier nœud ins´ er´ e ` a la racine qui peuvent avoir +1 ou -1 comme d´ es´ equilibre. Construit ABR ´ Equilibr´ e(N : Nœud, T : tableau d’entiers, g, d :entiers) d´ ebut si g ≤d // NB : rien ` a faire si g > d : arbre vide alors m = (g+d)/2 // NB : ´ el´ ement m´ ediant de [g..d] val(N) = T[m] G(N) = ArbreVide( ) Construit ABR ´ Equilibr´ e(G(N),T , g, m −1) D(N) = ArbreVide( ) Construit ABR ´ Equilibr´ e(D(N),T , m + 1, d) ﬁn ﬁn Correction de l’exercice 1. Aucun n’est un rouge noir. Un arbre rouge noir est un arbre binaire de recherche comportant un champ suppplémentaire par nœud : sa couleur, qui peut valoir soit ROUGE, soir NOIR. En outre, un arbre rouge noir satisfait les propriétés suivantes : 1. Chaque nœud est soit rouge, soit noir. 2. Chaque feuille est noire. 3. Si un nœud est rouge, alors ses deux ﬁls sont noirs. 4. Pour chaque nœud de l’arbre, tous les chemins descendants vers des feuilles contiennent le même nombre de nœuds noirs. 5. La racine est noire. – Le premier arbre (a) n’a pas sa racine noir. – Dans le deuxième (b) le chemin vers la troisième feuille contient un seul nœuds noir feuille exclue, tandis qu’un chemin vers la première en contient 2 feuille exclue. – Le troisième arbre (c) est très joli avec de belles couleurs mais ce n’est pas un ABR donc pas un rouge noir (oui je sais c’est vache). – Le quatrième (d) a un nœud rouge dont un ﬁls est rouge. Correction de l’exercice 2. Oui. 30 15 10 N N 25 20 N N N 40 N 50 N N Figure 3: Coloriage corrigé Les arbres rouge noir Exercice 1 [Exemples de tas] Question 1. Les arbres 3, 6 et 7. Question 2. 9 7 1 4 9 7 4 1 9 4 1 7 Question 3. 16 14 8 2 4 7 1 11 10 9 3 16 14 8 2 4 11 1 7 10 9 3 Question 4. 16 1 8 2 4 7 10 9 3 16 8 1 2 4 7 10 9 3 16 8 2 1 4 7 10 9 3 Exercice 2 [Propriétés classiques des tas] Question 1. Un tas est un arbre complet donc un tas de hauteur h ne peut avoir des emplacements vides que sur la profondeur h. D’où 2h ≤n ≤2h+1 −1. Question 2. On déduit de l’inégalité précédente : n+1 2 ≤2h ≤n, puis log(n + 1) −1 ≤h ≤log(n). De l’inégalité de gauche, découle h ≥log(n) + log( n+1 n ) −1 > log(n) −1. h étant entier, h = ⌊log(n)⌋. Question 3. Soit B un sous-arbre d’un tas et c la valeur de sa clef. Supposons qu’il existe un nœud dont la valeur v est strictement plus grande que c. Soit v0 = c, . . . , vp = n les valeurs des clefs des nœuds en suivant la branche reliant ces deux nœuds. Par déﬁnition des tas, on a ∀i ∈{0, . . . , p −1}, vi ≥vi+1, ce qui contredit l’aﬃrmation précédente. 1 Tas Question 4. Si l’on considère une branche entre la racine r et une feuille f, il découle de la déﬁnition des tas et du fait que les clefs sont toutes distinctes que clef(r) > clef(f). Donc le plus petit élément est dans une feuille du tas. Réciproquement, il est clair que n’importe quelle feuille peut contenir le plus petit élément du tas. Exercice 4 [Représentation des tas en tableaux] Question 1. Les ﬁls du nœud i sont les nœuds 2i + 1 (ﬁls gauche) et 2i + 2 (ﬁls droit). Le père du nœud i est le nœud ⌊i−1 2 ⌋. Question 2. Oui : 23 17 6 1 5 13 7 12 14 10 1 Question 3. ∀i ∈{1, . . . , n −1}, T[i] ≤T[⌊i −1 2 ⌋] uploads/S4/ sda-td5-arbres-equilibres-corrige.pdf