\documentclass[11pt]{article}

\usepackage{amsmath,stmaryrd,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}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.50.0.2953}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Created=Thursday, September 11, 2014 16:21:49}
%TCIDATA{LastRevised=Thursday, November 29, 2018 07:17:55}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Style Editor\CORRIGE">}
%TCIDATA{CSTFile=CORRIGE.cst}

\input{tcilatex}
\begin{document}

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

\renewcommand{\footrulewidth}{0.4pt}
%\SetTitle{PSI* -- 2018/2019 -- Informatique -- Corrig\'{e} du Th\`{e}me 1}
%\SetAuthor{}
%\Setdate{}
%\TitlePage{}
%
%~\vspace{-1cm}




\textbf{Question 1}\vspace{0.2cm}

Pas de difficult\'{e} avec les listes Python~!

\setlength{\columnseprule}{0.5pt} \setlength{\multicolsep}{5pt} 
\begin{multicols}{2}
\begin{verbatim}
def est_vide(a):
    return a==[]

def arbre_vide():
    return []

def cons(e,g,d):
    return [e,g,d]
\end{verbatim}
\vfill
\columnbreak
\begin{verbatim}
def contenu(a):
    return a[0]

def f_g(a):
    return a[1]

def f_d(a):
    return a[2]
\end{verbatim}
\vfill
\end{multicols}\vspace{0.2cm}

\textbf{Question 2}\vspace{0.2cm}

Comme il est plus facile de tester si un arbre est vide que de tester s'il
contient un unique n\oe ud, on convient que la hauteur de l'arbre vide est $%
-1$, ce qui permet d'\'{e}tendre au cas de l'arbre vide la relation%
\begin{equation*}
h\left( a\right) =1+\max \left( h\left( fils\_g\left( a\right) \right)
,h\left( fils\_d\left( a\right) \right) \strut \right) .
\end{equation*}%
Cette relation se pr\^{e}te \'{e}videmment \`{a} une programmation r\'{e}%
cursive~:\vspace{0.2cm}

\begin{boxedminipage}{11cm}
\begin{verbatim}
def hauteur(a):
    if est_vide(a):
        return -1
    else:
        return 1+max(hauteur(f_d(a)),hauteur(f_g(a)))
\end{verbatim}
\end{boxedminipage}\vspace{0.2cm}


J'utilise la fonction \texttt{max} de Python. Terminaison justifi\'{e}e par
la d\'{e}croissance stricte de la hauteur de l'arbre en param\`{e}tre \`{a}
chaque appel r\'{e}cursif et preuve par r\'{e}currence sur ladite hauteur~!%
\vspace{0.2cm}

\textbf{Question 3}\vspace{0.2cm}

Je construis r\'{e}cursivement la cha\^{\i}ne de caract\`{e}res souhait\'{e}%
e~:

\begin{itemize}
\item si l'arbre est vide, je renvoie la cha\^{\i}ne vide

\item si l'arbre est une feuille (deux fils vides), je renvoie la cha\^{\i}%
ne repr\'{e}sentant le nombre en \'{e}tiquette (conversion avec \texttt{str})

\item sinon, l'\'{e}tiquette est un op\'{e}rateur, je renvoie donc une
parenth\`{e}se, suivie de la cha\^{\i}ne associ\'{e}e au sous-arbre gauche
(premier op\'{e}rande), de l'\'{e}tiquette puis de la cha\^{\i}ne associ\'{e}%
e au sous-arbre droit (second op\'{e}rande).
\end{itemize}

D'o\`{u} le programme~:\vspace{0.2cm}

\begin{boxedminipage}{16.7cm}
\begin{verbatim}
def parcours_infixe(a):
    if est_vide(a):
        return ''
    elif est_vide(f_g(a)) and est_vide(f_d(a)):
        return str(contenu(a))
    else:
        return '('+parcours_infixe(f_g(a))+contenu(a)+parcours_infixe(f_d(a))+')'
\end{verbatim}
\end{boxedminipage}\vspace{0.2cm}

\textbf{N.B.}~: la d\'{e}nomination \textquotedblleft \emph{parcours infixe}%
\textquotedblright\ vient du fait que l'\'{e}tiquette est \'{e}crite \textbf{%
entre} les cha\^{\i}nes correspondant aux sous-arbres. Le r\'{e}sultat pour
l'arbre de l'\'{e}nonc\'{e} est 
\begin{equation*}
\fbox{\texttt{((3+(5x(7+2)))-(4+(8x9)))}}
\end{equation*}%
On peut de m\^{e}me programmer r\'{e}cursivement un parcours \emph{pr\'{e}%
fixe }(avec l'op\'{e}rateur avant les op\'{e}randes, comme dans le langage
Lisp, ou comme $f\left( x,y\right) $ en maths~!) ou un parcours \emph{%
postfixe} (avec l'op\'{e}rateur apr\`{e}s les op\'{e}randes, comme dans la 
\emph{notation polonaise inverse}, cf. le chapitre 3). Ainsi, le programme
suivant~:\vspace{0.2cm}

\begin{boxedminipage}{17.5cm}
\begin{verbatim}
def parcours_postfixe(a):
    if est_vide(a):
        return ''
    elif est_vide(f_g(a)) and est_vide(f_d(a)):
        return str(contenu(a))
    else:
        return parcours_postfixe(f_g(a))+' '+parcours_postfixe(f_d(a))+' '+contenu(a)
\end{verbatim}
\end{boxedminipage}\vspace{0.2cm}

donne pour l'arbre de l'\'{e}nonc\'{e} la cha\^{\i}ne suivante~: \texttt{3 5
7 2 + x + 4 8 9 x + -}\vspace{0.2cm}

Avec cette notation les parenth\`{e}ses ne sont pas n\'{e}cessaires, un
espace suffit pour s\'{e}parer deux symboles.\vspace{0.5cm}

\textbf{Question 4}\vspace{0.2cm}

J'applique l'indication de l'\'{e}nonc\'{e}~:

\begin{itemize}
\item j'ajoute l'\'{e}l\'{e}ment $x$ \`{a} la fin de $t$ (m\'{e}thode 
\texttt{append})~; $x$ se trouve alors dans $t\left[ i\right] $ o\`{u} $i$
vaut $len(t)-1$ (rappelons que $t\left[ 0\right] $ n'est pas utilis\'{e})

\item tant que $t\left[ i\right] $ a un p\`{e}re (condition $i>1$) et est
plus petit que son p\`{e}re $t\left[ p\right] $ (o\`{u} $p=i//2$), j'\'{e}%
change $t[i]$ et $t\left[ p\right] $ et j'actualise les valeurs de $i$ et de 
$p$\vspace{0.2cm}
\end{itemize}

D'o\`{u} le programme~:\vspace{0.2cm}

\begin{boxedminipage}{10.2cm}
\begin{verbatim}
def entasser(x,t):
    t.append(x)
    i=len(t)-1 #l indice de cette derniere valeur
    p=i//2 #le pere
    while i>1 and t[i]<t[p]:
        t[i],t[p]=t[p],t[i]
        i,p=p,p//2
\end{verbatim}
\end{boxedminipage}\vspace{0.2cm}

\textbf{Question 5}\vspace{0.2cm}

Selon l'indication de l'\'{e}nonc\'{e}, je commence par remplacer la racine $%
t\left[ 1\right] $ par la derni\`{e}re valeur $t\left[ -1\right] $, puis je
supprime cette derni\`{e}re valeur (m\'{e}thode \texttt{pop}). Ainsi la
valeur minimum (racine initiale) a disparu, mais $t$ n'est \emph{a priori }%
plus un tas, il faut faire \textquotedblleft redescendre\textquotedblright\
la nouvelle racine en pr\'{e}servant la structure de tas. Pour cela, il est
clair qu'il suffit d'\'{e}changer cette valeur $t\left[ i\right] $ avec le
plus petit de ses deux fils (ou avec son fils si elle n'en a qu'un, cas $%
2i=n $), not\'{e} $t\left[ f\right] $, cela tant que $t\left[ i\right] $ a
au moins un fils (condition $i\leq n//2$) et que $t\left[ i\right] >t\left[ f%
\right] $. \vspace{0.1cm}

Si $t\left[ i\right] \leq t\left[ f\right] $ on peut sortir, d'o\`{u} le 
\texttt{return None}, puisque nous n'avons rien \`{a} renvoyer, le r\'{e}%
sultat de l'ex\'{e}cution de cette \emph{proc\'{e}dure} est la modification
de \texttt{t}.

D'o\`{u} le programme~:\vspace{0.2cm}

\begin{boxedminipage}{7.7cm}
\begin{verbatim}
def suppr_min(t):
    t[1]=t[-1]
    t.pop()
    n=len(t)-1
    i=1
    while i<=n//2:
        if 2*i==n or t[2*i]<t[2*i+1]:
            f=2*i
        else:
            f=2*i+1
        if t[i]>t[f]:
            t[i],t[f]=t[f],t[i]
            i=f
        else:
            return None
\end{verbatim}
\end{boxedminipage}\vspace{0.2cm}

Noter que les deux premi\`{e}res lignes peuvent \^{e}tre remplac\'{e}es par 
\texttt{t[1]=t.pop()}, \textbf{sauf} pour un tableau d'une seule valeur, qui
doit \^{e}tre vid\'{e} par notre fonction.\vspace{0.2cm}

\textbf{Question 6}\vspace{0.2cm}

Selon le pr\'{e}ambule, je remplis un tableau auxiliaire $tas$ (initialis%
\'{e} avec un 0 en premi\`{e}re place, qui restera inutilis\'{e}\ldots ) o%
\`{u} j'entasse les valeurs du tableau initial $ti$, puis je reremplis $ti$
avec les valeurs (dans l'ordre croissant~!) extraites de $tas$ l'une apr\`{e}%
s l'autre (l'utilisation de $suppr\_min$ assure que la racine de $tas$ est
la plus petite de ses valeurs \`{a} chaque \'{e}tape~!).\vspace{0.2cm}

\textbf{N.B.} Les $n$ valeurs\ de $ti$ sont bien stock\'{e}es dans $tas\left[
1\right] ,\ldots ,tas\left[ n\right] $ pour b\'{e}n\'{e}ficier des liens p%
\`{e}re-fils de l'\'{e}nonc\'{e}\ldots \vspace{0.2cm}

La complexit\'{e} en $O\left( n\log _{2}n\right) $ est justifi\'{e}e dans l'%
\'{e}nonc\'{e} (au \textbf{II-4}). On remarquera que cet algorithme
(diabolique) donne un programme de tri efficace et \textbf{it\'{e}ratif}~!

Voici le programme~:\vspace{0.2cm}

\begin{boxedminipage}{5.4cm}
\begin{verbatim}
def tri_tas1(ti):
    tas=[0]
    for x in ti:
        entasser(x,tas)
    ti=[]
    while len(tas)>1:
        ti.append(tas[1])
        suppr_min(tas)
    return ti
\end{verbatim}
\end{boxedminipage}\vspace{0.2cm}

\textbf{Question 7}\vspace{0.2cm}

Pour effectuer les op\'{e}rations pr\'{e}c\'{e}dentes sans tableau
auxiliaire, je donne comme param\`{e}tre \`{a} la fonction $entasser$ l'%
\textbf{indice} $i$ au lieu de la \textbf{valeur} $x$ (ajout\'{e}e \`{a} la
fin du tas en construction, \`{a} la question \textbf{6}).\vspace{0.2cm}

Pour l'extraction des valeurs dans l'ordre, au lieu de supprimer la valeur 
\`{a} la racine comme \`{a} la question \textbf{7}, je l'\'{e}change avec $t%
\left[ n\right] $ ($n$ \'{e}tant fourni en param\`{e}tre) et je recr\'{e}e
un tas avec les valeurs $t\left[ 1\right] ,\ldots ,t\left[ n-1\right] $.%
\vspace{0.2cm}

Bien entendu, la m\'{e}thode ci-dessus va rendre les valeurs initiales en
ordre d\'{e}croissant si je cr\'{e}e des tas avec la plus petite valeur \`{a}
la racine\ldots\ Il suffit d'inverser le sens des in\'{e}galit\'{e}s dans
les tests pour retrouver l'ordre croissant~!

Ci-dessous les programmes (\`{a} peine) modifi\'{e}s~:\vspace{0.2cm}

\begin{boxedminipage}{13.5cm}
\begin{verbatim}
def entasser(i,t): #entasse t[i] parmi t[1],...,t[i-1]
    p=i//2 #le pere
    while i>1 and t[i]>t[p]:
        t[i],t[p]=t[p],t[i]
        i,p=p,p//2

def suppr_min(t,n): #echange t[1] et t[n] et
                    #refait un tas avec les n-1 premieres valeurs
    t[1],t[n]=t[n],t[1]
    n-=1
    i=1
    while i<=n//2:
        if 2*i==n or t[2*i]>t[2*i+1]:
            f=2*i
        else:
            f=2*i+1
        if t[i]<t[f]:
            t[i],t[f]=t[f],t[i]
            i=f
        else:
            return None

def tri_tas2(ti):
    n=len(ti)-1
    for i in range(2,n+1):
        entasser(i,ti)
    for i in range(n,1,-1):
        suppr_min(ti,i)
    return ti
\end{verbatim}
\end{boxedminipage}\vspace{0.2cm}

La complexit\'{e} en temps est similaire, la complexit\'{e} en m\'{e}moire
est am\'{e}lior\'{e}e~!\vspace{0.3cm}

\textbf{Question 8}\vspace{0.2cm}

L'algorithme est d\'{e}crit dans l'\'{e}nonc\'{e}\ldots\ Il faut se rappeler
que le p\`{e}re du n\oe ud d'indice $n$ a pour indice $r=n//2$ et que deux
cas se pr\'{e}sentent~:

\begin{itemize}
\item soit $n=2r$, auquel cas le n\oe ud d'indice $r$ a un seul fils

\item soit $n=2r+1$, auquel cas le n\oe ud d'indice $r$ a deux fils,
d'indices $2r$ et $2r+1$
\end{itemize}

Dans tous les cas, le n\oe ud d'indice $n//2$ est le dernier \`{a} avoir au
moins un fils, d'o\`{u} le test conditionnant l'appel r\'{e}cursif.\vspace{%
0.2cm}

\begin{boxedminipage}{7cm}
\begin{verbatim}
def ordonner(t,r):
    n=len(t)-1
    if 2*r==n or t[2*r]>t[2*r+1]:
        f=2*r
    else:
        f=2*r+1
    if t[r]<t[f]:
        t[r],t[f]=t[f],t[r]
        if f<=n//2:
            ordonner(t,f)
\end{verbatim}
\end{boxedminipage}\vspace{0.2cm}

La terminaison du programme est justifi\'{e}e par le fait que le second param%
\`{e}tre est au moins doubl\'{e} \`{a} chaque appel r\'{e}cursif, tandis que
l'appel r\'{e}cursif $ordonner(t,f)$ est soumis \`{a} la condition $f<=n//2$
(avec $n$ qui reste inchang\'{e}, le tableau est r\'{e}organis\'{e} mais sa
taille est constante~!).\vspace{0.2cm}

La correction se prouve par r\'{e}currence sur la hauteur du sous-arbre de
racine $t\left[ r\right] $.\vspace{0.2cm}

Noter que, comme au \textbf{9}, je construis le tas avec le maximum \`{a} la
racine (je choisis ci-dessus le plus\textbf{\ grand} des deux fils), pour
obtenir un tri croissant apr\`{e}s la seconde phase, identique \`{a} celle
du \textbf{9}.\vspace{0.2cm}

Voici le programme final, qui op\`{e}re aussi en place~:\vspace{0.2cm}

\begin{boxedminipage}{6cm}
\begin{verbatim}
def tri_tas3(ti):
    n=len(ti)-1
    d=n//2
    for r in range(d,0,-1):
        ordonner(ti,r)
    for i in range(n,1,-1):
        suppr_min(ti,i)
    return ti        
\end{verbatim}
\end{boxedminipage}\vspace{0.5cm}

\textbf{Question 9}\vspace{0.2cm}

Du fait de la boucle \texttt{for r\ldots } ci-dessus, la complexit\'{e} de
la cr\'{e}ation du tas est la somme des $C\left( r\right) $ pour $r=1,\ldots
,d$, o\`{u} $C\left( r\right) $ est le nombre de comparaisons (entre \'{e}l%
\'{e}ments du tableau comme d'habitude) effectu\'{e}e lors de l'appel de $%
ordonner\left( t,r\right) $.\vspace{0.2cm}

Je fixe $h$ entier tel que $2^{h-1}\leq d<2^{h}$~; $h$ est le niveau des
derniers n\oe uds qui ne sont pas des feuilles et j'ai, \`{a} la lecture du
programme $ordonner$ 
\begin{equation*}
\forall r\in \left[ \!\left[ 2^{h-1},d\right] \!\right] \quad C\left(
r\right) =2
\end{equation*}%
et%
\begin{equation}
\forall r<2^{h-1}\quad C\left( r\right) \leq 2+\max \left( C\left( 2r\right)
,C\left( 2r+1\right) \strut \right) \vspace{0.2cm}
\end{equation}%
J'en d\'{e}duis par r\'{e}currence sur $j\in \left[ \!\left[ 0,h\right] \!%
\right] $ 
\begin{equation*}
\mathcal{P}_{j}:\forall r\in \left[ \!\left[ 1,d\right] \!\right] \quad r\in %
\left[ \!\left[ 2^{h-j-1},2^{h-j}\right[ \!\right[ \Rightarrow C\left(
r\right) \leq 2\left( 1+j\right) .
\end{equation*}%
En effet, j'ai $\mathcal{P}_{0}$ d'apr\`{e}s ce qui pr\'{e}c\`{e}de et si je
suppose $\mathcal{P}_{j}$ et que je consid\`{e}re $r$ entier de $\left[ \!%
\left[ 2^{h-j-2},2^{h-j-1}\right[ \!\right[ $ j'ai 
\begin{equation*}
2^{h-j-2}\leq r\leq 2^{h-j-1}-1\quad \text{d'o\`{u}}\quad 2^{h-j-1}\leq
2r\leq 2^{h-j-1}-2\quad \text{et}\quad 2^{h-j-1}+1\leq 2r+1\leq 2^{h-j-1}-1
\end{equation*}%
par cons\'{e}quent $2r$ et $2r+1$ sont dans $\left[ \!\left[
2^{h-j-1},2^{h-j}\right[ \!\right[ $, d'o\`{u} gr\^{a}ce \`{a} $\left(
1\right) $ et \`{a} $\mathcal{P}_{j}$%
\begin{equation*}
C\left( r\right) \leq 2+2\left( 1+j\right) =2\left( 1+j+1\right)
\end{equation*}%
et donc $\mathcal{P}_{j+1}$ est v\'{e}rifi\'{e}e~!\vspace{0.2cm}

Or l'intervalle $\left[ \!\left[ 2^{h-j-1},2^{h-j}\right[ \!\right[ $
contient exactement $2^{h-j-1}$ entiers, d'o\`{u}%
\begin{equation}
\sum_{r\in \left[ 2^{h-j-1},2^{h-j}\right[ }C\left( r\right) \leq
2^{h-j-1}\times 2\left( 1+j+1\right) =2^{h}\times \dfrac{j+1}{2^{j}}
\end{equation}%
(pour $j=0$, remplacer $\left[ \!\left[ 2^{h-1},2^{h}\right[ \!\right[ $ par 
$\left[ \!\left[ 2^{h-1},d\right] \!\right] $, la majoration est
\textquotedblleft encore plus vraie\textquotedblright ~!).\vspace{0.2cm}

Or on conna\^{\i}t pour tout $z$ complexe tel que $\left\vert z\right\vert
<1 $ la relation (produit de Cauchy de la s\'{e}rie g\'{e}om\'{e}trique de
raison $z$ par elle-m\^{e}me~!)%
\begin{equation*}
\sum_{j=0}^{\infty }\left( j+1\right) z^{j}=\dfrac{1}{\left( 1-z\right) ^{2}}%
\quad \text{d'o\`{u}}\quad \sum_{j=0}^{\infty }\dfrac{j+1}{2^{j}}=4.
\end{equation*}%
Il en r\'{e}sulte en sommant les in\'{e}galit\'{e}s $\left( 2\right) $ pour $%
j=0,\ldots ,h$ et en majorant g\'{e}n\'{e}reusement%
\begin{equation*}
\sum_{r=1}^{d}C\left( r\right) \leq 2^{h}\times 4\quad \text{or}\quad
2^{h}\leq n
\end{equation*}%
d'o\`{u} finalement~:%
\begin{equation*}
\fbox{La complexit\'{e} de la cr\'{e}ation du tas est ici un $O\left(
n\right) $.}\vspace{0.2cm}
\end{equation*}%
On notera que ---~pour la complexit\'{e} globale du tri par tas~--- le b\'{e}%
n\'{e}fice reste modeste (quelques pour cent) et diminue lorsque $n$
augmente, puisque c'est la phase d'extraction, toujours en $n\log _{2}n$,
qui est pr\'{e}pond\'{e}rante\ldots\ Mais la structure de tas peut servir 
\`{a} d'autres choses qu'au tri par tas~!\vspace{0.5cm}

\textbf{Question 10}\vspace{0.2cm}

\begin{boxedminipage}{10cm}
\begin{verbatim}
    def ajoute(self,x):
        if self.vide : 
            self.vide = False
            self.e = x
            self.gauche = Noeud()
            self.droite = Noeud()
        elif self.e > x : self.gauche.ajoute(x)
        elif self.e < x : self.droite.ajoute(x)    
\end{verbatim}
\end{boxedminipage}\vspace{0.5cm}

\textbf{Question 11}\vspace{0.2cm}

\begin{boxedminipage}{13cm}
\begin{verbatim}
    def recherche(self,x):
        if self.vide : return False
        elif self.e == x : return True
        elif self.e > x : return self.gauche.recherche(x)
        else : return self.droite.recherche(x)  
\end{verbatim}
\end{boxedminipage}\vspace{0.5cm}

\textbf{Question 12}\vspace{0.2cm}

\begin{boxedminipage}{16cm}
\begin{verbatim}
    def profondeur(self):
        if self.vide : return -1
        return 1+max(self.gauche.profondeur(),self.droite.profondeur())
\end{verbatim}
\end{boxedminipage}\vspace{0.5cm}

\textbf{Question 13}\vspace{0.2cm}

\begin{boxedminipage}{10cm}
\begin{verbatim}
    def arbreToTab(self,t,i):
        if not self.vide:
            t[i]=self.e
            self.gauche.arbreToTab(t,2*i)
            self.droite.arbreToTab(t,2*i+1)
            
    def affiche(self):
        nMax = 2**(self.profondeur()+1)
        t = [-1]*nMax
        self.arbreToTab(t,1)
        afficher(t)
\end{verbatim}
\end{boxedminipage}\vspace{0.5cm}

\textbf{Question 14}\vspace{0.2cm}

\begin{boxedminipage}{16cm}
\begin{verbatim}
    def taille(self):
        if self.vide : return 0
        return 1+self.gauche.taille()+self.droite.taille()
\end{verbatim}
\end{boxedminipage}\vspace{0.5cm}

\textbf{Question 15}\vspace{0.2cm}

\begin{boxedminipage}{16cm}
\begin{verbatim}
    def tri(self):
        n = self.taille()
        t = [-1]*(n)
        self.range(t,0,n-1)
        return(t)
        
    def range(self,t,i,j):
        if i == j :
            t[i]=self.e
            print(self.e,i,j)
        else :
            if not self.gauche.vide :
                kg = self.gauche.taille()
                t[i+kg]=self.e
                self.gauche.range(t,i,i+kg-1)
                if not self.droite.vide :
                    self.droite.range(t,i+kg+1,j)
            else :
                t[i]=self.e
                self.droite.range(t,i+1,j)
\end{verbatim}
\end{boxedminipage}\vspace{0.5cm}

\textbf{Question 16}
Le tri par arbre binaire de recherche consiste \`a construire un arbre binaire de recherche contenant tous les \'el\'ements de l'ensemble \`a trier et \`a faire le parcours infixe de cet arbre. On obtient une complexit\'e en $O(h*n)$. Dans le pire cas, $h = n$ et la complexit\'e n'est pas satisfaisante. Mais si les \'el\'ements ont \'et\'e m\'elang\'es al\'eatoirement, on a une hauteur moyenne en $O(\log n)$. Le tri par arbre binaire de recherche a alors une complexit\'e moyenne en $O(n\log n)$ ce qui est optimal. 

{\bf Remarque :} il existe plusieurs variantes des arbres binaires de recherche qui maintiennent un certain \'equilibre de l'arbre et permettent d'assurer une hauteur logarithmique. Dans ce cas, la complexit\'e pire cas du tri est \'egalement un $O(n\log n)$.

\vspace{.5cm}

\textbf{Question 17}\vspace{0.2cm}

\begin{boxedminipage}{16cm}
\begin{verbatim}             
    def affectation(self,n) :
        v,e,g,d = n.vide,n.e,n.gauche,n.droite
        self.vide = v
        self.e = e
        self.gauche = g
        self.droite = d
        
    def rechEtSupprMax(self):
        if self.droite.vide : 
            res = self.e
            self.affectation(self.gauche)
            return res
        elif self.droite.gauche.vide and self.droite.droite.vide : 
            res = self.droite.e
            self.droite.vide = True
            return res
        else :
            return self.droite.rechEtSupprMax()
    
    def supprRacine(self):
        if self.gauche.vide :
            self.affectation(self.droite)
        elif self.gauche.gauche.vide and self.gauche.droite.vide : 
            self.e = self.gauche.e
            self.gauche.vide = True
        elif self.gauche.droite.vide : 
            self.e = self.gauche.e
            self.gauche.affectation(self.gauche.gauche)
        else :
            self.e = self.gauche.rechEtSupprMax()
    
    def suppr(self,x):
        if not self.vide : 
            if self.e == x and self.gauche.vide and self.droite.vide : 
                self.vide = True
            elif self.e == x : self.supprRacine()
            elif self.e > x and not self.gauche.vide : self.gauche.suppr(x)
            elif self.e < x and not self.droite.vide : self.droite.suppr(x)
 \end{verbatim}
\end{boxedminipage}\vspace{0.5cm}
\end{document}