\documentclass[11pt]{article}

\usepackage{amsmath,amssymb,fancybox,fancyhdr,lastpage,a4,mdwlist,multicol}

\usepackage[french]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{tikz}
\usepackage{tikz,tkz-tab,tkz-fct}
\usepackage[algoruled,french,onelanguage,linesnumbered]{algorithm2e}
\usepackage{mdwlist}
\topmargin-0.5cm
\headheight20pt
\textheight23cm
\textwidth17.5cm
\oddsidemargin-1cm
\evensidemargin0cm
\parindent0pt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts,graphicx,fancybox,fancyhdr,lastpage}

\usepackage{boxedminipage}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.50.0.2953}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Created=Monday, October 27, 2014 10:00:28}
%TCIDATA{LastRevised=Sunday, February 12, 2017 08:45:02}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Style Editor\POLY">}
%TCIDATA{CSTFile=POLY.cst}

\input{tcilatex}
\begin{document}

%\SetTitle{Th\`{e}me info 1 -- Arbres binaires et tri par tas}
%\SetAuthor{}
%\Setdate{}
%\TitlePage{}

%~\vspace{-1.1cm}

\pagestyle{fancy}
\lhead{{\bf MP}}
\chead{} 
\rhead{TP : arbres binaires}
\lfoot{\sl Lyc\'ee Chateaubriand}
\cfoot{}
\rfoot{\thepage/\pageref{LastPage}}

\renewcommand{\footrulewidth}{0.4pt}

\section{Structure d'arbre binaire - repr\'{e}sentations par une liste}


%\subsection{Les primitives du type abstrait de donn\'{e}es \textquotedblleft
%arbre binaire\textquotedblright}
%
%Les primitives permettant de cr\'{e}er et de manipuler (souvent r\'{e}%
%cursivement) les arbres binaires sont~:
%
%\begin{itemize}
%\item \texttt{est\_vide(a)}~: renvoie \texttt{Vrai} si l'arbre \texttt{a}
%est vide, \texttt{Faux} sinon~;
%
%\item \texttt{arbre\_vide()}~: renvoie l'arbre vide~;
%
%\item \texttt{cons(e,g,d)}~: renvoie l'arbre d'\'{e}tiquette \texttt{e}, de
%fils gauche (\emph{resp.} droit) \texttt{g} (\emph{resp.} \texttt{d})~;
%
%\item \texttt{contenu(a)}~: renvoie l'\'{e}tiquette de l'arbre \textbf{non
%vide} \texttt{a}~;
%
%\item \texttt{f\_g(a)} (\emph{resp.} \texttt{f\_d(a)})~: renvoie le fils
%gauche (\emph{resp.} droit) de l'arbre \textbf{non vide} \texttt{a}.\vspace{%
%-0.3cm}
%\end{itemize}



\textbf{Question 1~: }\'{e}crire en Python les primitives ci-dessous 
dans cette repr\'{e}sentation.\vspace{0.2cm}
\begin{itemize}
\item \texttt{est\_vide(a)}~: renvoie \texttt{Vrai} si l'arbre \texttt{a}
est vide, \texttt{Faux} sinon~;

\item \texttt{arbre\_vide()}~: renvoie l'arbre vide~;

\item \texttt{cons(e,g,d)}~: renvoie l'arbre d'\'{e}tiquette \texttt{e}, de
fils gauche (\emph{resp.} droit) \texttt{g} (\emph{resp.} \texttt{d})~;

\item \texttt{contenu(a)}~: renvoie l'\'{e}tiquette de l'arbre \textbf{non
vide} \texttt{a}~;

\item \texttt{f\_g(a)} (\emph{resp.} \texttt{f\_d(a)})~: renvoie le fils
gauche (\emph{resp.} droit) de l'arbre \textbf{non vide} \texttt{a}.
\end{itemize}

\vspace{.3cm}

\textbf{Question 2~: }programmer (r\'{e}cursivement~!) dans ce contexte le
calcul de la hauteur d'un arbre.\vspace{0.2cm}

\textbf{Question 3~: }l'arbre suivant repr\'{e}sente graphiquement une
expression alg\'{e}brique.\vspace{0.1cm}%
\[
\includegraphics[scale=1]{expr.eps}
\]%
Programmer le \emph{parcours} (r\'{e}cursif~!) d'un tel arbre pour \'{e}%
crire dans une cha\^{\i}ne de caract\`{e}res l'expression alg\'{e}brique
associ\'{e}e. Il sera sage d'ajouter des parenth\`{e}ses. Tester le programme avec l'exemple ci-dessus.


{\bf Remarque}
\begin{itemize}
\item l'op\'{e}ration inverse consistant \`{a} reconstruire l'arbre \`{a}
partir de la cha\^{\i}ne de caract\`{e}res est plus d\'{e}licate.
\end{itemize}


\section{Tri par tas (\emph{heapsort} en anglais)\protect\vspace{-0.3cm}}

Nous avons vu en cours la notion de tas.
Nous allons voir que l'impl\'{e}mentation se fait tr\`{e}s bien avec les
tableaux (et de fa\c{c}on \textbf{it\'{e}rative}\ldots ), mais la vision
arborescente est fondamentale pour imaginer et visualiser les algorithmes. Penser donc à utiliser la fonction {\tt afficher} pour tester les fonctions.

Pour la suite, on suppose donn\'{e} un tableau initial $ti$ contenant les $n$
valeurs \`{a} trier. Pour stocker $n$ valeurs dans un tas, on utilisera un
tableau de taille $n+1$, les cases \textquotedblleft
utiles\textquotedblright\ \'{e}tant index\'{e}es de 1 \`{a} $n$ comme expliqu%
\'{e} en cours.

\subsection{Tri par tas, premi\`{e}re version}

La version la plus naturelle consiste \`{a} utiliser un tableau auxilaire $%
tas$ que l'on remplira avec les donn\'{e}es initiales, avant de le vider.%
\vspace{0.2cm}

\textbf{Question 4}~: \'{e}crire une proc\'{e}dure $entasser$, recevant pour
param\`{e}tres un tas $t$ et une valeur $x$ et ajoutant $x$ dans $t$ en pr%
\'{e}servant la structure de tas. On pourra ajouter $x$ \`{a} la fin du tas
et le faire \textquotedblleft remonter vers la racine\textquotedblright\ par 
\'{e}changes successifs $fils\leftrightarrow p\grave{e}re$ autant que n\'{e}%
cessaire (cf. l'id\'{e}e du tri par insertion\ldots ).\vspace{0.2cm}

\textbf{Question 5}~: \'{e}crire une proc\'{e}dure $suppr\_min$, recevant
pour param\`{e}tres un tas $t$ et supprimant de $t$ sa racine en pr\'{e}%
servant la structure de tas. On pourra remplacer la racine par la derni\`{e}%
re valeur de $t$, supprimer cette derni\`{e}re valeur et faire
\textquotedblleft redescendre\textquotedblright\ cette nouvelle racine dans
le tas \`{a} l'aide d'\'{e}changes $p\grave{e}re\leftrightarrow fils$
(attention \`{a} choisir le bon fils lorsqu'il y en a deux\ldots ).\vspace{%
0.2cm}

\textbf{Question 6~}: d\'{e}duire des deux questions pr\'{e}c\'{e}dentes une
fonction $tri\_tas1$, recevant pour param\`{e}tre le tableau initial $ti$ et
le renvoyant tri\'{e}. Seules les valeurs index\'{e}es \`{a} partir de 1
seront tri\'{e}es.

\subsection{Tri par tas en place}

\textbf{Question 7}~: modifier les programmes des questions \textbf{4}, 
\textbf{5}, \textbf{6} afin d'obtenir une fonction $tri\_tas2$ triant
\textquotedblleft en place\textquotedblright\ le tableau re\c{c}u en param%
\`{e}tre (\emph{i.e.} sans utiliser de tableau auxiliaire). L\`{a} encore,
seules les valeurs index\'{e}es \`{a} partir de 1 seront tri\'{e}es, mais on pourra utiliser {\tt t[0]} pour stocker le nombre d'éléments considérés dans le tas (différent de la taille du tableau qui sera constante cette fois).

\subsection{Optimisation de la cr\'{e}ation du tas}

Si l'on s'y prend bien, la complexit\'{e} de la fonction $entasser$ de la
question \textbf{4} est major\'{e}e par $\log _{2}i$, o\`{u} $i$ est le
nombre de valeurs dans le tas initial. Il en r\'{e}sulte une cr\'{e}ation
progressive du tas contenant les $n$ valeurs avec une complexit\'{e} major%
\'{e}e par $\log _{2}\left( n!\right) $, soit un $O\left( n\ln n\right) $ gr%
\^{a}ce \`{a} la formule de Stirling. En fait cette cr\'{e}ation du tas peut
se faire avec une complexit\'{e} lin\'{e}aire.\vspace{0.2cm}

Pour cela, on part du tableau $t$ contenant les valeurs \`{a} trier
(initialement dans un ordre quelconque) dans les cases index\'{e}es de 1 
\`{a} $n$, on pose $d=\left\lfloor n/2\right\rfloor $, indice du n\oe ud le
plus \`{a} droite de l'avant-dernier niveau du tas. L'id\'{e}e est
d'ordonner successivement les sous-arbres dont les racines sont les n\oe uds
d'indices $d,d-1,\ldots ,1$.\vspace{0.2cm}

Pour ce faire on \'{e}crit une fonction $ordonner(t,r)$ qui traite le
sous-arbre dont la racine a pour indice $r$, en supposant que les
sous-arbres de ce dernier ont d\'{e}j\`{a} \'{e}t\'{e} trait\'{e}s (ce qui
justifiera une preuve par r\'{e}currence descendante~!). Le traitement se d%
\'{e}roule ainsi~:

\begin{itemize}
\item on recherche l'indice $f$ du plus petit fils de $t\left[ r\right] $

\item si besoin on \'{e}change $t\left[ r\right] $ et $t\left[ f\right] $ et
dans ce cas, si $t\left[ f\right] $ n'est pas une feuille, on appelle (r\'{e}%
cursivement) $ordonner\left( t,f\right) $ puisque le sous-arbre de racine $t%
\left[ f\right] $ n'est peut-\^{e}tre plus un tas\ldots
\end{itemize}

Voici un exemple \`{a} partir du tableau $t=\left[ 0,14,9,8,4,10,7\right] $ o%
\`{u} l'on appelle successivement $ordonner$ avec $r=3,2,1$ (on a fait
figurer son num\'{e}ro \`{a} gauche de chaque n\oe ud)~:\vspace{-0.1cm}%
\[
\begin{tabular}{ccc}
\includegraphics[scale=1]{ord1.eps} & \includegraphics[scale=1]{ord2.eps} & \includegraphics[scale=1]{ord3.eps} \\ 
\'{e}tat initial & \'{e}tape 1~: $r=3$ & \'{e}tape 2~: $r=2$\vspace{0.2cm}
\\ 
\includegraphics[scale=1]{ord4.eps} & \includegraphics[scale=1]{ord5.eps} & \includegraphics[scale=1]{ord6.eps} \\ 
\'{e}tape 3~: $r=1$ & appel r\'{e}cursif~: $f=2$ & \'{e}tat final%
\end{tabular}%
\]%
%\vspace{0.5cm}

\textbf{Question 8}~: programmer la fonction $ordonner$ et l'utiliser pour 
\'{e}crire une fonction $tri\_tas3$.\vspace{0.2cm}

\textbf{Question 9} (facultative)~: montrer que la complexit\'{e} de la cr%
\'{e}ation du tas \`{a} l'aide de la fonction $ordonner$ est un $O\left(
n\right) $.

\section{Tri par arbres binaires de recherche - programmation objet}
Un {\it arbre binaire de recherche}, est un arbre binaire tel que l'étiquette de tout n\oe ud est :
\begin{itemize}
\item supérieure à toutes les étiquettes du sous-arbre gauche ;
\item inférieure à toutes les étiquettes du sous-arbre droit.
\end{itemize}

Dans cette partie, on propose d'implémenter une classe {\tt Abr}.

Les attributs de cette classe sont :
\begin{itemize}
\item {\tt vide} : un booléen indiquant si l'arbre est vide ;
\item {\tt gauche} : {\tt None} ou un {\tt Abr} qui code le sous-arbre gauche ;
\item {\tt droite} : {\tt None} ou un {\tt Abr} qui code le sous-arbre droite ;
\item {\tt e} : un {\tt int} qui code l'étiquette de la racine de l'arbre.
\end{itemize}

\`A sa création, un {\tt Abr} est vide, ses sous-arbres ne sont pas créés et l'étiquette de la racine (inexistante) a une valeur nulle par défaut.
\begin{verbatim}
class Abr:
    def __init__(self):
        self.vide = True
        self.gauche = None
        self.droite = None
        self.e = 0
\end{verbatim}

La commande {\tt a = Abr()} crée un arbre vide.
Pour accéder aux attributs d'un arbre {\tt a} donné, on écrit {\tt a.nom$\_$attribut}.
Pour définir les {\it méthodes} de la classe {\tt Abr}, on définit des fonctions comme d'habitude, indentées d'un cran pour signifier l'appartenance à la classe. Le premier paramètre dans la définition est toujours {\tt self}, mais il n'est pas utilisé dans les appels dont la syntaxe est {\tt a.methode(arg2,arg3,...)}.
\vspace{.5cm}

\textbf{Question 10}~: écrire une méthode dont l'entête est {\tt def ajoute(self,x):} qui ajoute l'élément {\tt x} dans l'arbre (s'il n'y est pas déjà présent) en maintenant la structure d'arbre binaire de recherche.\vspace{.2cm}

\textbf{Question 11}~: écrire une méthode dont l'entête est {\tt def recherche(self,x):} qui renvoie un booléen indiquant si {\tt x} est une étiquette de l'arbre.\vspace{.2cm}

\textbf{Question 12}~: écrire une méthode dont l'en-tête est {\tt def hauteur(self):} qui renvoie la hauteur de  l'arbre (un arbre vide étant de hauteur.\vspace{.2cm}

\textbf{Question 13}~: écrire une méthode dont l'entête est {\tt def affiche(self):} qui va construire un tableau représentant l'arbre puis utiliser la fonction d'affichage définie en cours pour afficher l'arbre. (Ne pas hésiter à définir des méthodes auxiliaires)\vspace{.2cm}

\textbf{Question 14}~: écrire une méthode dont l'en-tête est {\tt def taille(self):} qui renvoie le nombre de n\oe uds dans l'arbre.\vspace{.2cm}

\textbf{Question 15}~: écrire une méthode dont l'en-tête est {\tt def tri(self):} qui renvoie un tableau contenant l'ensemble des étiquettes de l'arbre dans l'ordre croissant (il suffit de faire un parcours infixe).\vspace{.2cm}


\textbf{Question 16}~: Estimer la complexité du tri par arbre binaire de recherche en fonction de la hauteur de l'arbre. Que peut-on en conclure ?\vspace{.2cm}

\textbf{Question 17 (subsidiaire)}~: écrire une méthode dont l'en-tête est {\tt def supprime(self,x):} qui supprime l'élément {\tt x} dans l'arbre (s'il y est présent) en maintenant la structure d'arbre binaire de recherche. Cette question est difficile et nécessite la définition de méthodes auxiliaires.



\end{document}