\documentclass[11pt]{article}

\usepackage{fullpage,french,epsf,fancyheadings}

\pagestyle{fancy}
\lhead{Arbres binaires de recherche}
\rhead{Jean-Christophe Filliâtre}

\begin{document}

\begin{center}
  \LARGE\bf Arbres binaires de recherche
\end{center}
\bigskip

Les arbres binaires de recherche constituent un moyen courant de stockage et 
de recherche (pour représenter des dictionnaires par exemple). Les algorithmes
impliqués sont très classiques et se retrouvent dans de nombreuses situations
(parcours d'un arbre, 

On définit un arbre comme étant soit une feuille (vide), soit un n\oe ud
constitué d'une information (par exemple une chaîne de caractères) et de deux 
sous-arbres, c'est-à-dire le type \textsc{Caml} suivant :

\begin{verbatim}
     type 'a arbre = Feuille
                   | Noeud   of 'a arbre * 'a * 'a arbre
\end{verbatim}

\noindent où \texttt{'a} est le type de l'information. La propriété d'un
arbre binaire de recherche est la suivante : \emph{pour chaque n\oe ud
$(g,i,d)$, les informations contenues dans le sous-arbre gauche $g$
sont inférieures (ou égales) à $i$, les informations contenues dans
le sous-arbre droit $d$ supérieures (ou égales) à $i$}.

Par exemple, l'arbre suivant est un arbre binaire de recherche :

\bigskip
%\epsfxsize=10cm%
\hfil\epsfbox{arbre-binaire.eps}\hfil


On se propose d'écrire les principales fonctions de manipulation des arbres
binaires de recherche, à savoir \emph{la recherche}, \emph{l'insertion}
et \emph{la suppression} dans un arbre binaire.


\section{Recherche}

Ecrire une fonction \verb!recherche : 'a arbre -> 'a -> bool! testant 
la présence d'un élément dans un arbre binaire de recherche.

Quelle est sa complexité en fonction de la taille $N$ de l'arbre (nombre
de n\oe uds de l'arbre) ? Distinguer les cas en moyenne et au pire.
A quel type d'arbre correspond la complexité la plus médiocre ?

\section{Insertion}

Ecrire une fonction \verb!insertion : 'a arbre -> 'a -> 'a arbre! réalisant
l'insertion d'un nouvel élément dans un arbre binaire de recherche. Quelle
est la complexité de cette opération ? 

En déduire une fonction \verb!construit : 'a list -> 'a arbre!
construisant un arbre binaire de recherche à partir d'une liste
d'éléments.

\section{Parcours}

Ecrire une fonction \verb!parcours : 'a arbre -> 'a list! prenant un
arbre binaire de recherche en argument et renvoyant la liste
\emph{triée} de ses éléments.  Un tel parcours s'appelle
\emph{parcours préfixe} d'un arbre.

\section{Suppression}

Ecrire une fonction \verb!suppression : 'a arbre -> 'a -> 'a arbre!
supprimant un élément dans un arbre binaire de recherche. Quelle
est la complexité de cette opération ? 

\end{document}