TD — Séance 4 — Arbres et tas

ABR, suppression, hauteur, AVL et tas binaire

TD de la séance 4 de Structures de données et algorithmes avancés : chercher en O(log n) et toujours extraire le minimum.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Appliquer à la main, sur des données nouvelles, les mécanismes du cours : insertion, recherche, suppression et parcours dans un arbre binaire de recherche, hauteur selon l’ordre d’insertion, rotations d’un arbre AVL, indices et percolations d’un tas binaire. Chaque réponse se donne sous la forme demandée (tableau, arbre, nombre de comparaisons ou d’échanges) et se justifie en une ou deux phrases.

Conventions. Les clés sont des entiers distincts. Une recherche ou une insertion dans un ABR compte une comparaison par nœud examiné. La suppression d’un nœud à deux enfants utilise le successeur infixe. Un arbre s’écrit clé(gauche,droite), - désignant un sous-arbre vide et une feuille s’écrivant par sa seule clé ; la hauteur de l’arbre vide vaut \(-1\), celle d’une feuille 0, et \(\mathrm{bf}(x)=h(\mathrm{gauche}(x))-h(\mathrm{droite}(x))\). Le tas est un tas min rangé dans un tableau indexé à partir de 0 ; insert range la clé en queue puis l’échange avec son parent tant qu’elle lui est strictement inférieure ; extractMin range le dernier élément à la racine, puis l’échange avec le plus petit de ses enfants tant qu’il lui est strictement supérieur.

Exercice 1 : un ABR de dix clés

On insère dans un ABR vide, dans cet ordre, les clés 63, 28, 81, 14, 45, 70, 92, 37, 52, 75.

  1. Compléter le tableau : pour chaque clé, le chemin des nœuds comparés, la profondeur d’arrivée et le nombre de comparaisons.
  2. Dessiner l’arbre obtenu, l’écrire sous la forme clé(gauche,droite), et donner sa hauteur et le nombre total de comparaisons des dix insertions.
  3. Pour get(52), get(40) et get(99), donner les nœuds examinés, le nombre de comparaisons et le résultat.
  4. Donner les parcours infixe, préfixe et postfixe de l’arbre.
  5. On appelle cles(30, 72), qui descend à gauche d’un nœud seulement si \(30<\) clé et à droite seulement si clé \(<72\). Donner les nœuds visités, dans l’ordre, et la liste rendue.
clé chemin (nœuds comparés) profondeur comparaisons
63
28
81
14
45
70
92
37
52
75

Exercice 2 : trois suppressions

On part de l’arbre de l’exercice 1 et l’on supprime, dans cet ordre, 14, puis 28, puis 63.

  1. Pour chaque suppression, nommer le cas (feuille, un enfant, deux enfants), donner le nœud qui prend la place de la clé supprimée (s’il y en a un), l’arbre obtenu et sa hauteur.
  2. Pour la suppression de 63, donner le chemin suivi pour trouver le successeur, et le cas de la suppression du successeur lui-même.
  3. Expliquer pourquoi le successeur infixe d’un nœud à deux enfants n’a jamais d’enfant gauche.
  4. Donner le parcours infixe de l’arbre final et vérifier qu’il est trié.
clé cas remplacée par arbre obtenu hauteur
14
28
63

Exercice 3 : la hauteur selon l’ordre d’insertion

  1. Avec les clés 1 à 7, donner un ordre d’insertion qui produit un ABR de hauteur 2, et un ordre qui produit un ABR de hauteur 6.
  2. Compléter le tableau des six ordres d’insertion des clés 1, 2, 3. Si les six ordres sont équiprobables, quelle est la probabilité d’obtenir un arbre de hauteur 1 ?
  3. Pour \(n=1\,023\) clés, donner la plus petite et la plus grande hauteur possibles, et le nombre de comparaisons d’une recherche réussie au pire dans chacun des deux arbres.
  4. Pour \(n=2\,500\) clés insérées dans un ordre aléatoire, calculer le coût moyen d’une recherche réussie \(C_n=2(1+1/n)H_n-3\), avec \(H_{2\,500}=8{,}4015\). Le comparer à la hauteur minimale.
ordre 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1
hauteur

Exercice 4 : les quatre cas dans un AVL

On insère dans un AVL vide, dans cet ordre, les clés 44, 29, 17, 58, 66, 51, 23.

  1. Compléter le tableau : pour chaque insertion, le premier nœud déséquilibré rencontré en remontant (s’il y en a un), son facteur d’équilibre, le cas (LL, RR, LR, RL), la ou les rotations, et l’arbre après rééquilibrage.
  2. Donner l’arbre final, sa hauteur, les facteurs d’équilibre de ses nœuds et le nombre total de rotations.
  3. Quelle serait la hauteur d’un ABR non équilibré construit par les mêmes insertions ?
clé nœud bf cas rotation(s) arbre après
44
29
17
58
66
51
23

Exercice 5 : indices dans un tas

  1. Un tas est rangé dans un tableau de \(n=13\) cases. Donner le parent et les enfants de la case 5, les cases des feuilles et la hauteur du tas.
  2. Les deux tableaux suivants sont-ils des tas min ? Pour chacun, dessiner l’arbre et donner toutes les cases dont la clé est plus petite que celle de leur parent. \[A=[3, 7, 5, 9, 8, 6, 12, 11, 10]\qquad B=[3, 7, 5, 9, 6, 4, 12, 11, 10]\]

Exercice 6 : percolations

  1. On insère dans un tas vide, dans cet ordre, les clés 8, 3, 10, 1, 6, 14, 4, 7. Compléter le tableau.
  2. On appelle ensuite deux fois extractMin(). Pour chaque appel, donner la valeur rendue, le tableau après chaque échange, le nombre d’échanges et le nombre de comparaisons (deux par niveau descendu s’il y a deux enfants, une s’il n’y en a qu’un).
  3. Si l’on poursuit les extractions jusqu’à vider le tas, dans quel ordre les clés sortent-elles ? Quel est le coût de ce tri pour \(n\) clés ?
clé insérée 0 1 2 3 4 5 6 7 échanges
8
3
10
1
6
14
4
7

Exercice 7 : hauteur maximale d’un AVL et pièges

  1. Soit \(N_h\) le plus petit nombre de nœuds d’un AVL de hauteur \(h\). Justifier \(N_h=N_{h-1}+N_{h-2}+1\), calculer \(N_0\) à \(N_7\), et en déduire la plus grande hauteur possible d’un AVL de 20 clés. La comparer à la borne \(1{,}44\log_2(n+2)-0{,}328\) (aide : \(\log_2 22=4{,}459\)).

  2. Vrai ou faux ? Justifier chaque réponse en une ou deux lignes, par un argument ou un contre-exemple.

    1. Dans un tas min de clés distinctes, la deuxième plus petite clé est en case 1 ou en case 2.
    2. Le parcours infixe d’un tas min sort ses clés triées.
    3. Une insertion dans un AVL provoque au plus deux rotations.
    4. La plus grande clé d’un tas min de \(n\) clés est dans l’une des cases \(\lfloor n/2\rfloor\) à \(n-1\).
    5. Un ABR dont chaque nœud a 0 ou 2 enfants a une hauteur en \(\mathcal{O}(\log n)\).

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet