next up previous
suivant: À propos de ce

Exercice 8.1  Arbres binaires de recherche.

\begin{figure}\begin{center}
\epsfig{file=ABR.eps,width=6cm}
\end{center}\end{figure}

  1. Ajouter successivement à l'arbre binaire dessiné ci-dessus les valeurs: $ 9,15,16,7,23,5$
  2. Dessiner tous les arbres binaires de recherche valués sur $ V=\{10,20,30,40\}$ ayant 20 comme valeur à la racine.
  3. Donner le mot infixe obtenu en écrivant les valeurs des sommets dans l'ordre de parcours infixe.
  4. Ecrire une fonction d'ajout d'une valeur $ n$ à un arbre binaire de recherche.
  5. Ecrire deux fonctions qui retournent respectivement la plus petite et le plus grande valeur contenue dans un arbre binaire de recherche. Ecrire les fonctions qui suppriment ces deux éléments
  6. Ecrire une fonction de recherche d'un élément donné dans un arbre binaire de recherche.
  7. Ecrire une fonction qui vérifie si un arbre binaire est un arbre binaire de recherche.

Exercice 8.2 Bricolage

Dans une boite à outils, vous disposez de $ n$ écrous de diamètres tous différents et des $ n$ boulons correspondants. Mais tout est mélangé et vous voulez apparier chaque écrou avec le boulon qui lui correspond. Les différences de diamètre entre les écrous sont tellement minimes qu'il n'est pas possible de d´eterminer à l'oeil nu si un écrou est plus grand qu'un autre. Il en va de même avec les boulons. Par conséquent, le seul type d'opération autorisée consiste à essayer un écrou avec un boulon, ce qui peut amener trois réponses possibles : soit l'écrou est strictement plus large que le boulon, soit il est strictement moins large, soit ils ont exactement le même diamètre.

  1. Ecrire un algorithme simple en O(n2) essais qui appareille chaque écrou avec son boulon.
  2. Supposons qu'au lieu de vouloir appareiller tous les boulons et écrous, vous voulez juste trouver le plus petit écrou et le boulon correspondant. Montrer que vous pouvez résoudre ce problème en moins de $ 2n - 2$ essais.




next up previous
suivant: À propos de ce
Maylis Delest 2007-11-12