Skip to content

Séquence 5

L'objectif de la séquence est de travailler sur la construction et l'utilisation d'arbres binaires de recherche. On poura lire le chapitre 12 de l'ouvrage

Algorithmique par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein Dunod 3ième édition 2010 lien des versions plus anciennes sont accessibles partiellement sur internet.

Question 1

On considère l'arbre de 13 noeuds étiquetés, de racine le noeud 1

noeud étiquette fils gauche fils droit
1 I 2 3
2 F 4 5
3 M 6 7
4 C 8 9
5 G 10 /
6 K / /
7 P 11 12
8 A / /
9 D / /
10 H / /
11 L / /
12 W 13 /
13 U / /

Pour chacun des noeuds \(i\) de l'arbre, indiquer si le sous-arbre de racine \(i\) est un arbre binaire de recherche.

réponses (éléments)

Les sous-arbres dont les racines sont les noeuds \(i=4,8,9,10,6,7,11,12,13\) sont des arbres binaires de recherche, les autres sous-rbres ne le sont pas.

Question 2

On considère un ABR avec \(n\) noeuds et de hauteur \(h\).

  1. La recherche d'un élément dans l'ABR est de complexité au pire \(O(1)\), \(O(log n)\), \(O(h)\), \(O(n)\)
  2. La recherche d'un élément dans l'ABR construit par insertion des éléments dans un ordre aléatoire est de complexité moyenne \(O(1)\), \(O(log n)\), \(O(h)\), \(O(n)\)

réponses (éléments)

  1. Les réponses \(O(h)\) et \(O(n)\) sont correctes, la plus précise est \(O(h)\), en effet il existe une feuille à la hauteur \(h\) et pour la retrouver il faut de l'ordre de \(O(h)\) comparaisons, tous les autres noeuds étant à une distance inférieure ou égale à \(h\). Comme on peut construire un ABR dégénéré de taille \(n\) (un fil) on a \(h=n-1)\) et donc la complexité sera en \(O(n)\) au pire
  2. Lorsque l'ABR est construit en insérant les clés dans un ordre aléatoire, on montre que la hauteur moyenne d'un noeud est \(O(\log n)\), les bonnes réponses sont \(O(\log n)\) et \(O(h)\) (comme avant)

Question 3

Étant donné un ABR, quel parcours permet de traiter les noeuds par ordre croissant de leurs étiquettes

  1. un parcours en largeur d'abord
  2. un parcours en profondeur d'abord préfixé
  3. un parcours en profondeur d'abord infixé
  4. un parcours en profondeur d'abord post-fixé

réponses (éléments)

La bonne réponse est le parcours en profondeur d'abord infixé, on doit traiter les noeuds par ordre d'étiquette donc les noeuds du sous-arbres gauche doivent être traités avant le traitement de la racine qui elle-même doit être traitée avant les noeuds du sous-arbre droit.

Question 4

On considère l'arbre binaire de recherche de 9 noeuds étiquetés, de racine le noeud 1

noeud étiquette fils gauche fils droit
1 I 2 7
2 F 8 /
3 T / /
4 C / /
5 J / 4
6 U / /
7 B 5 3
8 E 6 9
9 S / /
  1. On souhaite insérer un nouveau noeud portant l'étiquette D, à quelle place faut-il l'insérer ?
  2. On souhaite maintent supprimer le noeud 2, quel noeud sera la racine du sous-arbre gauche du noeud 1 après suppression.

réponses (éléments)

  1. Il faut l'insérer comme racine du sous-arbre gauche du noeud 9
  2. Le noeud 8